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
2
3
4
5
6
7
8
n = input()
arr = [int(x) for x in input().split()]
for i in arr:
if i % 2:
print('Alice')
exit()

print('Bob')