随机化

· · 个人记录

这不是纯骗分来的（开玩笑

异或哈希

本质就是为每个数赋一个随机的权值 w_i ，然后通过将每个权值用异或或者加之类的方式得到一个数，来判断集合是否相等、是否为空、是否为奇数之类的问题

看题吧：

ABC367F

模板题（？

每个区间算一下权值总和即可，具体可以用前缀和维护

[COTS 2023] 下 Niz

这道题前面的推理与随机化关系不大，遂跳过 （绝对不是我没听懂）

如何快速判断一个区间是否是排列呢，记录一个 s_n=\oplus_{i=1}^nw_i，然后判断一下 \oplus_{i=l}^rw_{a_i}=s_{r-l+1} 就行了

[UR14] 最强跳蚤

注意到完全平方数有一性质是所有质因子次数为偶数，于是我们对每一个质数赋一个权值，然后计算总异或和就好了，具体的记录每个点到根节点路径上的异或和 s_i，那么 u 到 v 的路径总和就是 s_u \oplus s_v

随机重排

函数是 random_shuffle，具体性质有如下几个重要的：

  1. 前缀最大值个数期望 O(\log n)
  2. 由 \{1,-1\} 构成的序列前缀和绝对值最大值期望 O(\sqrt{n})
  3. LIS期望长度 O(\sqrt{n})

于是看题：

平面最近点对（加强版）

我们充分发挥人类智慧

既然是随机化专题，于是我们先对这 n 个点随机重排一下

考虑已经判完了前 i 个点，此时最近距离是 d，我们将平面分成 d \times d 的区域，那么每个区域只会有 O(1) 个点，所以对于第 i + 1 个点，我们只检查这个点所在区域周围一圈的区域内是否存在比 d 小的距离即可，因为这个范围外的点垂直距离一定不小于 \sqrt{2}d

这样做的复杂度为什么对，我们注意到重排后，第 i 个点只有 \frac{1}{i} 的概率更新答案，所以期望是 O(n) 的

HDU6804 Contest of Rope Pulling

先鸽着

THE END