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')