DPairの随机化题单

众所周知,随机化是提升算法效率的一种有效方法。

所以这一类题一般都比较有意思。

下面给出一些可以(或需要)随机化实现,并且基本可以保证(证明)其高正确性的题目。

可能会涉及其他算法。

并不包括模拟退火。

持续更新中。。。

Part1 效率提升类

有些时候我们正常算法的复杂度无法接受,于是我们采用 正确率很高 的随机化提升算法效率。

其实和提升效率有异曲同工之妙,也是在保证正确性的情况下尽可能减少询问。

对于这种题要记住:“跑得快不一定赢,不跌跟头,才是成功。”


  1. CF1305F - Kuroni and the Punishment
  2. CF840D - Destiny
  3. CF843B - Interactive LowerBound
  4. CF862D - Mahmoud and Ehab and the binary string
  5. CF1114E - Arithmetic Progression
  6. CF1354G - Find a Gift
  7. CF1438F - Olha and Igor
  8. CF1039B - Subway Pursuit
  9. CF1061F - Lost Root
  10. CF1198F - GCD Groups 2