Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 710 Accepted Submission(s): 501
Problem Description
Bob and Alice are playing a new game. There are n boxes which have been numbered from 1 to n. Each box is either empty or contains several cards. Bob and Alice move the cards in turn. In each turn the corresponding player should choose a non-empty box A and choose another box B that B< A && (A+B)%2=1 && (A+B)%3=0. Then, take an arbitrary number (but not zero) of cards from box A to box B. The last one who can do a legal move wins. Alice is the first player. Please predict who will win the game.
Input
The first line contains an integer T (T<=100) indicating the number of test cases. The first line of each test case contains an integer n (1<=n<=10000). The second line has n integers which will not be bigger than 100. The i-th integer indicates the number of cards in the i-th box.
Output
For each test case, print the case number and the winner’s name in a single line. Follow the format of the sample output.
Sample Input
2
2
1 2
7
1 3 3 2 2 1 2
Sample Output
Case 1: Alice
Case 2: Bob
【题目链接】:http://acm.hdu.edu.cn/showproblem.php?pid=3389
【题解】
/*
题目所给的条件其实可以简化成A+B == 6n+3;
也就是说(A+B)%6 == 3;
则对于可以互相传递纸牌的两个位置x,y(x< y)
(x+y)%6==3;
根据同余率;
(x%6+y%6)%6==3;
所以设x%6为a,y%6为b;
则可以传递纸牌的条件是
①a=0,b=3
②a=3,b=0
③a=1,b=2
④a=2,b=1
⑤a=4,b=5
⑥a=5,b=4
假设没有③..⑥这些能够传递纸牌的情况;只考虑①和②能传递纸牌;
则传递顺序必然是这样的(下面的数字都是下标从大到小%6后的结果)
0->3->0->3….->0->3
或
3->0->3->0….->0->3
最后一个传递到的数字一定是数字3(因为不能传递到数字0了);
这其实很像阶梯博弈了
【阶梯博弈】http://blog.csdn.net/harlow_cheng/article/details/54024055
我们只要对下标为%6为0的堆做NIM博弈就好了嘛
即把0传递给3的过程看作是把%6==0的下标的堆的“石头”扔掉;
(如果对方也一直在对0操作,则你的胜败肯定和0的那些堆的异或值决定的结果一样)
如果对方对3进行了一次操作->即传递给了0,那么你就把传递给0的牌等量地传递给3
这样又保持了0堆你是必胜的状态;且总是由你把0堆上的牌传递给3堆上的牌(或总是对方。。)
所以只要对0堆(i%6==0)的所有牌数异或就好了->作为第一个游戏的sg函数
③和④的情况
对应
2->1->2->1->2….->2->1 (1不能再变成2了!)
或
1->2->1->2->1….->2->1
则对2堆进行nim博弈(i%6==2的堆的异或值)->作为第二个游戏的sg函数
④和⑤
对应
5->4->5->4->5….->5->4 (1不能再变成2了!)
或
4->5->4->5->4….->5->4
则对5对进行nim博弈(i%6==5的堆的异或值)->作为第三个游戏的sg函数
把三个游戏的sg函数再异或一下;则为整个游戏的sg函数了;
为0则先手胜,否则先手输;
因为异或有交换律;
所以直接异或i%6==0,2,5的堆就好了;不必按顺序真的一个一个游戏搞sg函数;
*/
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
//const int MAXN = x;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
int main()
{
//freopen("F:\\rush.txt","r",stdin);
int T;
rei(T);
rep1(ii,1,T)
{
int n,ans = 0;
rei(n);
rep1(i,1,n)
{
int x;
rei(x);
if (i%6==0 || i%6==2 || i%6==5)
ans = ans ^ x;
}
if (ans==0)
printf("Case %d: Bob\n",ii);
else
printf("Case %d: Alice\n",ii);
}
return 0;
}