SHU训练六——博弈(一)

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;
}
上一篇:PTA1023-C语言-组个最小数


下一篇:利用深度学习在GTA5进行自动驾驶——食用方法