（未完待续）

毒瘤 构造 题。

题目链接：AtCoder Grand Contest 030 C Coloring Torus。

题目

题目描述

给定一个数字 $K$。

你需要构造一个 $n\times n$ 的矩阵 $A$，需要满足以下条件：

• $n\in[1,500]$。
• $\forall i,j\in[1,n],A _ {i,j}\in[1,K]$ 且为整数。
• $\forall v\in[1,K],\exists i,j\in[1,n],A _ {i,j}=v$。
• 设 $\text{cnt} _ {i,j,v}$ 表示 $A _ {i\bmod n+1,j},A _ {i,j\bmod n+1},A _ {(i-2+n)\bmod n+1,j},A _ {i,(j-2+n)\bmod n+1}$ 四个数中等于 $v$ 的数的个数。那么对于矩阵中任意两个数 $A _ {i,j}$ 和 $A _ {x,y}$，若 $A _ {i,j}=A _ {x,y}$，则需要满足 $\forall v\in[1,K],\text{cnt} _ {i,j,v}=\text{cnt} _ {x,y,v}$。

输出任意一个合法的方案即可。

数据范围

$$1\leq K\leq 10^3$$

题解

分类讨论。

1. $K\leq 500$

直接构造 $K\times K$ 的矩阵，就像这样：

1 1 ... 1 1
2 2 ... 2 2
. . ... . .
K-1 K-1 ... K-1 K-1
K K ... K K

容易发现满足题意

2. $501\leq K\leq 10^3$

考虑斜着构造上面的矩阵。

1 2 ... 499 500
2 3 ... 500 1
. . ... . .
500 1 ... 498 499

然后斜着在对角线上插入数字即可。

总共 $500$ 条对角线，可以插入 $500$ 个数字，再加上原来的 $500$ 个，刚好 $1000$ 个。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register

const int MAXN=500+5;

int n,K;
int a[MAXN][MAXN];

int main(void){
    scanf("%d",&K);
    if(K<=500){
        printf("%d\n",K);
        for(reg int i=1;i<=K;++i)
            for(reg int j=1;j<=K;++j)
                printf("%d%c",i,j==K?'\n':' ');
    }
    else{
        n=500;
        for(reg int i=0;i<n;++i)
            for(reg int j=0;j<n;++j)
                a[i][j]=(i+j)%n+1;
        for(reg int i=n+1;i<=K;++i)
            for(reg int j=0;j<n;++j)
                if((j&1)==0)
                    a[(i-1-j+n)%n][j]=i;
        printf("%d\n",n);
        for(reg int i=0;i<n;++i)
            for(reg int j=0;j<n;++j)
                printf("%d%c",a[i][j],j==n-1?'\n':' ');
    }
    return 0;
}