Yet Another Game of Stones(博弈论)

题目链接:题目

题意:

n堆石子。B每次在一堆取正数个。A取石子的数量受堆的限制。

堆类型是0:每次取正数个。


堆类型是1:每次取奇数个。

堆类型是2:每次取偶数个。

输出必胜的人。


题解:
与经典的nim博弈只差在A取个别石子有限制。那么首先考虑A取石子有限制的那几堆。

1.ai是奇数,bi=2。A必定取不完,那么最后肯定会剩下一个情景是:只有一堆是1,其他都是0。要么此时A取,要么此时B取。无论如何A都输。

2.ai是偶数,bi=2。A一定要在第一次就全取完这一堆,否则B可以把这一堆变成情况1。

3.ai是奇数且大于一个,bi=1。A如果不一次取完,B可以取得剩下2个,使得A输。

4.ai是偶数,bi=1。A如果不取得剩下1个, B可以取得剩下2个,使得A输。
 

5.如果A避开了情况234中的情况(234中的情况只出现小等于一次才能避开),就变成了普通的nim博弈。

#include<cstdio>
 
const int N=100005;
int a[N],b[N];
 
void print(int x) {
	if(x) puts("Alice");
	else puts("Bob");
}
 
int main() {
	int T;scanf("%d",&T);
	while(T--) {
		///
		int n;scanf("%d",&n);
 
		///read
		for(int i=1;i<=n;++i) scanf("%d",a+i);
		for(int i=1;i<=n;++i) scanf("%d",b+i);
 
		///solve
		int cnt0=0,cnt1=0;
		for(int i=1;i<=n;++i) {
			if(a[i]%2&&b[i]==2) ++cnt0;
			if((a[i]>1&&b[i]==1)||(a[i]%2==0&&b[i]==2)) {
				++cnt1;
				if(a[i]%2==0&&b[i]==1) {
					a[i]=1;
				} else {
					a[i]=0;
				}
			}
		}
		if(cnt0||cnt1>=2) {
			print(0);
			continue;
		}
		int ans=0;
		for(int i=1;i<=n;++i) ans=ans^a[i];
		print((cnt1==0&&ans)||(cnt1&&ans==0)); 
	}
	return 0;
}
 
  1.  
原文地址:https://www.cnblogs.com/shmilky/p/14088996.html