hihoCoder 1257 Snake Carpet(很简单的构造方法)

时间:2022-12-24 14:59:34

2015 ACM / ICPC 北京现场赛 I 题

构造

注意一个小坑,每条蛇的输出是要从头到尾输出的。

还要注意的是,不能开数组去模拟构造过程,然后输出,那样会TLE的。

hihoCoder 1257 Snake Carpet(很简单的构造方法)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std; const int maxn=+;
vector<int> G[maxn];
int Find[maxn][];
int n;
int R1,C1,R2,C2;
int tot; int ans[maxn][maxn]; void f()
{
Find[][]=; Find[][]=; Find[][]=;
for(int i=;i<=;i=i+)
{
if(i%==) Find[i][]=Find[i-][]+;
else Find[i][]=Find[i-][];
} for(int i=;i<=;i=i+)
{
if(i%==) Find[i][]=Find[i-][]+;
else Find[i][]=Find[i-][];
}
} void init()
{
//清空
for(int i=;i<=n;i++) G[i].clear();
tot=; //确定左图的大小
R1=C1=(n+)/; //确定右图的大小
if(n%==){
R2=Find[n-][];
C2=Find[n-][];
}
else {
R2=Find[n][];
C2=Find[n][];
}
} void odd()
{
for(int i=;i<=n;i=i+)
{
tot++;
for(int j=;j<=tot;j++)
{
G[i].push_back(tot);
G[i].push_back(j); ans[tot][j]=i;
}
for(int j=tot-;j>=;j--)
{
G[i].push_back(j);
G[i].push_back(tot); ans[j][tot]=i;
}
}
} void even()
{
if(R1==R2)
{
int NowR=;
int NowC=; for(int i=;i<=n;i=i+)
{ //横着画
if(i%==)
{
for(int j=;j<=i/;j++)
{
G[i].push_back(NowR+);
G[i].push_back(j+C1); ans[NowR+][j+C1]=i;
} for(int j=i/;j>=;j--)
{
G[i].push_back(NowR+);
G[i].push_back(j+C1); ans[NowR+][j+C1]=i;
}
NowR=NowR+;
} //竖着画
else
{
for(int j=;j<=i/;j++)
{
G[i].push_back(j);
G[i].push_back(NowC++C1); ans[j][NowC++C1]=i;
} for(int j=i/;j>=;j--)
{
G[i].push_back(j);
G[i].push_back(NowC++C1); ans[j][NowC++C1]=i;
}
NowC=NowC+;
}
}
}
else if(R1==C2)
{
swap(R2,C2); int NowR=R2+;
int NowC=; for(int i=;i<=n;i=i+)
{
//竖着画 if(i%==)
{
for(int j=R2;j>=R2-i/+;j--)
{
G[i].push_back(j);
G[i].push_back(NowC++C1); ans[j][NowC++C1]=i;
} for(int j=R2-i/+;j<=R2;j++)
{
G[i].push_back(j);
G[i].push_back(NowC++C1); ans[j][NowC++C1]=i;
}
NowC=NowC+;
} //横着画
else
{
for(int j=;j<=i/;j++)
{
G[i].push_back(NowR-);
G[i].push_back(j+C1); ans[NowR-][j+C1]=i;
} for(int j=i/;j>=;j--)
{
G[i].push_back(NowR-);
G[i].push_back(j+C1); ans[NowR-][j+C1]=i;
}
NowR=NowR-;
}
}
}
} void print()
{
for(int i=;i<=n;i++)
{
for(int j=;j<G[i].size();j++)
{
printf("%d",G[i][j]);
if(j<G[i].size()-) 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 ;
}