自动搬运

查看原文

来自洛谷，原作者为

	影辰 **

搬运于2025-08-24 22:12:01，当前版本为作者最后更新于2019-10-11 10:30:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

构造

因为题目只要求两位相同，所以可以暴力枚举这两位所有的可能性，方案数为$O(n^2)$。

但是，这么做是显然不优的，因为完全没有用到第三位。

观察题目条件：n为偶数。

就想一想能不能奇数偶数分开来做呢？

注意到一共有三位，总共放到奇偶两个抽屉中，必有一个抽屉有两个位，即存在两位同奇偶。

我们就想办法枚举到这两位同奇偶的数对。

一个有序三元组$(a,b,c)$可以覆盖三个有序的二元组$(a,b,?),(?,b,c),(a,?,c)$

这样的有序二元组取值为$[1,n]$时共有$3n^2$

由于我们分奇偶讨论，所以每种有$\frac{3}{4}n^2$个，总计$\frac{3}{2}n^2$个

如果两两不相同，那么一次性可以排除三个，总共需要排除$\frac{n^2}{2}$次。

可以很容易构造出两两不同的方案，详情见代码。

此时我们感觉答案已经很优了。

证明

设你使用了猜了$t$个答案

所有答案为$(a_i,b_i,c_i)$这样的三元组

按照$a_i$划分为$n$个集合$S_i$,$S_i$中每个三元组的$a$等于$i$

设$s_i=|S_i|$

显然这些答案要求覆盖所有的$n^3$个三元组

一个答案$(a,b,c)$可以覆盖所有形如$(a,b,?),(?,b,c),(a,?,c)$的三元组，不难发现有$3n-2$个

考察每个集合内部重复覆盖的三元组

如：

$(a,b,c)$和$(a,d,e)$共同覆盖了$(a,b,e),(a,d,c)$两个三元组

$(a,b,c)$和$(d,b,e)$共同覆盖了$(d,b,c),(a,b,e)$两个三元组

$(a,b,c)$和$(a,b,d)$共同覆盖了$(a,b,?)$共$n$个三元组（只考虑$n\ge4$的情况）

所以同一集合内的两个三元组至少重复覆盖了2个三元组

按$a$和按$b$分类算两次并不会使答案变得比实际更小。(只有前两项相同的三元组才会重复减去，而需要减去的$n\ge2+2$，所以不会重复)

发现：

$$\sum_{i=1}^{n}{2(_{2}^{s_i})}\ge n*(\frac{t}{n})^2-t $$

所以总共覆盖的三元组至多有

$$(3n-2)t-2*(n*(\frac{t}{n})^2-t)\ge n^3$$

这样就可以解出来$t\ge\frac{n^2}{2}$了

代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
int main(){
	scanf("%d",&n);
	k=n/2;
	printf("%lld\n",1ll*n*n/2);
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++)
			printf("%d %d %d\n",2*i-1,2*j-1,2*((j+i)%k+1)-1);
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++)
			printf("%d %d %d\n",2*i,2*j,2*((i+j)%k+1));
}