DPairの随机化题单

众所周知，随机化是提升算法效率的一种有效方法。 所以这一类题一般都比较有意思。 下面给出一些可以（或需要）随机化实现，并且基本可以保证（证明）其高正确性的题目。 可能会涉及其他算法。 并不包括模拟退火。 持续更新中。。。 ## Part1 效率提升类 有些时候我们正常算法的复杂度无法接受，于是我们采用 **正确率很高** 的随机化提升算法效率。 - [CF1305F Kuroni and the Punishment](https://www.luogu.com.cn/problem/CF1305F) - [CF840D Destiny](https://www.luogu.com.cn/problem/CF840D) ## Part2 询问减少类 ~~不要问我为什么全是交互题，我也不知道~~ 其实和提升效率有异曲同工之妙，也是在保证正确性的情况下尽可能减少询问。 对于这种题要记住：**“跑得快不一定赢，不跌跟头，才是成功。”** - [CF843B Interactive LowerBound](https://www.luogu.com.cn/problem/CF843B) - [CF862D Mahmoud and Ehab and the binary string](https://www.luogu.com.cn/problem/CF862D) - [CF1114E Arithmetic Progression](https://www.luogu.com.cn/problem/CF1114E) - [CF1354G Find a Gift](https://www.luogu.com.cn/problem/CF1354G) - [CF1438F Olha and Igor](https://www.luogu.com.cn/problem/CF1438F) - [CF1039B Subway Pursuit](https://www.luogu.com.cn/problem/CF1039B) - [CF1061F Lost Root](https://www.luogu.com.cn/problem/CF1061F)