P15542 [CCC 2026 S3] Common Card Choice 题解

前言

场内选手来了。。。这个题的官方 spj 是脑残，不过滤行末空格，以及比赛的时候我没读到最后一个 sub 每个猜测选的数必须不交。。。

思路

先看前 $8$ 分，这个 $\gcd$ 的条件是诈骗的，考虑更弱的限制：奇偶性。

如果两个数都是偶数它们的 $\gcd$ 一定 $\geq 2$，于是考虑凑两个偶数出来：

• 如果序列里有两个偶数 $c_i,c_j$，令 $A=\{i\},B=\{j\}$。
• 否则，如果序列里有一个偶数 $x$ 和 $\geq 2$ 个奇数，令前两个奇数的出现位置为 $i,j$，令 $A=\{x\},B=\{i,j\}$。
• 否则，如果序列里有 $\geq 4$ 个奇数，令它们的出现位置为 $a,b,c,d$，令 $A=\{a,b\},B=\{c,d\}$。
• 否则，一定有 $n\leq 3$。暴力枚举子集检查是否有解即可。

再看最后一个 subtask，他这个题意表达有点欠佳，应该提一嘴 $c$ 序列在一开始是确定好的，不会根据输出的答案改变，否则这个题是不可做的（证明略）。

同样从奇偶性考虑，最后的序列里可能奇数更多，也可能偶数更多，也就是说奇数和偶数中一定有一种的出现次数是 $\mathcal{O}(n)$ 的。

• 如果偶数更多，随机 $x$ 次 $(i,j)$，令 $A=\{i\},B=\{j\}$，那么失败的概率最多是 $(\frac{\binom{n/2}{2}}{\binom{n}{2}})^{x}≈4^{-x}$，在奇数偶数一样多时取到。
• 如果奇数更多，随机 $y$ 次 $(i_0,i_1,i_2,i_3)$，令 $A=\{i_0,i_1\},B=\{i_2,i_3\}$，那么失败（这里定义失败为不符合上面的第三个条件，即 $c_{i_0},c_{i_1},c_{i_2},c_{i_3}$ 均为奇数）的概率最多是 $(\frac{\binom{n/2}{4}}{\binom{n}{4}})^{x}≈16^{-x}$，同样在奇偶数一样多时取到。

两个各做 $50$ 遍即可，或者第一个少做几遍第二个多做几遍。