2020 GDUT 新生赛 C https://ac.nowcoder.com/acm/contest/9692/C
首先简单讨论一下 的几种情况。
,母牛也就只能啪的一下把自己毙了,很快啊!母猪胜。
,母牛打了
枪后,母猪接下来必须开致命的那枪,母牛胜。
,母牛开了
枪后,母猪接着也只开
枪,把致命的那一枪留给母牛,母猪胜。
,母牛开了
枪后,母猪接着开
枪,把致命的那一枪留给母牛,母猪胜。
,母牛开了
枪后,如果母猪开
枪,母牛接下来就开
枪;如果母猪开
枪,母牛接下来就开
枪。反正母猪最后必须开致命的那枪,母牛胜。
对于 的情况,看官方题解的时候各种易证就看得很迷,最后还是把可能的情况给枚举了一下:
其实整个思考的过程大概是个数学归纳法吧,就是假设一方(假设是 )在某一轮打的枪数小于
而且开的最后一枪是总的第
枪,那么另一方(假设是
)接下来可能采取的行动最多四种,分别是打
枪,分别对应图中的一棵子树。但是无论如何,
总有策略使得在某一轮轮到自己的时候,打的枪数依然小于
而且最后一枪是总的第
枪。还是配合着上面的图来看,打了圈的是
可以采取的策略,没打圈的是
所有可能采取的行动。
然后发现胜者为了使第 枪成为自己某一轮的最后一枪,必定有策略使得第
枪是自己某一轮的最后一枪而且这一轮打的枪数小于
,接下来就可以五个五个往下继续了。举个例子:
,母猪能确保第
枪是自己某一轮的最后一枪(就是
的情况),从而按照上面的策略走,确保第
枪是自己某一轮的最后一枪,从而确保自己胜利。