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

异或哈希

本质就是为每个数赋一个随机的权值

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，具体性质有如下几个重要的：

前缀最大值个数期望 $O(\log n)$
由 $\{1,-1\}$ 构成的序列前缀和绝对值最大值期望 $O(\sqrt{n})$
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

先鸽着

随机化

文章操作