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