lstqwq的随机化算法题单
题单介绍
前置知识：如何生成给定范围内的随机整数，浮点数，知道如何随机打乱一个序列，最好对随机数有充分的了解。
让我们开启我们的随机化算法之旅吧（本题单已经自动略过毒瘤题，请放心食用）。
* $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)随机打乱序列后贪心
[CF798D Mike and distribution](https://www.luogu.com.cn/problem/CF798D) 随机打乱序列后贪心
[P3212 [HNOI2011]任务调度](https://www.luogu.com.cn/problem/P3212)对于$t_i=3$枚举，对于其他任务种类随机交换执行顺序然后贪心
[P5911 [POI2004]PRZ](https://www.luogu.com.cn/problem/P5911)随机化吊打状压（
[P3475 [POI2008]POD-Subdivision of Kingdom](https://www.luogu.com.cn/problem/P3475)随机化再次吊打状压
[P4220 [WC2018]通道](https://www.luogu.com.cn/problem/P4220) 随机化好题
[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)模拟退火经典题：求费马点，爬山可能更好qwq
[P1337 [JSOI2004]平衡点 / 吊打XXX](https://www.luogu.com.cn/problem/P1337)求加权费马点
[P5544 [JSOI2016]炸弹攻击1](https://www.luogu.com.cn/problem/P5544)模拟退火卡常题
[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——微调询问区间
[CF2C Commentator problem](https://www.luogu.com.cn/problem/CF2C)模拟退火，需要有计算几何基础
[SP4409 AREA1 - Circle vs Triangle](https://www.luogu.com.cn/problem/SP4409)一道很神的题，需要很强的计算几何基础，但不毒瘤
[SP34 RUNAWAY - Run Away](https://www.luogu.com.cn/problem/SP34)简单模拟退火，注意在生成新的解时如果不合法要重新生成
* $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。