题目描述
Alice and Bob are playing game of Misère Nim. Misère Nim is a game playing on k piles of stones, each pile containing one or more stones. The players alternate turns and in each turn a player can select one of the piles and can remove as many stones from that pile unless the pile is empty. In each turn a player must remove at least one stone from any pile. Alice starts first. The player who removes the last stone loses the game.
题解
首先从小的考虑。都是1的话，显然偶数个1就必胜。如果只有一堆多于1的话，异或和不为0，而且一定可以取完后剩下奇数个1。所以一般情况先手只要保持自己取过后异或和为0，这样下次自己取的时候异或和一定不是0，那就一定会出现只有一堆大于1的情况，这时就是自己赢了。
AC代码
import java
.util
.Scanner
;
public class Main {
static final int NN
=110;
static int[] a
=new int[NN
];
public static void main(String
[] args
) {
int t
;
Scanner in
=new Scanner(System
.in
);
t
=in
.nextInt();
for(int z
=1;z
<=t
;z
++){
int n
=in
.nextInt();
int res
=0;
for(int i
=1;i
<=n
;i
++){
a
[i
]=in
.nextInt();
res
=res
^a
[i
];
}
int all1
=1;
for(int i
=1;i
<=n
;i
++){
if(a
[i
]!=1){all1
=0;break;}
}
int win
;
if(all1
==1){
win
=(n
+1)%2;
}
else{
win
=((res
!=0)?1:0);
}
System
.out
.print("Case "+z
+": ");
if(win
==1){
System
.out
.println("Alice");
}
else System
.out
.println("Bob");
}
}
}
