hiho1257 Snake Carpet

題目鏈接：http://hihocoder.com/problemset/problem/1257

題目大意：有n條蛇 編號為1-n 每條蛇的長度跟編號相等 奇數編號的蛇必須拐奇數次（除了第一條）偶數編號的蛇必須拐偶數次（除了第二條）問能不能在這種約束條件下面用蛇構造成一個矩形

思路：構造題 肯定是有一種固定的構造方式，通過推可以發現矩形的長可以成為(n+1)/2 寬是n+((n&1)==0)?

偶數很好做 因為直接在后面加就行了 奇數的時候可以發現通過前一個偶數和前一個奇數來向外面加一層

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int type[600];
void pre(){type[0]=1;type[1]=1;for(int n=2;n<=550;n++){type[n]=type[n-2]+2;}
}
bool judge(int n){if(n<=3){if(n==1){printf("1 1\n");return true;}if(n==2){printf("1 1\n1 2 1 3\n");return true;}if(n==3){printf("2 1\n1 1 1 2\n1 3 2 3 2 2\n");return true;}}return false;
}
void print(int n,int row,int col){if(n&1){for(int i=0;i<(n+1)/2;i++){printf("%d %d ",row+i,col);}for(int i=1;i<=n/2;i++){printf("%d %d%c",row+(n+1)/2-1,col-i,i==n/2?'\n':' ');}}else {int tmp=n/2;for(int i=0;i<tmp;i++){printf("%d %d ",row,col-i);}for(int i=tmp-1;i>=0;i--){printf("%d %d%c",row+1,col-i,i==0?'\n':' ');}}
}
void solve(int n,int row,int col){if(judge(n)) return;if(n&1){solve(n-3,row,col-2);print(n-2,row,col-1);print(n-1,row+(n-3)/2,col-(n+1)/2);print(n,row,col);return;}else {solve(n-1,row,col-2);for(int i=0;i<n/2;i++){printf("%d %d ",row+i,col);}for(int i=n/2-1;i>=0;i--){printf("%d %d%c",row+i,col-1,i==0?'\n':' ');}return ;}return ;
}
int main(){int n;pre();while(scanf("%d",&n)!=EOF){printf("%d %d\n",(n+1)/2,type[n]);solve(n,1,type[n]);}return 0;
}
/*
133
223

13344
22344

22135
44335
44555
偶數:
*****nn
*****nn
*****nn
奇數：
*  *  *  * n-2 n
*  *  *  * n-2 n
*  *  *  * n-2 n
n-1n-1n-1n-2n-2n
n-1n-1n-1n  n  n
*/

?