AtCoder Grand Contest 030 (AGC030) C - Coloring Torus 构造

时间:2021-09-21 12:26:08

原文链接https://www.cnblogs.com/zhouzhendong/p/AGC030C.html

题解

  才发现当时是被题意杀了。

  当时理解的题意是“对于任意的 (i,j) ,颜色 i 和 颜色 j 的相邻格子对数相同”。好像当时看了样例都没有发现被题意杀……

  回归正题。

  如果要构造 n = k 的,那么直接 构造一个第 i 行为 i 的就好了。

  那么 n<k<=2n 呢?

  我们考虑斜着的列。

  如果第 i 个斜列放 i ,那么也可以达到 n = k 的目的。

  如果第 i 个斜列间隔放两种数,那么仍然可以满足条件。这时候就可以做到 $k\in [n,2n]$ 了。

  放个图便于理解。(下图蓝线穿过的列是特殊的列)

AtCoder Grand Contest 030 (AGC030) C - Coloring Torus 构造

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read(){
LL x=0;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
const int N=505;
int n,k;
int g[N][N];
int main(){
k=read();
n=min(k,500);
for (int i=1;i<=n;i++){
int x=1,y=i;
for (int j=1;j<=n;j++){
g[x][y]=i;
x=x%n+1,y=y%n+1;
}
}
for (int i=n+1;i<=k;i++){
int x=1,y=i-n;
for (int j=1;j<=n;j++){
if (j&1)
g[x][y]=i;
x=x%n+1,y=y%n+1;
}
}
printf("%d\n",n);
for (int i=1;i<=n;i++,puts(""))
for (int j=1;j<=n;j++)
printf("%d ",g[i][j]);
return 0;
}