题目链接：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[];
void pre(){
type[]=;
type[]=;
for(int n=;n<=;n++){
type[n]=type[n-]+;
}
}
bool judge(int n){
if(n<=){
if(n==){
printf("1 1\n");
return true;
}
if(n==){
printf("1 1\n1 2 1 3\n");
return true;
}
if(n==){
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&){
for(int i=;i<(n+)/;i++){
printf("%d %d ",row+i,col);
}
for(int i=;i<=n/;i++){
printf("%d %d%c",row+(n+)/-,col-i,i==n/?'\n':' ');
}
}
else {
int tmp=n/;
for(int i=;i<tmp;i++){
printf("%d %d ",row,col-i);
}
for(int i=tmp-;i>=;i--){
printf("%d %d%c",row+,col-i,i==?'\n':' ');
}
}
}
void solve(int n,int row,int col){
if(judge(n)) return;
if(n&){
solve(n-,row,col-);
print(n-,row,col-);
print(n-,row+(n-)/,col-(n+)/);
print(n,row,col);
return;
}
else {
solve(n-,row,col-);
for(int i=;i<n/;i++){
printf("%d %d ",row+i,col);
}
for(int i=n/-;i>=;i--){
printf("%d %d%c",row+i,col-,i==?'\n':' ');
}
return ;
}
return ;
}
int main(){
int n;
pre();
while(scanf("%d",&n)!=EOF){
printf("%d %d\n",(n+)/,type[n]);
solve(n,,type[n]);
}
return ;
}
/*
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
*/