题目描述
你有一个 \(2n×m\) 的网格，你需要给每个格子染上 \(n\) 种颜色之一，且对于每一个由格子组成的且边界平行于网格边界且每边边长大于等于 \(2\) 的矩形，它的四个角的格子的颜色不完全相同。
输入格式
一行两个数 \(n\) 和 \(m\) 表示矩形的大小。
输出格式
输出一个符合条件的 \(2n×m\) 的矩形，或者一个数 \(−1\) 表示无解。
样例
见附加文件
数据范围
时间限制：\(1s\)
空间限制：\(256MiB\)
对于 \(20%\) 的数据，满足 \(n≤4\)，\(m≤12\)。
对于 \(60%\) 的数据，满足 \(n≤50\)，\(m≤100\)。
对于 \(100%\) 的数据，满足 \(n≤100\)，\(m≤10000\)。
看不懂的题解
我们找出所有的三元组 \((x, y, c)\) 代表某一列中 \(x\) 行和 \(y\) 行颜色都是 \(c\)。
首先三元组的种数只有 \(2n \times (2n - 1) / 2 \times n = n^2 \times (2n - 1)\) 种。 (一列的格子两两组合在乘上颜色个数)
我们接下来证明一列至少会占用 \(n\) 种：
\(\sum c_i = 2n\)
\[\begin{aligned} \sum \frac{c_i(c_i - 1)}{2} &= \frac{\sum c_i^2}{2} - \frac{\sum c_i}{2}\\ &\ge \frac{(\sum c_i)^2}{2n} - n\ \text{(Cauchy–Schwarz inequality)}\\ &= n \end{aligned} \](通俗易懂的解释就是一列有\(2n\)个格一个三元组占两个格所以一列至少会占\(n\)个三元组 ！：而且在一列种每一个三元组的颜色必须互不相同因为如果相同了就会出现\(x\)个三元组会占多于\(x\)组匹配（如两组相同颜色的三元组会占6种）)
所以 \(m > n \times (2n - 1)\) 时必然无解。(一列至少占\(n\)种共有\(n^2 \times (2n - 1)\)种 所以最多\(n\times (2n - 1)\)列)
下面给出 \(m = n \times (2n - 1)\) 的构造。
不妨把一对颜色相同的点看作一个匹配，那么如果我们能找出 \(K_{2n}\) 的 \(2n - 1\) 个边集不相交的匹配，每一组匹配都可以循环着染色染 \(n\) 列。(如果不看颜色共有\(n \times (2n - 1)\)种 一列占\(n\)种所以可以构造\(2n-1\)列完全不同的匹配然后再对其进行染色（注意：一列中每个三元组的颜色互不相同）即循环染色这样不会冲突)
（以下点的下标从 \(0\) 开始）构造匹配是容易的：对 \(i\in [0, 2n - 2]\) 我们找出满足 \(x + y \equiv i \pmod{(2n - 1)}\) 的每一对 \((x, y)\) 根据同余的性质一定有 \(n - 1\) 对，而 \(i \times 2^{-1}\) 一定没有匹配，和 \(2n - 1\) 匹配即可。这样对于每一个 \(i\) 我们都找到了一组匹配，且它们边集不交。(手模一下可以发现每一个\(i\)可以构造出一列唯一的匹配可得到通式\((i-j+2*n-1)%(2*n-1)\) \(:\) 第\(j\)个格与第(i-j+2n-1)%(2n-1)个格颜色相同，特殊处理：而 \(i \times 2^{-1}\) 一定没有匹配，和 \(2n - 1\) 匹配即可。)
std
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[222];
int ans[222][22222];
int main()
{
scanf("%d%d",&n,&m);
if(m > n*(2*n-1))return printf("-1"),0;
int cnt = 0;
for(int i = 0;i <= 2*n-2;i++)
{
for(int col = 1;col <= n;col++)
{
memset(a,0,sizeof a);
int cc = col;
for(int j = 0;j <= 2*n-2;j++)
{
if(a[j])continue;
if(j != (i-j+2*n-1)%(2*n-1))a[j] = a[(i-j+2*n-1)%(2*n-1)] = cc%n==0?n:cc%n ,cc++;
else a[j] = a[2*n-1] = cc%n==0?n:cc%n ,cc++;
}
cnt++;
for(int j = 0;j <= 2*n-1;j++)
{
ans[j][cnt] = a[j];
}
if(cnt == m)break;
}
if(cnt == m)break;
}
for(int i = 0;i <= 2*n-1;i++)
{
for(int j = 1;j <= m;j++)
printf("%d ",ans[i][j]);
putchar('\n');
}
return 0;
}