当前位置：首页 > news >正文

2.26 随机化

news 2026/5/11 19:56:22

随机化的作用：

玄学的人类智慧。
哈希成一个大数，减少冲突，~~冲突了可以去买彩票了~~。
Xor Hashing，第二类的变种。
配合算法（DP、贪心等）和数据结构。

P13667 [GCPC 2023] Balloon Darts

人类智慧题。

考虑鸽巢原理，\(4\) 个点必然有至少 \(2\) 给点在一条直线上，枚举这 \(2\) 个点并标记直线上的点。

剩下还有 \(2\) 条边，\(3\) 个点里面必然有至少 \(2\) 个点在一条直线上，枚举这 \(2\) 个点，然后判断剩下的能否构成一条直线。

大概 \(\mathcal O(n^2)\)？但是实际非 impossible 跑不满。

还有一种就是直接随机点，玄学。。。

P13810 [CERC 2022] Differences

哈希成大数类型题。

直接做有点难，但是与一个字符串有 \(k\) 个位置不同，有 \(n - 1\) 个，有 \((n - 1)k\) 个不同，哎，要是给这些字符串随机赋一个权值 \(key\)，那么就会产生 \(k\sum_{j \neq i} key_j\) 的贡献，加上自己 \(k\times key_i\) 正好是 \(k\times \sum\limits_{i = 1}^n key_i\)。

随机化是为了避免类似于 \(3 ,3 ,2 ,4\) 之类的判定为合法。

于是只要预处理每一位会产生的贡献即可，时间复杂度为 \(\mathcal O(\lvert \sum \rvert nm)\)，\(\lvert sum\rvert\) 为字符集大小，等于 \(4\)。

CF2014H Robin Hood Archery

合集的前面写了，这里不写了。

CF1175F The Number of Subpermutations

上一题很容易想到 Hash。

这一题考虑有贡献的排列本质就是最大值为 \(r - l + 1\)，区间长度为 \(r - l + 1\)，区间内的数不重复。

如何判断区间内的数不重复？给每个数哈希映射成一个大数求区间和即可。

这样时间复杂度为 \(\mathcal O(n^2)\)。

但是考虑到每个排列都有 \(1\)，我们从 \(1\) 开始向左/向右扩展，以向右为例，假设当前位置 \(j\)，所有扩展到的数的最大值 \(mx\)，那么 \([j - mx + 1 ,j]\) 就有可能成为我们的答案，此时求区间和判断一下即可，注意左端点也要合法。向左同理，翻转序列，重新求前缀和即可。时间复杂度为 \(\mathcal O(n)\)。

但是 TJ 区这种做法都是清一色的 xor，把加法改成 xor 就叫 xor hashing 了，有没有 add hashing 啊：（

CF840D Destiny

随机化优化数据结构！

考虑如果我们确定了区间内每个数的个数会怎么样。

暴力就是每个数都判一遍。

但考虑符合要求的数在区间的出现次数至少为 \(1 + \lfloor \frac{r - l + 1}{k}\rfloor\)，一次随机到的概率为 \(\frac{1 + \lfloor \frac{r - l + 1}{k}\rfloor }{r - l + 1}\) 就当它 \(\frac{1}{k}\)，那么随机 \(N\) 次随即不到的概率为 \(\left(\frac{k - 1}{k}\right)^N\)，只要 \(N\ge c\) 一个值这个概率就几乎为 \(0\)。

现在我们只要知道区间每个数出现的次数即可，配合莫队就行，复杂度 \(\mathcal O(n\sqrt m + mc)\)。

还有一种主席树的做法，在主席树上二分；还有线段树维护摩尔投票的（这个代码稍难实现），可以见我以前的博客。

CF1305F Kuroni and the Punishment

随机化优化暴力。

首先显然答案上界为 \(n\)，或者序列中的奇数个数 \(odd\)，我们可以把它们改成偶数这样 \(2\mid \gcd\)。

现在好像没方向，但是我们发现这样至少 \(\lceil \frac{odd}{2}\rceil\) 个数操作一次或者不操作，证明最坏情况其他都是 \(2\) 次，设操作 \(2\) 次的有 \(k\) 个，那么要满足 \(k\le \lfloor \frac{odd}{2}\rfloor\)，那么 \(others = n - k = odd - \lfloor \frac{odd}{2} \rfloor = \lceil \frac{odd}{2}\rceil\)。

接下来我们考虑暴力，把每个数都进行 \(0\sim 1\) 次操作，得到的值分解质因数，因为 \(\gcd\) 的因数必然是某个质因子，取最小质因子移动次数更少，肯定更优（当然 \(\gcd\) 可能是合数但是我们完全可以操作成质数，或者钦定它的因子为 \(\gcd\)）。

由 \(2\times 3 \times 5\times 7 \times 11 \times 13 \times 17\times 19 \times 23\times 29 \times 31\times 37 \ge 10^{12} + n_{max}\)，一个数最多 \(11\) 个不同的质因子

时间复杂度为 \(\mathcal O(n\sqrt{V} + kn^2)\)，\(k = 11\)。

但是我们有 \(\frac{1}{2}\) 的概率随机到一个只操作 \(0\sim 1\) 次的数，如果随机 \(N\) 次不正确只有当这些数都是变化 \(\ge 2\) 次时，如果有至少一个它的因子必然有一个是 \(\gcd\)，因此错误率是 \(\frac{1}{2^N}\)，\(N \ge c\) 一个保证极小概率一次中彩票值即可。

剩下的就是计算 \(x\) 至少经过多少步变为 \(g\) 的倍数，这个好算。

时间复杂度为 \(\mathcal O(N\sqrt{V} + kNn)\)。

TJ 区还有每个数肯定变为 \([a_i - odd ,a_i + odd]\)，这个值域不大，先把 \(\sqrt{V}\) 以内的质数线性筛出来然后再筛这个范围的，把可能的质数 \(g\) 放进来算每个 \(x\) 至少经过多少步变为 \(g\) 的倍数，这样数据基本上在小的或者大的找到答案，不会找太多次。