本文主要是介绍[IOI2021]地牢游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
地牢游戏
题解
首先，我们根据 s u b t a s k 3 , 4 subtask\,3,4 subtask3,4，应该很容易想到一种倍增的做法去解决我们的问题。
对于这几个图，我们的分层是相当少的，所以我们可以将我们整个过程分成至多 6 6 6个阶段，对于每个阶段单独倍增直到超越这个阶段，或者说抵达我们的终点。
我们考虑将我们的倍增做法延伸到我们的正解上，显然，由于当我们胜利后会直接加上一个 s i s_i si，所以可以发现这实际上是一个加倍的过程，我们先前打不掉，然后变得打得掉最多只会经过 log S \log\,S logS层。
我们可以把我们的整个段化划分成 log S \log\,S logS个 [ 2 k , 2 k + 1 ) [2^k,2^{k+1}) [2k,2k+1)的区间，每次进入这个区间后我们就看成我们可以 w i n win win下所有 s < 2 k s< 2^k s<2k的点，会输掉所有 s ⩾ 2 k s\geqslant 2^k s⩾2k的点。
我们一直倍增到我们跑到一个可以打赢的 [ 2 k , 2 k + 1 ) [2^k,2^{k+1}) [2k,2k+1)点的位置，显然，这种情况我们就可以跳出这个区间了。或者我们的值超过 2 k + 1 2^{k+1} 2k+1，亦或者我们抵达了我们的终点为止。
判断我们是否跑到一个可以打赢的 [ 2 k , 2 k + 1 ) [2^k,2^{k+1}) [2
这篇关于[IOI2021]地牢游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
