一些简单的分析过程
(a,b)表示a个正面，b个反面的状态。
<u,v>表示u个正面且v个反面的硬币翻转。
则新状态(a-(u-v),b+(u-v))
且有a+b=n,u+v=m
m为偶数，则u,v奇偶性相同，故u-v为偶数。
故状态的(a,b)变换后的新状态(a',b'),a和a'奇偶性相同，b和b'奇偶性相同。
初始(n,0)
目标(0,n)
因此n为奇数不可能。n为偶数有可能。
现在需要进一步推导n为偶数是一定可以的。
(a,b) R (A,B) 表示(a,b)可达(A,B)
显然R满足自反性，对称性，传递性，是等价关系。
一个状态(a,b)的自由度实际上只有一个。若取定了a，则b=n-a
下面尝试证明a-A=2k时，(a,b) R (A,B)
因为对称性的原因，我们只需要考虑k>=0的情况。
- 2k<m,操作方案<u,v>需要且只需要满足①u+v=m,②u-v=2k.因此得到u=m/2+k,v=m/2-k.因为2k<m,故u,v都在[0,m]的范围内，且都是整数。也就是说必然存在方案（解就是方案）。
- 2k>=m,则只需要考察 (a-m,b+m)与(A,B)是否满足R关系。显然经过有限次迭代之后一定会转化为条件1(2k<m)
至此，已经可以确定只要状态的第一个数的奇偶性是相同的，则一定可以变换得到。
因此Yes等价于n是偶数。
现在增加了一次翻转一枚硬币的操作。事实上，无论翻转哪枚，都将改变状态的奇偶性。
因此，Bob的策略就是——
如果n是奇数，看戏就好。
如果n是偶数，Alice翻完之后，随便翻一枚，改变状态奇偶性，变成奇数的情况就好。只是n=m的情况下Bob没有翻的机会Alice就赢了。
华为工作强度 799人发布