训练赛一
7-5 连续因子 (20 分)
思路：
暴力枚举起点，每次从起点往后延伸，并且更新长度和起点，最后输出即可。
代码：
int main(){ ll n;scanf("%lld",&n); ll res=0,pos=-1; for(ll i=2;i*i<=n+1;i++){ ll tmp=0; ll tmpn=n,t=i; for(;tmpn%t==0;t++,tmp++) tmpn/=t; if(res<tmp){ res=tmp; pos=i; } } if(res==0){ cout<<"1"<<"\n"<<n<<"\n"; return 0; } cout<<res<<endl; for(int i=1;i<=res;i++){ cout<<pos+i-1; if(i!=res) cout<<"*"; } puts(""); return 0; }
7-6 链表去重 (25 分)
思路：
之前存图的时候用链式前向星，这里也可以借助数组模拟链表，然而我写的暴力只过了15分。
代码：
const int maxn=1e5+100; bool vis[maxn]; int w[maxn],ne[maxn],del_w[maxn],del_ne[maxn]; int n,head=-1,pre=-1,del_head=-1,del_tail=-1; int main(){ head=read,n=read; for(int i=1;i<=n;i++){ int pos=read; w[pos]=read;ne[pos]=read; } for(int i=head;~i;i=ne[i]){ if(vis[abs(w[i])]){ if(pre==-1) head=ne[i]; else ne[pre]=ne[i]; if(del_head==-1) del_head=i; del_w[i]=w[i]; if(del_tail!=-1) del_ne[del_tail]=i; del_tail=i; } else{ vis[abs(w[i])]=1; pre=i; } } del_ne[del_tail]=-1; for(int i=head;~i;i=ne[i]){ printf("%05d %d ",i,w[i]); if(ne[i]==-1) puts("-1"); else printf("%05d\n",ne[i]); } for(int i=del_head;~i;i=del_ne[i]){ printf("%05d %d ",i,del_w[i]); if(del_ne[i]==-1) puts("-1"); else printf("%05d\n",del_ne[i]); } return 0; }
7-8 凑零钱 (30 分)
思路：
背包dp判断能否构成的同时记录路径，输出答案的时候倒着输出。
dfs也能过。
代码：
const int maxn=1e4+100; int n,m,a[maxn],dp[maxn]; int vis[maxn][maxn]; bool cmp(int a,int b){ return a>b; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) for(int j=m;j>=0;j--){ if(j>=a[i]){ if(dp[j]<=dp[j-a[i]]+a[i]){ dp[j]=dp[j-a[i]]+a[i]; vis[i][j]=1; } } } if(dp[m]!=m) puts("No Solution"); else{ int tmpm=m; while(tmpm){ if(vis[n][tmpm]){ cout<<a[n]; tmpm-=a[n]; if(tmpm>0) cout<<" "; } n--; } } return 0; }
7-9 特殊堆栈 (30 分)
思路：
有点思维的题。在动态求中位数时，一般都是用对顶堆维护。但是对顶堆的删除操作不容易实现。
先考虑暴力的做法，是维护一个栈和一个vector容器，每次询问时都对vector进行sort，这样复杂度是O ( n 2 )
如果在插入的时候就保持vector的有序，每次查询时都二分查找该数在有序列表中的位置，时间复杂度就降到了O ( n l o g n + c )
代码：
const int maxn=1e5+100; stack<int>stk; vector<int>v; int main(){ int n;cin>>n; char op[15]; for(int i=1;i<=n;i++){ cin>>op; ///cout<<op<<endl; if(op[1]=='o'){ if(v.size()==0) puts("Invalid"); else{ int x=stk.top(); stk.pop(); cout<<x<<endl; auto pos=lower_bound(v.begin(),v.end(),x); v.erase(pos); } } else if(op[1]=='u'){ int x;cin>>x; stk.push(x); auto pos=lower_bound(v.begin(),v.end(),x); v.insert(pos,x); } else if(op[1]=='e') { if(v.size()==0) puts("Invalid"); else{ int t=(v.size()+1)/2-1; cout<<v[t]<<endl; } } cout<<i<<" "<<op<<endl; } return 0; }
7-11 肿瘤诊断 (30 分)
思路：
三维的bfs，有点离谱，注意判断每个连通块的最低1的个数。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct node{ int x,y,z; }; int a[60][1300][130],n,m,l,t,b[60][1300][130],res=0; bool check(int x,int y,int z){ if(x>=0&&x<l&&y>=0&&y<m&&z>=0&&z<n&&a[x][y][z]==1&&b[x][y][z]==0) return 1; return 0; } int nx[]={1,-1,0,0,0,0}; int ny[]={0,0,1,-1,0,0}; int nz[]={0,0,0,0,1,-1}; void bfs(int x,int y,int z){ queue<node>q; q.push({x,y,z}); b[x][y][z]=1; int tmp=0; while(!q.empty()){ node t=q.front();q.pop(); tmp++; int tx=t.x,ty=t.y,tz=t.z; for(int i=0;i<6;i++){ int xx=tx+nx[i],yy=ty+ny[i],zz=tz+nz[i]; if(check(xx,yy,zz)){ b[xx][yy][zz]=1; q.push({xx,yy,zz}); } } } if(tmp>=t) res+=tmp; } int main(){ cin>>m>>n>>l>>t; for(int i=0;i<l;i++) for(int j=0;j<m;j++) for(int k=0;k<n;k++) cin>>a[i][j][k]; for(int i=0;i<l;i++) for(int j=0;j<m;j++) for(int k=0;k<n;k++) if(a[i][j][k]==1&&!b[i][j][k]) bfs(i,j,k); cout<<res<<endl; return 0; }
训练赛二
7-4 天梯地图 (30 分)
思路：
跑两次最短路。
对于时间来说，时间最短为第一关键字，距离最短为第二关键字。
对于距离来说，距离最短为第一关键字，节点最少为第二关键字。
用pre数组记录一下这个点是从哪个点转移过来的，输出的时候倒着推回去。
判断两个路径是否相同，先判断节点个数，在枚举节点判断对应的是否相等。
n只有500，写个朴素的dijkstra就好了
也不知道被卡哪了。
代码：
const int maxn=1e6+7,inf=0x3f3f3f3f; int n,m,g1[510][510],g2[510][510],s,e; int dis1[maxn],st1[maxn],pre1[maxn],cnt[maxn]; int dis2[maxn],st2[maxn],pre2[maxn],d[maxn]; void dijkstra1(){ memset(dis1,0x3f,sizeof dis1); dis1[s]=0; pre1[s]=-1; for(int i=1;i<=n;i++) cnt[i]=1; for(int i=0;i<n-1;i++){ int t=-1; for(int j=1;j<=n;j++) if(!st1[j]&&(t==-1||dis1[t]>dis1[j])) t=j; for(int j=1;j<=n;j++){ if(dis1[j]>dis1[t]+g1[t][j]){ dis1[j]=dis1[t]+g1[t][j]; pre1[j]=t; cnt[j]=cnt[t]+1; } else if(dis1[j]==dis1[t]+g1[t][j]){ if(cnt[j]>cnt[t]+1){ pre1[j]=t; cnt[j]=cnt[t]+1; } } } st1[t]=1; } } void dijkstra2(){ memset(dis2,0x3f,sizeof dis2); memset(d,0x3f,sizeof d); dis2[s]=0;d[s]=0; pre2[s]=-1; for(int i=0;i<n-1;i++){ int t=-1; for(int j=1;j<=n;j++) if(!st2[j]&&(t==-1||dis2[t]>dis2[j])) t=j; for(int j=1;j<=n;j++){ if(dis2[j]>dis2[t]+g2[t][j]){ dis2[j]=dis2[t]+g2[t][j]; pre2[j]=t; d[j]=d[t]+g1[t][j]; } else if(dis2[j]==dis2[t]+g2[t][j]){ if(d[j]>d[t]+g1[t][j]){ pre1[j]=t; d[j]=d[t]+g1[t][j]; } } } st2[t]=1; } } int main(){ n=read,m=read; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) g1[i][j]=g2[i][j]=0; else g1[i][j]=g2[i][j]=inf; rep(i,1,m){ int u=read,v=read,op=read,l=read,t=read; u++,v++; if(op==1){ g1[u][v]=min(g1[u][v],l); g2[u][v]=min(g2[u][v],t); } else{ g1[u][v]=min(g1[u][v],l); g2[u][v]=min(g2[u][v],t); g1[v][u]=min(g1[v][u],l); g2[v][u]=min(g2[v][u],t); } } s=read,e=read; s++,e++; dijkstra1(); dijkstra2(); int res_time=dis2[e],res_dis=dis1[e]; string path_time,path_dis; int tmp=e; while(tmp!=-1){ path_time+=(tmp-1+'0'); tmp=pre2[tmp]; } tmp=e; while(tmp!=-1){ path_dis+=(tmp-1+'0'); tmp=pre1[tmp]; } reverse(path_dis.begin(), path_dis.end()); reverse(path_time.begin(), path_time.end()); if(path_dis==path_time){ printf("Time = %d; Distance = %d: ",res_time,res_dis); for(int i=0;i<path_dis.size();i++){ cout<<path_dis[i]; if(i!=path_dis.size()-1) cout<<" => "; } } else{ printf("Time = %d: ",res_time); for(int i=0;i<path_time.size();i++){ cout<<path_time[i]; if(i!=path_time.size()-1) cout<<" => "; } puts(""); printf("Distance = %d: ",res_dis); for(int i=0;i<path_dis.size();i++){ cout<<path_dis[i]; if(i!=path_dis.size()-1) cout<<" => "; } } return 0; }
7-9 家庭房产 (25 分)
思路：
思路不难想，就是并查集，但是有点难处理。
每次将根节点维护为家族里编号最小的编号，剩下的就是模拟了。
代码：
const int maxn=11000; int root[maxn],siz[maxn]; struct node{ ll minid,siz,id; double cnt,area; }a[1100]; int cnt_sum[maxn],cnt_area[maxn]; bool vis[maxn]; int Find(int x){ if(x!=root[x]) root[x]=Find(root[x]); return root[x]; } void Union(int x,int y){ x=Find(x),y=Find(y); if(x!=y){ if(x<y){ root[y]=x; siz[x]+=siz[y]; cnt_area[x]+=cnt_area[y]; cnt_sum[x]+=cnt_sum[y]; } else{///y的编号小 root[x]=y; siz[y]+=siz[x]; cnt_area[y]+=cnt_area[x]; cnt_sum[y]+=cnt_sum[x]; } } } bool cmp(node a,node b){ if(a.area==b.area){ return a.id<b.id; } return a.area>b.area; } int main(){ for(int i=0;i<=9999;i++) root[i]=i,siz[i]=1; int n=read; rep(i,1,n){ int now=read; vis[now]=1; int fa=read,mo=read; if(fa!=-1){ Union(fa,now); vis[fa]=1; } if(mo!=-1){ vis[mo]=1; Union(mo,now); } int k=read; rep(j,1,k){ int son=read; vis[son]=1; Union(son,now); } int t=Find(now); ll t1=read,t2=read; cnt_sum[t]+=t1; cnt_area[t]+=t2; } int cnt=0; for(int i=0;i<=9999;i++) if(vis[i]&&i==Find(i)){ a[++cnt]={i,siz[i],cnt,cnt_sum[i]*1.0/siz[i],cnt_area[i]*1.0/siz[i]}; } sort(a+1,a+1+cnt,cmp); cout<<cnt<<endl; for(int i=1;i<=cnt;i++) printf("%04lld %lld %.3f %.3f\n",a[i].minid,a[i].siz,a[i].cnt,a[i].area); return 0; }
7-10 最长对称子串 (25 分)
思路：
有好几种解法：
1.马拉车，复杂度O ( n )
2.二分对称子串的长度，复杂度O ( n l o g n )
3.枚举对称点，每次从对称点往周围延伸，记录最大长度。跟马拉车的思想类似，复杂度O ( n 2 )
4.枚举起点和终点，复杂度O ( n 3 ),但是跑不满，应该也能过。
代码：
const int maxn= 3000+10; char str[maxn]; string s; int len1,len2,res,p[maxn]; void init(){ str[0]='$';str[1]='#'; for(int i=0;i<len1;i++){ str[i*2+2]=s[i]; str[i*2+3]='#'; } len2=len1*2+2; str[len2]='*'; } void manacher(){ int id=0,mx=0; for(int i=1;i<len2;i++){ if(mx>i) p[i]=min(p[id*2-i],mx-i); else p[i]=1; for(;str[i+p[i]]==str[i-p[i]];p[i]++); if(p[i]+i>mx){ mx=p[i]+i; id=i; } } } int main(){ getline(cin,s); len1=s.size(); init(); manacher(); int res=0; for(int i=1;i<len2;i++) res=max(res,p[i]); cout<<res-1; return 0; }
7-11 垃圾箱分布 (30 分)
思路：
将垃圾箱的编号调整到[ n + 1 , n + m ]
m最大为10，对每个垃圾箱都跑一遍最短路，记录最短距离，平均距离，编号，sort后输出。
代码：
const int maxn=1e6+7,inf=0x3f3f3f3f; int n,m,k,ds,g[1100][1100]; struct node{ int id,minn; double ave; }a[12]; int idx; bool cmp(node a,node b){ if(a.minn==b.minn){ if(a.ave==b.ave){ return a.id<b.id; } return a.ave<b.ave; } return a.minn>b.minn; } int dis[maxn];///记录当前点到起点的距离 bool st[maxn];///若当前点的最短距离已经确定 为true void dfs(int s){ memset(dis,0x3f,sizeof dis);///初始化距离为正无穷 memset(st,0,sizeof st); dis[s]=0;///从1开始更新 for(int i=0;i<n+m-1;i++){ int t=-1; ///找到当前不在st中而且距离最小的点t for(int j=1;j<=n+m;j++) if(!st[j]&&(t==-1||dis[t]>dis[j])) t=j; ///用点t更新其他不在st中的点的距离 for(int j=1;j<=n+m;j++) dis[j]=min(dis[j],dis[t]+g[t][j]); ///将t点放到st集合里 st[t]=true; } int res=inf,cnt=0,sum=0; for(int i=1;i<=n;i++){ if(dis[i]>ds){ break; } sum+=dis[i];cnt++; res=min(res,dis[i]); } if(cnt==n){ idx++; a[idx]={s,res,sum*1.0/n}; } } int main(){ n=read,m=read,k=read,ds=read; for(int i=1;i<=n+m;i++) for(int j=1;j<=n+m;j++) if(i==j) g[i][j]=0; else g[i][j]=inf; for(int i=1;i<=k;i++){ string x,y;cin>>x>>y; int t=read; int cntx=0,cnty=0; if(x[0]=='G'){ for(int j=1;j<x.size();j++) cntx=cntx*10+x[j]-'0'; cntx+=n; } else{ for(int j=0;j<x.size();j++) cntx=cntx*10+x[j]-'0'; } if(y[0]=='G'){ for(int j=1;j<y.size();j++) cnty=cnty*10+y[j]-'0'; cnty+=n; } else{ for(int j=0;j<y.size();j++) cnty=cnty*10+y[j]-'0'; } /// cout<<i<<"******"<<cntx<<" "<<cnty<<endl; g[cntx][cnty]=g[cnty][cntx]=min(t,g[cntx][cnty]); } for(int i=n+1;i<=n+m;i++) dfs(i); /// cout<<idx<<endl; if(idx==0) puts("No Solution"); else{ sort(a+1,a+1+idx,cmp); cout<<"G"<<a[1].id-n<<endl; printf("%.1lf %.1lf\n",1.0*a[1].minn,a[1].ave); } return 0; }
