题解：CF2149G Buratsuta 3

思路

考虑随机化，如果您的刷题量够多，那么你一定做过 P3567 这题和那题的思路差不多，这题唯一的限制是那题只要输出一个就行，这个是你要输出所有情况，那么我们的思路其实很好想还是那题的代码我们只需要在随机下标时，找到合适的答案并给它加入到我们的一个 set 里，来记录答案，最后遍历一下。

思路很简单，但是这题读者在看完之后肯定有一个疑问：这样随机的答案次数太多不就 TLE 了？

首先先说一下结论，我们的答案大概率不会超过3个，下面是证明：

设区间长度为

len

，阈值

T = ⌊len/3⌋

，我们要找出现次数 严格大于 T 的元素。

假设有

k

个不同的元素满足条件，每个的出现次数至少为

T+1

，那么它们的总出现次数至少为

k(T+1)

，这个值必须小于等于

len

：

k(T+1) \le len

代入

T = ⌊len/3⌋

分析：

当 $len = 3m$ 时， $T = m$ ， $k(m+1) \le 3m\Rightarrow k \le 3m/(m+1) < 3\Rightarrow k \le 2$
当 $len = 3m+1$ 时， $T = m$ ， $k(m+1) \le 3m+1\Rightarrow k \le (3m+1)/(m+1) < 3\Rightarrow k \le 2$
当 $len = 3m+2$ 时， $T = m$ ， $k(m+1) \le 3m+2\Rightarrow k \le (3m+2)/(m+1) < 3\Rightarrow k \le 2$

因此，满足条件的元素最多只有 2 个。

如果一个值在区间内出现次数大于

T

，那么它在区间中的占比大于

\frac{1}{3}

，随机选取一个位置选到该值的概率也大于

\frac{1}{3}

。

如果有 2 个这样的值，随机选到其中至少一个的概率大于

\frac{2}{3}

。

随机选取

S = 30

次，漏掉所有满足条件的值的概率小于

(1/3)^{30} \approx 4.2\times10^{-15}

，这个概率要是漏答案基本比中彩票的概率还低。