2015年ACM/ICPC北京赛区 I题(构造)
题意:
给你一个数n(n<=500),让你用长度分别为1,2,...,n的折线段填满w*h的矩阵,其中w*h==n*(n+1)/2。
要求奇数长度的折线有奇数个折点,偶数长度的折线有偶数个折点,第一、二条线段除外。
比赛的时候想了一种不太好想的思路,结果没调出来。赛后调出来了,代码很短,效率也很好。
就是这样构造:
1
122(特判)
12
32
33
44
44
12
32
33
144
344
332
552
555
等等。
看不懂的话,直接看代码吧:
#include<bits/stdc++.h>
using namespace std;
int k,m,n,nn,t;
int nex[]={1,2,3,0};
int dxy[]={0,-1,0,1,-1,0,-1,0};
int main()
{
while(scanf("%d",&nn)!=EOF)
{
if(nn==2) {printf("1 3\n1 1\n1 2 1 3\n");continue;}
int n=(nn+1)*nn/2;
int w=(nn+1)/2;
int h=n/w;
int x=(nn&1)?1:3;
int y=1,k=1;
printf("%d %d\n",h,w);
for(int i=1;i<=nn;)
{
if(i&1)
{
t=0;k=0;
while(k+1<i)
{
k++;
printf("%d %d ",x,y);
x+=dxy[t];
y+=dxy[t+4];
t=nex[t];
}
printf("%d %d\n",x,y);
x=h-i;
i++;
y=w-(i/2)+1;
}
else
{
int yy=y;
while(y<=w) printf("%d %d ",x,y),y++;
y--;x--;
while(y>yy) printf("%d %d ",x,y),y--;
printf("%d %d\n",x,y);
i++;
x=(nn&1)?i:i+2;
y=(i+1)/2;
}
}
}
return 0;
}