【AtCoder Grand Contest 030 C】Coloring Torus | Mrsrz's blog

构造。

题目大意：

有 $n\times n$ 的网格，和 $k$ 种颜色，要求给每个格子染上 $1\sim k$ 中的一种，满足：

1. 所有 $1\sim k$ 均出现。
2. 对于颜色 $i$ 和 $j$，所有颜色 $i$ 的格子旁边（四连通，$n$ 与 $1$ 连通）的颜色 $j$ 格子数量相等。

给定 $k$，求一个满足条件的 $n$，并给出 $n\times n$ 矩阵的填色方案。

$1\le k\le 1000,1\le n\le 500$。

题解：

首先，$n=k$ 的情况非常好构造，每个颜色单独一行即可。

考虑最坏情况下，$k=2n$，所以我们构造出来的情况中，$n=\frac k 2$。

当 $n$ 为偶数时，可以采取如下方案：

第 $1$ 行依次填 $1,2,3,\ldots,n$；第 $2$ 行依次填 $n+2,n+3,n+4,\ldots,2n,n+1$。第 $i(i>2)$ 行为第 $i-2$ 行把最前面两种颜色挪到最后面。

容易发现满足条件。而且，按照这样构造，$i$ 和 $i+n$ 处于同一斜线上。

这里的 $k$ 满足 $k\bmod 4=0$。对于 $k\bmod 4\neq 0$ 的情况，我们只需要每次把最大的颜色减去 $n$ 即可。由于 $i+n$ 和 $i$ 处于同一斜线上，因此把 $i+n$ 变为 $i$，其四周的颜色不变。

Code：

#include<cstdio>
#include<vector>
int k,n;
std::vector<int>A[555];
int main(){
    scanf("%d",&k);
    if(k<=500){
        printf("%d\n",k);
        for(int i=1;i<=k;++i)
        for(int j=1;j<=k;++j)
        printf("%d%c",i," \n"[j==k]);
    }else{
        n=k+1>>1;
        if(n&1)++n;
        for(int i=1;i<=n;++i)
        A[0].push_back(i);
        for(int i=n+2;i<=2*n;++i)
        A[1].push_back(i);
        A[1].push_back(n+1);
        for(int i=2;i<n;++i){
            A[i]=A[i-2];
            A[i].push_back(A[i][0]),A[i].push_back(A[i][1]);
            A[i].erase(A[i].begin());
            A[i].erase(A[i].begin());
        }
        for(int i=0;i<n*2-k;++i){
            for(int x=0;x<n;++x)
            for(int y=0;y<n;++y)
            if(A[x][y]==2*n-i)A[x][y]-=n;
        }
        printf("%d\n",n);
        for(int i=0;i<n;++i){
            for(int j:A[i])printf("%d ",j);
            putchar('\n');
        }
    }
    return 0;
}