CF1404D - Game of Pairs

题目大意

两个人Van游戏，

第一个人对于 \(1,2,\cdots,2n\) 分成 \(n\) 组

第二个人尝试从每组中选一个数，使得选出数的和是 \(2n\) 的倍数

你选一个人Van，然后赢了交互器

分析

考虑从一个 \(\mathbb{Naive}\) 的构造开始：

分成 \(n\) 组，每组都是 \((i,n+i)\)

为什么这么构造？因为每组两个数 \(\mod n\) 都相同

那么最终选出的和 \(Sum\mod n=\frac{n(n+1)}{2}\)

观察到，在 \(n\) 为偶数时， \(Sum \mod n=\frac{n}{2}\ne 0\) ，此时必然无解

然后我没过脑子随机化艹出了n为奇数的方案，但是没事下面有确定解法

而 \(n\) 为奇数时，我们只需要类似找到一组 \(\mod n=0,1,2,\cdots ,n-1\) 的方案

此时必然满足 \(Sum\mod n=0\)

这只需要对于给出的每组 \((a_i,b_i)\) ，对于 \(a_i\mod n,b_i\mod n\) 连一条边

然后在最终的置换环上进行决策即可

然而我们需要 \(Sum\mod 2n=0\)

又 \(\frac{(2n+1)2n}{2}=n(2n+1)\mod 2n=n\) ，故如果找到的 \(Sum\mod 2n=n\) ，取当前方案的补集即可