Incredible Chess
Left Right
思路：
nim模板题。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=510;
int a[maxn],b[maxn];
int main(){
int T,Case=1;
cin>>T;
while(T--){
int n;cin>>n;
int res=0;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
res^=(y-x-1);
}
cout<<"Case "<<Case++<<":";
if(res) printf(" Alice\n");
else puts(" Bob");
}
return 0;
}
Matrix Game
题意：
给定一个n*m的格子，每个格子都有石子，玩家可以每次在任意一行中取任意个石子，问先手是否能赢。
思路：
由于每次玩家都是在任意一行取石子，把每一行的石子加起来就转化成nim游戏了。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=510;
int main(){
int T,Case=1;
cin>>T;
while(T--){
int n,m;cin>>n>>m;
ll res=0;
for(int i=1;i<=n;i++){
ll tmp=0;
for(int j=1;j<=m;j++){
ll x;cin>>x;
tmp+=x;
}
res^=tmp;
}
cout<<"Case "<<Case++<<":";
if(res) printf(" Alice\n");
else puts(" Bob");
}
return 0;
}
Misere Nim
题意：
n堆石子，每个人可以取任意个但是不能不取，取走最后一个石子的人输。求输赢状态。
思路：
Anti-Nim游戏。
结论为：
先手必胜当且仅当
所有堆的石子数都为1并且游戏的SG值为0
有些堆的石子数大于1且游戏的SG值不为0
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=510;
int main(){
int T,Case=1;
cin>>T;
while(T--){
ll res=0,cnt=0;
int n;cin>>n;
for(int i=1;i<=n;i++){
ll x;cin>>x;
res^=x;
if(x==1) cnt++;
}
cout<<"Case "<<Case++<<":";
if((cnt==n&&res==0)||(cnt<n&&res)) printf(" Alice\n");
else puts(" Bob");
}
return 0;
}
Crazy Calendar
题意：
给定一个n*m的格子，每个格子都有石子，每次可以将格子的任意个石子向正下方或正右方移动，直到到达边缘，问输赢情况。
思路：
当先手移动到右下角时，先手必胜。
到右下角距离为偶数的点对答案不会产生影响，到右下角距离为奇数的点才会影响答案，对所有奇数点做一遍nim游戏就好啦。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int T,Case=1;
cin>>T;
while(T--){
ll res=0,cnt=0;
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ll x;cin>>x;
int cnt1=n-i+1+m-j+1;
if(cnt1%2){
res^=x;
}
}
}
cout<<"Case "<<Case++<<":";
if(!res) printf(" lose\n");
else puts(" win");
}
return 0;
}
Partitioning Game
题意：
n堆物品，每堆物品有多个组成，Alice和Bob轮流依次对这些物品进行操作，每次都要把其中一堆物品分成不同的个数，最后一个没办法再进行操作的人输掉比赛。
思路：
由于每一堆物品的分割都是相互独立的，所以我们可以用SG函数来处理，先计算一堆的，对于一个由a件物品组成的堆，可以分割的后继方法有（1，a-1），（2，a-2），（3，a-3），……，（（a-1）/2，a-（a-2）/2）；
由于由同一堆分割好的两堆也是相互独立的，所以再用SG定理，得到：SG(x)=mex{SG(1)^SG(a-1), SG(2)^SG(a-2), SG(3)^SG(a-3), ... ,SG((a-1)/2)^SG(a-(a-1)/2)};
则最后的答案是：SG(a1)SG(a2)SG(a3)...SG(an);
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10010;
int sg[maxn],vis[maxn];
void init(){
memset(sg,0,sizeof sg);
for(int i=1;i<=10000;i++){
memset(vis,0,sizeof vis);
for(int j=1;j+j<i;j++)
vis[sg[j]^sg[i-j]]++;
for(int j=0;j<=10000;j++)
if(!vis[j]){
sg[i]=j;break;
}
}
}
int main(){
init();
int T,Case=1;
cin>>T;
while(T--){
int n,res=0;cin>>n;
for(int i=1;i<=n;i++){
int x;cin>>x;
res^=sg[x];
}
cout<<"Case "<<Case++<<":";
if(res) printf(" Alice\n");
else puts(" Bob");
}
return 0;
}
Again Stone Game
题意：
有n堆石子，两个人轮流操作，每次至少选择一堆，拿走至少一个石子，但是不要拿走超过一半的石子。不能操作者输。
思路：
先SG函数打表找规律，得到：
该堆石子数为偶数时，SG值等于他的一半
为奇数时，将他不断/2变为偶数，SG值等于该偶数的SG值
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int sg[maxn],vis[maxn];
void init(){
memset(sg,0,sizeof sg);
for(int i=1;i<maxn;i++){
memset(vis,0,sizeof vis);
for(int j=1;j<=i/2;j++)
vis[sg[i-j]]=1;
for(int j=0;;j++){
if(!vis[j]){
sg[i]=j;break;
}
}
}
}
int main(){
int T,Case=1;
cin>>T;
while(T--){
int n;cin>>n;
int res=0;
for(int i=1;i<=n;i++){
int x;cin>>x;
if(x%2) x/=2;
res^=(x/2);
}
cout<<"Case "<<Case++<<":";
if(!res) puts(" Bob");
else puts(" Alice");
}
return 0;
}
Game of Hyper Knights
题意：
给出一个棋盘，两个人每次按照图中方式移动棋子，不能移动者输。问输赢。
思路：
二维的SG函数，先手必胜的条件是所有棋子的SG值异或和不为0.对于每个棋子，SG值等于后继点的mex值。dfs求解即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int sg[1100][1100];
int nx[]={-2,-3,-2,-1,-1,1};
int ny[]={1,-1,-1,-2,-3,-2};
int dfs(int x,int y){
if(sg[x][y]!=-1) return sg[x][y];
set<int>s;
for(int i=0;i<6;i++){
int xx=x+nx[i],yy=y+ny[i];
if(xx>=0&&yy>=0) s.insert(dfs(xx,yy));
}
for(int i=0;;i++)
if(s.count(i)==0){
sg[x][y]=i;
return i;
}
}
int main(){
memset(sg,-1,sizeof sg);
int T,Case=1;
cin>>T;
while(T--){
int n;cin>>n;
int res=0;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
res^=dfs(x,y);
}
cout<<"Case "<<Case++<<":";
if(!res) puts(" Bob");
else puts(" Alice");
}
return 0;
}