2015 ACM / ICPC 北京現場賽 I 題
構造
注意一個小坑，每條蛇的輸出是要從頭到尾輸出的。
還要注意的是，不能開數組去模擬構造過程，然后輸出，那樣會TLE的。
?
#include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> using namespace std;const int maxn=500+10; vector<int> 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<G[i].size();j++){printf("%d",G[i][j]);if(j<G[i].size()-1) printf(" ");else printf("\n");}} }int main() {f();while(~scanf("%d",&n)){init();//初始化odd();//左圖even();//右圖/*for(int i=1;i<=R1;i++){for(int j=1;j<=C1+C2;j++){printf("%5d",ans[i][j]);}printf("\n");}*/printf("%d %d\n",R1,C1+C2);print();//輸出 }return 0; }
?
