Question

C++ 看不懂问题 提供一下思路呗

Answer 1

博弈论问题，可以用
反推法
取胜者最后一次戳爆的气球数x一定满足1≤x≤3或1≤x≤5（取决于采取方案①还是②）
即落败者最后一次戳气球时剩余气球数一定为4（这里假设采用方案①，下同），为3或为5都会导致失败。由于双方都采取最优策略，可推得落败者倒数第二次戳气球时剩余气球数一定为8。所以你会发现这个问题实际上是一个
同余
问题。只要轮到你戳气球时，保证戳完后剩余气球数x满足x≡0(mod
4)即可取胜。为了满足这一条件，你需要：①在对方每次戳完气球后，自己下次戳爆的气球数和对方本轮戳爆气球数之和为4；②保证对方第一次戳球后剩下球数x不满足x≡0(mod
4)
若能满足条件①和②，则此游戏一定取胜。否则，必须采取方案二，尝试使对方每次戳球前总球数满足x≡0(mod
6)。若方案二也不能满足，则此游戏必败。
而你会发现，条件②实际上就相当于总球数n≡0(mod
4)。因此，当总球数n能被4
整除
时，应该采用方案①；同理，当总球数n能被6整除时，应该采用方案②。得到结论：当总球数n为4或6的倍数时，这个游戏可以取胜；否则，必定失败。