2020 GDUT 新生赛 C https://ac.nowcoder.com/acm/contest/9692/C

首先简单讨论一下 的几种情况。

  • ，母牛也就只能啪的一下把自己毙了，很快啊！母猪胜。
  • ，母牛打了 枪后，母猪接下来必须开致命的那枪，母牛胜。
  • ，母牛开了 枪后，母猪接着也只开 枪，把致命的那一枪留给母牛，母猪胜。
  • ，母牛开了 枪后，母猪接着开 枪，把致命的那一枪留给母牛，母猪胜。
  • ，母牛开了 枪后，如果母猪开 枪，母牛接下来就开 枪；如果母猪开 枪，母牛接下来就开 枪。反正母猪最后必须开致命的那枪，母牛胜。

对于 的情况，看官方题解的时候各种易证就看得很迷，最后还是把可能的情况给枚举了一下：

其实整个思考的过程大概是个数学归纳法吧，就是假设一方（假设是 ）在某一轮打的枪数小于 而且开的最后一枪是总的第 枪，那么另一方（假设是 ）接下来可能采取的行动最多四种，分别是打 枪，分别对应图中的一棵子树。但是无论如何， 总有策略使得在某一轮轮到自己的时候，打的枪数依然小于 而且最后一枪是总的第 枪。还是配合着上面的图来看，打了圈的是 可以采取的策略，没打圈的是 所有可能采取的行动。

然后发现胜者为了使第 枪成为自己某一轮的最后一枪，必定有策略使得第 枪是自己某一轮的最后一枪而且这一轮打的枪数小于 ，接下来就可以五个五个往下继续了。举个例子：，母猪能确保第 枪是自己某一轮的最后一枪（就是 的情况），从而按照上面的策略走，确保第 枪是自己某一轮的最后一枪，从而确保自己胜利。