Skip to content

Latest commit

 

History

History
 
 

810.Chalkboard-XOR-Game

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

810.Chalkboard-XOR-Game

对于Alice而言,如果手头的X=x1^x2^x3^...^xn=0,那么算赢.

如果X!=0,因为XOR的运算具有交换律,所以最后必然可以化简为ai^Ai!=0的形式.其中ai是其中的某个元素xi,而Ai是除了xi以外所有元素的亦或和.如果Ai不是零的话,那么Alice取ai就可以了(因为留给对手的是Ai).如果这个Ai是零的话,那么我们试图重新找一个a/A的组合,直到找到一个非零的Ai,于是Alice就可以取相应的ai.

那么会不会所有的Ai都是零呢?我们来分析一下.假设所有的Ai都是零.那么A1^A2^...^An=X^X^..^X (共n-1次)=0.由此推出n必须是奇数.根据逆否的性质,如果n是偶数的话,那么不可能所有的Ai都是零,于是Alice必然有此轮不输策略.

于是有意思的事情来了.如果n是偶数,Alice有不输的策略;轮到Bob的时候,n就是奇数;如果他侥幸能存活那一轮,再轮到Alice的时候,她面对的依然是n是偶数的情况,又有了不输的策略.这个轮回最多一直持续到Bob只剩下一个数可选,也就必输了.

所以,如果数列的总个数是偶数的话,对于先手(Alice)必赢.反之,Bob面对的总是偶数的情况,他就能必赢.

Leetcode Link