2015 ACM / ICPC 北京现场赛 I 题
构造
注意一个小坑，每条蛇的输出是要从头到尾输出的。
还要注意的是，不能开数组去模拟构造过程，然后输出，那样会TLE的。
#include#include #include #include #include using namespace std;const int maxn=500+10;vector G[maxn];int Find[maxn][3];int n;int R1,C1,R2,C2;int tot;int ans[maxn][maxn];void f(){ Find[2][1]=1; Find[2][2]=2; Find[4][2]=2; for(int i=4;i<=500;i=i+2) { if(i%4==0) Find[i][1]=Find[i-2][1]+2; else Find[i][1]=Find[i-2][1]; } for(int i=4;i<=500;i=i+2) { if(i%4==2) Find[i][2]=Find[i-2][2]+2; else Find[i][2]=Find[i-2][2]; }}void init(){ //清空 for(int i=0;i<=n;i++) G[i].clear(); tot=0; //确定左图的大小 R1=C1=(n+1)/2; //确定右图的大小 if(n%2==1){ R2=Find[n-1][1]; C2=Find[n-1][2]; } else { R2=Find[n][1]; C2=Find[n][2]; }}void odd(){ for(int i=1;i<=n;i=i+2) { tot++; for(int j=1;j<=tot;j++) { G[i].push_back(tot); G[i].push_back(j); ans[tot][j]=i; } for(int j=tot-1;j>=1;j--) { G[i].push_back(j); G[i].push_back(tot); ans[j][tot]=i; } }}void even(){ if(R1==R2) { int NowR=1; int NowC=0; for(int i=2;i<=n;i=i+2) { //横着画 if(i%4==0) { for(int j=1;j<=i/2;j++) { G[i].push_back(NowR+1); G[i].push_back(j+C1); ans[NowR+1][j+C1]=i; } for(int j=i/2;j>=1;j--) { G[i].push_back(NowR+2); G[i].push_back(j+C1); ans[NowR+2][j+C1]=i; } NowR=NowR+2; } //竖着画 else { for(int j=1;j<=i/2;j++) { G[i].push_back(j); G[i].push_back(NowC+1+C1); ans[j][NowC+1+C1]=i; } for(int j=i/2;j>=1;j--) { G[i].push_back(j); G[i].push_back(NowC+2+C1); ans[j][NowC+2+C1]=i; } NowC=NowC+2; } } } else if(R1==C2) { swap(R2,C2); int NowR=R2+1; int NowC=1; for(int i=2;i<=n;i=i+2) { //竖着画 if(i%4==0) { for(int j=R2;j>=R2-i/2+1;j--) { G[i].push_back(j); G[i].push_back(NowC+1+C1); ans[j][NowC+1+C1]=i; } for(int j=R2-i/2+1;j<=R2;j++) { G[i].push_back(j); G[i].push_back(NowC+2+C1); ans[j][NowC+2+C1]=i; } NowC=NowC+2; } //横着画 else { for(int j=1;j<=i/2;j++) { G[i].push_back(NowR-1); G[i].push_back(j+C1); ans[NowR-1][j+C1]=i; } for(int j=i/2;j>=1;j--) { G[i].push_back(NowR-2); G[i].push_back(j+C1); ans[NowR-2][j+C1]=i; } NowR=NowR-2; } } }}void print(){ for(int i=1;i<=n;i++) { for(int j=0;j