UESTC 2503
题目
Alice 和 Bob 在做游戏。有一个长度为$n$的正整数序列,Alice 先手,两人轮流操作。Alice 需要删掉一个非空连续子段,子段和为奇数;Bob 需要删掉一个非空连续子段,子段和为偶数。删除子段后左右两段拼接起来形成新的序列。不能操作的人输。如果两个人都足够聪明,那么谁会获胜?
题解
直接判断序列中有没有奇数就行,有的话就是Alice获胜,没有则Bob获胜。
如何推导出这个结论呢?
Alice先手,而Alice只能拿和为奇数的子串,
如果一开始就全部是偶数,那么就不存在和为奇数的子串,Alice必输。
假如有奇数,我们知道奇数+偶数是奇数,所以对于一个存在奇数的序列,
- 如果序列和就是奇数,那么Alice可以直接拿完,Bob无法继续,Alice获胜。
- 如果序列和是偶数,那么Alice可以拿到只剩下一个奇数,此时
- 剩下0个偶数,Bob无法拿取,Alice获胜。
- 剩下若干偶数和一个奇数,此时Bob还可以拿一次,下一次Alice可以直接拿完,Bob无法拿取,Alice获胜。
这就是我推导出的全过程。
代码
AC代码(Python)
超级简单,只有8行。
因为一发入魂,所以没有写测试例生成和暴力验证。
1 | n = input() |