Miracle_Creator的随机化算法题单

>效率高的算法，大多跟随机化脱不了干系——沃兹·基硕德 此题单适用人群：提高~省选。 前置知识：如何生成给定范围内的随机整数，浮点数，知道如何随机打乱一个序列，最好对随机数有充分的了解。 让我们开启我们的随机化算法之旅吧。 $1,$随机化贪心 适用范围：序列，坐标最优化问题。 在很多时候，贪心其实并不正确（所以才有了dp），随机化贪心的思想是确定一种初始的贪心方案（按这种初始方案贪心实际上并不保证正确），然后每次都将这个贪心方案做一下改动（这个改动是基于随机的），每次将方案做改动之后贪心一下记录结果，最后直接将贪心了这么多次的最优解当做答案即可，贪心的次数视数据而定，必要的时候可以加上 ```cpp while ((double)clock() / CLOCKS_PER_SEC <= 0.95) ``` 来控制时间，保证在不超时的情况下，随机化贪心跑尽可能多的次数。 如何随机调整贪心方案？ 对于序列问题，可以随机交换序列中的两个数或使用```random_shuffle```来随机打乱原序列。 对于坐标问题，可以每次生成一个新的坐标，或在原坐标的基础上进行些许改动。 例题： [P2210 Haywire](https://www.luogu.com.cn/problem/P2210)裸的随机化贪心，随机打乱位置序列贪心即可 [P2503 [HAOI2006]均分数据](https://www.luogu.com.cn/problem/P2503)贪心方案比较难想，随机化部分很简单 [P3878 [TJOI2010]分金币](https://www.luogu.com.cn/problem/P3878)随机交换序列中的两个数贪心即可。 [P3959 宝藏](https://www.luogu.com.cn/problem/solution/P3959)虽然是状压题，但是也能用随机化贪心水过去。 [P3973 [TJOI2015]线性代数](https://www.luogu.com.cn/problem/P3973)每次随机将$A$的一个位置上的数取反。 [P1692 部落卫队](https://www.luogu.com.cn/problem/P1692)每次随机打乱选人顺序然后贪心即可 [CF995C Leaving the Bar](https://www.luogu.com.cn/problem/CF995C)每次随机打乱向量序列然后贪心即可 [P1284 三角形牧场](https://www.luogu.com.cn/problem/P1284)随机交换+海伦公式 [P4212 外太空旅行](https://www.luogu.com.cn/problem/P4212)随机打乱序列后贪心 [CF329C Graph Reconstruction](https://www.luogu.com.cn/problem/CF329C)又双叒叕是随机打乱后贪心，不想再说啥了 [P3212 [HNOI2011]任务调度](https://www.luogu.com.cn/problem/P3212)对于$t_i=3$枚举，对于其他任务种类随机交换执行顺序然后贪心。 [P4703 偷上网](https://www.luogu.com.cn/problem/P4703)每次随机化一个坐标判断是否可行即可 $2,$爬山&模拟退火 适用范围：爬山法适用于单峰函数，而模拟退火适用于多峰函数 爬山法的思想是：只要我找到的新解比最优解更优，那么则一定接受，否则，则一定不接受。 模拟退火的思想是：只要我找到的新解比最优解更优，那么则一定接受，否则，则以一定概率（$e^{-\frac{\triangle E}{kT}}$）接受。 每次如何产生新解呢？方法则是在原最优解的基础上根据温度T的大小来做改动。 [讲的可能不是很清楚，这边建议看M_sea大佬的日报加深理解](https://m-sea.blog.luogu.org/qian-tan-SA) 题目： [P3382 【模板】三分法](https://www.luogu.com.cn/problem/P3382)显然是单峰函数极值问题，可以使用爬山求解。 [P4035 [JSOI2008]球形空间产生器](https://www.luogu.com.cn/problem/P4035)显然这个也是个单峰函数，同样可以使用爬山法求解。 [UVA10228 A Star not a Tree?](https://www.luogu.com.cn/problem/UVA10228)模拟退火经典题，求费马点，calc函数很好写。 [P1337 [JSOI2004]平衡点 / 吊打XXX](https://www.luogu.com.cn/problem/P1337)和上一题一模一样，只不过加了个权，变成加权费马点。 [P5544 [JSOI2016]炸弹攻击1](https://www.luogu.com.cn/problem/P5544)calc函数：首先要计算出在不触碰所有己方建筑的条件下所能达到的最大半径，接着计算这个最大半径能够干掉多少个敌军。 [P4360 [CEOI2004]锯木厂选址](https://www.luogu.com.cn/problem/P4360)前缀和+模拟退火 [P2538 [SCOI2008]城堡](https://www.luogu.com.cn/problem/P2538)模拟退火+dijkstra [P3936 Coloring](https://www.luogu.com.cn/problem/P3936)题目很简单，但是连通块以及各种东西的判定很麻烦。 [P1433 吃奶酪](https://www.luogu.com.cn/problem/P1433)正解是状压，但是可以通过模拟退火套随机化贪心艹过去。 [P3052 [USACO12MAR]Cows in a Skyscraper G](https://www.luogu.com.cn/problem/P3052)看见状压就要用模拟退火来搞，但是这题特意卡模拟退火，不过仍然能过，需要用到一个模拟退火当中的小trick——微调询问区间。 [P5911 [POI2004]PRZ](https://www.luogu.com.cn/problem/P5911)又是状压，模拟退火跑的很稳。 [P3475 [POI2008]POD-Subdivision of Kingdom](https://www.luogu.com.cn/problem/P3475)又是状压，不过这题退火要稍微卡一卡才能过qwq。 $3,$基于随机化的数据结构 $3.1$ 随机堆 如果你需要写可并堆，并且码量想写得比较少，那么选随机堆就对了，在合并时，随机与左子树或右子树合并即可。这样保证了左右子树的均匀，而且不需要频繁地交换左右儿子，并且很难被卡。 [P3377 【模板】左偏树（可并堆）](https://www.luogu.com.cn/problem/P3377)用随机堆很难被卡，更重要的是码量还小。 [CF827D Best Edge Weight](https://www.luogu.com.cn/problem/CF827D)树上差分+随机堆 $3.2$ 跳表 跳表是增加了向前指针的链表，原来的链表是$O(n)$查询，但是通过随机添加向前指针构建跳表可以达到$O(\log n)$的查询。 [P2286 [HNOI2004]宠物收养场](https://www.luogu.com.cn/problem/P2286) 本题单现在已经有了雏形，之后如果我再做到新的题或新的随机化算法时我会继续添加的qwq。