NFLS 随机化 12.21

简单记录一下，因为题目不怎么难。

然而有些题不是用随机化过的，暂时不管了就当杂题记录了（）。

当然部分题目随机化只是一种骗分的手段，比如下面的一题。

还有一些是随机使得减少一些限制，使得存在算出来正确的概率。即使一次的错误率是 99%，随几百次的错误率也很小。

A. NOIP2021 方差

弥补了一下初中的遗憾。

发现操作一次相当于交换差分数组的相邻两项。再分析一下差分是下凸的更优。

于是对差分数组排完序以后随一个值表示放在左边还是右边。然后退火一下就行了。原题就过了。

不过如果其差分数组一堆为 $1$ 就很难过。每次枚举的无用的状态太多。还是当做没有思路的骗分手段吧。

B. COCI 2022/2023 Contest #2 Lampice

成对出现考虑哈希判重。给一对数赋一个 $2^{64}$ 的哈希值，如果在一个矩形则异或一下就消掉了。判断一个矩形是否合法即里面异或完是否为 $0$。

枚举上边界和下边界，然后排序判断多少个相等的即可。复杂度 $O(n^2m\log m)$。

C. CF1310D Tourism

没有奇环容易联想到二分图。

考虑给每个点随机赋上一个颜色。每次只向颜色不同的点转移。简单 dp 即可。每次复杂度 $O(n^2k)$。

分析下正确率，算到答案序列的概率是 $\dfrac{1}{2^{k-1}}$。多随几次就好了。

D. hdu Andy and Maze

和上面一样的套路。为了保证不出现一样的，给每个点赋上一个颜色然后跑状压最短路（其实转移是 DAG）。每次复杂度 $O(2^km)$。

分析下正确率，答案的路径的赋颜色的总个数是 $O(k^k)$，而每次算到了 $O(k!)$ 种情况，也就是每次的正确率 $O(\dfrac{k!}{k^k})$，看似很低，跑 200 遍就错误率很小了。

E. THUPC2021初赛 混乱邪恶

显然有一个 $O(np^4/w)$ 的背包+bitset 优化做法。但是还是差一点。

考虑非常经典的随机游走问题，它告诉我们在二维平面上每次随机选一个方向走 $1$ 的单位长度，走 $n$ 步期望的距离不会超过 $O(\sqrt n)$。

这题也是在游走，但是差个随机。考虑把序列随机一下即可。

F. CF1114E Arithmetic Progression

先考虑 30 次询问把最大值搞出来。

然后随 30 个序列中的值，取所有相邻两项的 $\gcd$。

正确率我也不是很懂。看题解等价于选 $30$ 个数字 $\gcd$ 不为 $1$ 的概率。仔细一想有点道理。错误率就是 $\sum \dfrac{1}{i^{30}}$，左右。反正感觉很正确啊。

G. CF1305F Kuroni and the Punishment

暑假模拟赛的题目。https://wgyhm.top/2023/07/13/7-12-%E6%A8%A1%E6%8B%9F%E8%B5%9B/

H. CF364D Ghd

随一个数，那么有 $1/2$ 的概率它的因数是最后的答案。

然后枚举因数，加点剪枝就很好过了。随个 $10$ 次差不多了。

I. CF1728E Red-Black Pepper

先考虑预处理出 $f_i$ 表示选 $i$ 个红辣椒的最大值。预处理的方式就是先全选黑辣椒，然后按照 $a_i-b_i$ 排序，依次加上去。

根据这样的方式预处理容易发现 $f_i$ 是有凸性的。

然后 exgcd 求出解之后三分即可。

所以跟随机化什么关系呢？

J. ABC314Ex Disk and Segments

直接退火，还有学习了一发求点到线段距离的姿势。

点 $O$ 到直线距离，上面找两个点 $AB$，然后用叉积算 $S_{OAB}$ 的面积，和 $AB$ 除一下即可。

如果是线段的话，用 $\cos$ 判断角度和线段的端点是不是钝角。$\cos$ 的正负等价于点积的正负。是钝角则直接求和线段的那个端点的距离即可。

L. ABC326G Unlock Achievement

如果想到最大权闭合子图模型，发现是个板题。

所以跟随机化什么关系呢？