codeforces：C.EvenNumberAddicts【数学推理+博弈论】

Alice和Bob轮流在数组a中不放回地选数字&＃xff0c;Alice先选
如果Alice最终选的数字的总和是偶数&＃xff0c;那么Alice获胜
否则&＃xff0c;Bob获胜

• 我们只需要考虑奇数和偶数出现的次数即可&＃xff0c;设偶数出现a次&＃xff0c;奇数出现b次&＃xff0c;不妨设偶数为0&＃xff0c;奇数为1
• 一种简单的想法是&＃xff0c;如果a % 2 &＃61; 0, 且b % 4 &＃61; 2, 那么bob总是能做alice的跟屁虫&＃xff0c;和alice平分&＃xff0c;最终alice获得b / 2个奇数&＃xff0c;也就是2m &＃43; 1个奇数&＃xff0c;和就是奇数&＃xff0c;所以bob获胜

根据上述的分类&＃xff0c;我们可以参照mod 4这个标准&＃xff0c;进行分析

• b % 4 &＃61; 2&＃xff0c;bob要做alice的跟屁虫&＃xff08;alice选啥bob就选啥&＃xff09;&＃xff0c;如果alice选了最后一个0&＃xff0c;没办法bob只能继续选1&＃xff0c;但这不影响bob和alice最终平分1&＃xff0c;也就是2m &＃43; 1个奇数&＃xff0c;alice的和是奇数&＃xff0c;bob胜
• b % 4 &＃61; 3&＃xff0c;参照上述情况&＃xff0c;alice先选一个1使得b % 4 &＃61; 2&＃xff0c;这样的话&＃xff0c;bob就成了b % 4 &＃61; 2先选的&＃xff0c;所以alice一定可以获得奇数个1&＃xff0c;加上之前的第一个1&＃xff0c;所以和就是偶数&＃xff0c;alice胜
• b % 4 &＃61; 0&＃xff0c;alice先选一个0&＃xff0c;之后alice做bob的跟屁虫&＃xff0c;如果bob选了最后一个0&＃xff0c;没办法alice只能继续选1&＃xff0c;但这不影响bob和alice最终平分1&＃xff0c;也就是2m个奇数&＃xff0c;alice的和是奇数&＃xff0c;alice胜
• b % 4 &＃61; 1&＃xff0c;如果alice和bob先选了1&＃xff0c;就会转化为b % 4 &＃61; 0的情况&＃xff0c;所以第一个选1的人后面将会选到偶数个1
  • 如果a % 2 &＃61; 1&＃xff0c;bob会选到第一个1&＃xff0c;那它接着会选到偶数个1&＃xff0c;意味着bob选到的和是奇数&＃xff0c;alice选到的和是偶数&＃xff0c;alice胜
  • 如果a % 2 &＃61; 1&＃xff0c;alice会选到第一个1&＃xff0c;那它接着会选到偶数个1&＃xff0c;意味着alice选到的和是奇数&＃xff0c;bob胜

# -*- coding: utf-8 -*-
# &＃64;Time : 2022/10/4 23:17
# &＃64;Author : bridgekiller
# &＃64;FileName: 1738C.py
# &＃64;Software: PyCharm
# &＃64;Blog &＃xff1a;bridge-killer.blog.csdn.netimport sysinput &＃61; sys.stdin.readline# 装饰器
# 解决带有参数和返回值函数的装饰器
# 类似aop的思想, 非侵入式地横切
# --------------------
def debug(func):def wrapper(*args, **kwargs):print(&＃39;----------------&＃39;)res &＃61; func(*args, **kwargs)print(&＃39;----------------&＃39;)return resreturn wrapper# --------------------# 装饰器&＃xff0c;解决dfs爆栈问题
# --------------------
# 手写栈模板
# 克服py栈太浅的问题
from types import GeneratorTypedef bootstrap(f, stack&＃61;[]):def wrappedfunc(*args, **kwargs):if stack:return f(*args, **kwargs)else:to &＃61; f(*args, **kwargs)while True:if type(to) is GeneratorType:stack.append(to)to &＃61; next(to)else:stack.pop()if not stack:breakto &＃61; stack[-1].send(to)return toreturn wrappedfunc# --------------------def solve():n &＃61; int(input().strip())a &＃61; list(map(int, input().split()))odd, even &＃61; 0, 0for aa in a:if aa % 2 &＃61;&＃61; 0:even &＃43;&＃61; 1else:odd &＃43;&＃61; 1if odd % 4 &＃61;&＃61; 2:print(&＃39;Bob&＃39;)elif odd % 4 &＃61;&＃61; 3:print(&＃39;Alice&＃39;)elif odd % 4 &＃61;&＃61; 0:print(&＃39;Alice&＃39;)else:if even % 2 &＃61;&＃61; 1:print(&＃39;Alice&＃39;)else:print(&＃39;Bob&＃39;)if __name__ &＃61;&＃61; &＃39;__main__&＃39;:for _ in range(int(input())):solve()

总结

在dp面前&＃xff0c;数学就是降维打击~