题目描述

你有一个 \(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;
}

原文地址:http://www.cnblogs.com/AC7-/p/16871934.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性