P15542 [CCC 2026 S3] Common Card Choice 题解

M1rai · 2026-03-08 15:49:01 · 题解

前言

更可爱的阅读体验

场内选手来了。。。这个题的官方 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 遍即可，或者第一个少做几遍第二个多做几遍。