概述
1
2#include<stdio.h> #include<string.h> #include<stdlib.h> struct info { int x,y,len,wait,dir; }; const int MaxN=50; const int MaxM=100; const int MaxL=250; const int Add[4][2]={-1,0,0,1,1,0,0,-1}; int N,cases,n,m,D,Rs,fin,sta,T,ex,ey; int route[MaxN*MaxL]; int map[MaxL+1][MaxL+1]; int ants[MaxL+1][MaxL+1][4]; int list[MaxM]; info ant[MaxM]; void init() { int i,j,k,t,x1,y1,x2,y2; scanf("%d%d%d",&n,&m,&D); x1=0;y1=0;Rs=0; for(i=0;i<n;i++) { scanf("%d%d",&x2,&y2); if(x1>x2) t=0; if(y1<y2) t=1; if(x1<x2) t=2; if(y1>y2) t=3; for(;x1!=x2||y1!=y2;) { route[Rs]=t; Rs++; x1+=Add[t][0]; y1+=Add[t][1]; } } fin=0;sta=0; for(i=0;i<=MaxL;i++) for(j=0;j<=MaxL;j++) for(k=0;k<4;k++) ants[i][j][k]=-1; } void work() { bool ok; int i,j,x,y,d,p,tmp; int go[MaxM]; memset(go,0,sizeof(go)); ok=0; for(i=0;i<sta;i++) if(ant[i].x<0) ok++; for(i=0;i<sta;i++) if(ant[i].x>=0) { x=ant[i].x;y=ant[i].y; for(j=0;j<4;j++) if(ants[x][y][j]>=0) { tmp=ants[x][y][j]; if(ant[tmp].wait>ant[i].wait || (ant[tmp].wait==ant[i].wait && ant[tmp].len>ant[i].len)) { p=1;go[i]=1;ok++; break; } } } do{ ok=0; for(i=0;i<sta;i++) if(!go[i] && ant[i].x>0) { d=map[ant[i].x][ant[i].y]; x=ant[i].x+Add[d][0];y=ant[i].y+Add[d][1]; if(ants[x][y][d]>=0&&go[ants[x][y][d]]==1) { go[i]=1;ok=1; continue; } } }while(ok); for(i=0;i<sta;i++) if(!go[i]&&ant[i].x>=0) { ant[i].len++;ant[i].wait=0; ants[ant[i].x][ant[i].y][ant[i].dir]=-1; } else if(ant[i].x>=0) ant[i].wait++; for(i=0;i<sta;i++) if(!go[i]&&ant[i].x>=0) { x=ant[i].x;y=ant[i].y; if(x==100&&y==100&&i!=sta-1) { ants[100][100][map[100][100]]=i+1; } d=map[x][y]; ant[i].x+=Add[d][0];ant[i].y+=Add[d][1];ant[i].dir=d; if(ant[i].x==ex&&ant[i].y==ey) { list[fin]=i; fin++; ant[i].x=-1; } else ants[ant[i].x][ant[i].y][d]=i; } } void write() { int i; printf("Case %d:n",cases); printf("Carl finished the path at time %dn",ant[0].len+1); printf("The ants finished in the following order:n"); printf("%d",list[0]); for(i=1;i<m;i++) printf(" %d",list[i]); printf("n"); printf("The last ant finished the path at time %dn",T+1); if(cases<N) printf("n"); } int main() { int X,Y; scanf("%d",&N); for(cases=1;cases<=N;cases++) { init(); X=100;Y=100;ex=-1;ey=-1; for(T=0;fin<m;T++) { if(T<Rs) { map[X][Y]=route[T]; X+=Add[route[T]][0];Y+=Add[route[T]][1]; if(T==Rs-1) { ex=X;ey=Y; } } if(T%D==0&&sta<m) { if(ants[100][100][map[100][100]]) ants[100][100][map[100][100]]=sta; ant[sta].x=100;ant[sta].y=100; ant[sta].len=0;ant[sta].wait=0;ant[sta].dir=map[100][100]; sta++; } work(); } write(); } return 0; }#include<cstdio> #include<math.h> const double eps=1e-6; int x[25],y[25],n,i,len,px,py,cases; double ra,rb,r; char dr; bool check(double ox,double oy) { int i,s; s=0; for(i=0;i<n;i++) if(x[i]>ox && ((y[i]>oy)^(y[i+1]>oy))) s++; if(s%2==0) return false; for(i=0;i<n;i++) { if((x[i]-ox)*(x[i]-ox) + (y[i]-oy)*(y[i]-oy)<(r-eps)*(r-eps)) return false; if(x[i]==x[i+1] && ((y[i]>oy)^(y[i+1]>oy))&&fabs(x[i]-ox)<r-eps) return false; if(y[i]==y[i+1]&&((x[i]>ox)^(x[i+1]>ox))&&fabs(y[i]-oy)<r-eps) return false; } return true; } bool ok() { int i,j; double di,dd,mx,my,dx,dy; for(i=0;i<n;i++) if(x[i]==x[i+1]) for(j=0;j<n;j++) if(y[j]==y[j+1]) { if(check(x[i]+r,y[j]+r)) return true; if(check(x[i]+r,y[j]-r)) return true; if(check(x[i]-r,y[j]+r)) return true; if(check(x[i]-r,y[j]+r)) return true; } for(i=0;i<n;i++) for(j=0;j<n;j++) if(x[i]==x[i+1]) { di=fabs(x[j]-(x[i]+r)); if(di<r) { dd=sqrt(r*r-di*di); if(check(x[i]+r,y[j]+dd)) return true; if(check(x[i]+r,y[j]-dd)) return true; } di=(fabs(x[j]-(x[i]-r))); if(di<r) { dd=sqrt(r*r-di*di); if(check(x[i]-r,y[j]+dd)) return true; if(check(x[i]-r,y[j]-dd)) return true; } } else { di=fabs(y[j]-(y[i]+r)); if(di<r) { dd=sqrt(r*r-di*di); if(check(x[j]+dd,y[i]+r)) return true; if(check(x[j]-dd,y[i]+r)) return true; } di=fabs(y[j]-(y[i]-r)); if(di<r) { dd=sqrt(r*r-di*di); if(check(x[j]+dd,y[i]-r)) return true; if(check(x[j]-dd,y[i]-r)) return true; } } for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) { mx=(x[i]+x[j])/2.0; my=(y[i]+y[j])/2.0; di=sqrt((x[i]-mx)*(x[i]-mx) + (y[i]-my)*(y[i]-my)); if(di>0&&di<r) { dd=sqrt(r*r-di*di); dx=(my-y[i])/di*dd; dy=(x[i]-mx)/di*dd; if(check(mx+dx,my+dy)) return true; if(check(mx-dx,my-dy)) return true; } } return false; } int main() { while(scanf("%d",&n)&&n) { if(cases) printf("n"); px=0;py=0; for(i=1;i<=n;i++) { scanf("%d %c",&len,&dr); if(dr=='R') px+=len; if(dr=='L') px-=len; if(dr=='U') py+=len; if(dr=='D') py-=len; x[i]=px; y[i]=py; } ra=0;rb=999; while(rb-ra>eps) { r=(ra+rb)/2; if(ok()) ra=r; else rb=r; } printf("Case Number %d radius is: %.2lfn",++cases,r); } return 0; }
3
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MaxN=10+5; char g1[MaxN][MaxN],g2[MaxN][MaxN],g3[MaxN][MaxN],g4[MaxN][MaxN],g5[MaxN][MaxN],g6[MaxN][MaxN]; int p1[MaxN][MaxN],p2[MaxN][MaxN],p3[MaxN][MaxN],p4[MaxN][MaxN],p5[MaxN][MaxN],p6[MaxN][MaxN]; int g[MaxN][MaxN][MaxN]; int n; void init(); void work(); bool update_front(); bool update_left(); bool update_back(); bool update_right(); bool update_top(); bool update_bottom(); int main() { for(;;) { scanf("%d",&n); if(n==0) break; init(); work(); } return 0; } void init() { for(int i=0;i<n;++i) scanf("%s %s %s %s %s %s",g1[i],g2[i],g3[i],g4[i],g5[i],g6[i]); } void work() { fill(p1[0],p1[n],0);fill(p2[0],p2[n],0);fill(p3[0],p3[n],0); fill(p4[0],p4[n],0);fill(p5[0],p5[n],0);fill(p6[0],p6[n],0); fill(g[0][0],g[n][0],-1); for(;;) { bool quit=true; if(update_front()) quit=false; if(update_left()) quit=false; if(update_back()) quit=false; if(update_right()) quit=false; if(update_top()) quit=false; if(update_bottom()) quit=false; if(quit) break; } int ans=n*n*n; for(int i=0;i<n;++i) for(int j=0;j<n;++j) for(int k=0;k<n;++k) if(g[i][j][k]==0) --ans; printf("Maximum weight: %d gram(s)n",ans); } bool update_front() { bool upd=false; for(int i=0;i<n;++i) for(int j=0;j<n;++j) { int &t=p1[i][j]; char ch=g1[i][j]; if(t==n) continue; int &val=g[n-t-1][j][i]; if(val==0) { ++t; upd=true; } else if(ch=='.') { val=0; ++t; upd=true; } else if(val==-1) { val=ch-'A'+1; upd=true; } else if(val!=ch-'A'+1) { val=0; ++t; upd=true; } } return upd; } bool update_left() { bool upd=false; for(int i=0;i<n;++i) for(int j=0;j<n;++j) { int &t=p2[i][j]; char ch=g2[i][j]; if(t==n) continue; int &val=g[j][t][i]; if(val==0) { ++t; upd=true; } else if(ch=='.') { val=0; ++t; upd=true; } else if(val==-1) { val=ch-'A'+1; upd=true; } else if(val!=ch-'A'+1) { val=0; ++t; upd=true; } } return upd; } bool update_back() { bool upd=false; for(int i=0;i<n;++i) for(int j=0;j<n;++j) { int &t=p3[i][j]; char ch=g3[i][j]; if(t==n) continue; int &val=g[t][n-j-1][i]; if(val==0) { ++t; upd=true; } else if(ch=='.') { val=0; ++t; upd=true; } else if(val==-1) { val=ch-'A'+1; upd=true; } else if(val!=ch-'A'+1) { val=0; ++t; upd=true; } } return upd; } bool update_right() { bool upd=false; for(int i=0;i<n;++i) for(int j=0;j<n;++j) { int &t=p4[i][j]; char ch=g4[i][j]; if(t==n) continue; int &val=g[n-j-1][n-t-1][i]; if(val==0) { ++t; upd=true; } else if(ch=='.') { val=0; ++t; upd=true; } else if(val==-1) { val=ch-'A'+1; upd=true; } else if(val!=ch-'A'+1) { val=0; ++t; upd=true; } } return upd; } bool update_top() { bool upd=false; for(int i=0;i<n;++i) for(int j=0;j<n;++j) { int &t=p5[i][j]; char ch=g5[i][j]; if(t==n) continue; int &val=g[i][j][t]; if(val==0) { ++t; upd=true; } else if(ch=='.') { val=0; ++t; upd=true; } else if(val==-1) { val=ch-'A'+1; upd=true; } else if(val!=ch-'A'+1) { val=0; ++t; upd=true; } } return upd; } bool update_bottom() { bool upd=false; for(int i=0;i<n;++i) for(int j=0;j<n;++j) { int &t=p6[i][j]; char ch=g6[i][j]; if(t==n) continue; int &val=g[n-i-1][j][n-t-1]; if(val==0) { ++t; upd=true; } else if(ch=='.') { val=0; ++t; upd=true; } else if(val==-1) { val=ch-'A'+1; upd=true; } else if(val!=ch-'A'+1) { val=0; ++t; upd=true; } } return upd; }4#include<stdio.h> #include<string.h> #include<stdlib.h> char a[41],count[26],current[21],mark[41],remain[81],ans[21],pos[41][41][41]; int i,j,k,n,go,len,step,skips,maxl,remains,start,unique,cases,ok; int main() { for(len=1;len<41;len++) for(step=1;step<41;step++) { memset(mark,0,sizeof(mark)); go=0; mark[0]=1; pos[len][step][0]=0; for(i=1;i<len;i++) { skips=(step-1)%(len-i)+1; while(skips) { go++; if(go>=len) go=0; if(!mark[go]) skips--; } mark[go]=1; pos[len][step][i]=go; } } while(1) { gets(a); for(n=0;a[n];n++); if(n<2) break; cases++; maxl=0; unique=0; memset(ans,0,sizeof(ans)); memset(count,0,sizeof(count)); for(i=0;i<n;i++) count[a[i]-'A']++; for(i=0;i<n;i++) if(count[a[i]-'A']>1) for(j=1;j<n;j++) { memset(current,0,sizeof(current)); memset(mark,0,sizeof(mark)); go=i; for(len=0;len<n/2;len++) { current[len]=a[go]; mark[go]=1; if(len>=maxl&&strcmp(current,ans)) { remains=0; ok=0; for(k=0;k<n;k++) if(!mark[k]) remain[remains++]=a[k]; for(k=0;k<remains;k++) remain[remains+k]=remain[k]; for(start=0;start<remains;start++) if(remain[start]==current[0]) { for(step=j+1;step<=n;step++) { for(k=1;k<=len;k++) if(remain[pos[remains][step][k]+start]!=current[k]) break; if(k>len) { ok=1; if(len>maxl) { maxl=len; unique=1; memcpy(ans,current,sizeof(current)); } else if(unique) { maxl++; unique=0; } else { unique=1; memcpy(ans,current,sizeof(current)); } break; } } if(ok) break; } } skips=j; while(skips) { go++; if(go>=n) go=0; if(!mark[go]) skips--; } } } printf("Code %d: ",cases); puts(unique?ans:"Codeword not unique"); } return 0; }
最后
以上就是霸气钢笔为你收集整理的2004 ACM-ICPC世界总决赛试题分析1-4的全部内容，希望文章能够帮你解决2004 ACM-ICPC世界总决赛试题分析1-4所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复