题解 P5562 【[Celeste-B]Center of the Earth】
影辰
·
·
题解
构造
因为题目只要求两位相同，所以可以暴力枚举这两位所有的可能性，方案数为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)$和$(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}$了
## 代码
```cpp
#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));
}
```