(未完待续)
毒瘤 构造 题。
题目链接: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$$
题解
分类讨论。
- $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
容易发现满足题意
- $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;
}
近期评论