首页 > 代码库 > 51nod 博弈论水题

51nod 博弈论水题

2024-08-13 09:11:26   216人阅读

51nod1069 Nim游戏技术分享

有N堆石子。A B两个人轮流拿，A先拿。每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N及每堆石子的数量，问最后谁能赢得比赛。
例如：3堆石子，每堆1颗。A拿1颗，B拿1颗，此时还剩1堆，所以A可以拿到最后1颗石子。
/*对于某个局面(a1,a2,...,an)，若a1^a2^...^an<>0，一定存在某个合法的移动，将ai改变成ai‘后满足a1^a2^...^ai‘^...^an=0。不妨设a1^a2^...^an=k，则一定存在某个ai，它的二进制表示在k的最高位上是1（否则k的最高位那个1是怎么得到的）。这时ai^k<ai一定成立。则我们可以将ai改变成ai‘=ai^k，此时a1^a2^...^ai‘^...^an=a1^a2^...^an^k=0。*///O(n)求出必胜策略。#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)int read(){	int x=0;char c=getchar();	while(!isdigit(c)) c=getchar();	while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();	return x;} int main(){	int n=read(),t,ans=0;	rep(i,1,n) ans^=(t=read());	if(ans) puts("A");else puts("B");	return 0;}

51nod1067 Bash游戏 V2技术分享

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次只能拿1，3，4颗，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。
例如N = 2。A只能拿1颗，所以B可以拿到最后1颗石子。
//101111010111101011110#include<cstdio>#define rep(i,s,t) for(int i=s;i<=t;i++)int main(){	int n,u;scanf("%d",&n);	rep(i,1,n){		scanf("%d",&u);u%=7;		if(u==2||u==0) puts("B");else puts("A");	}	return 0;}

51nod1185 威佐夫游戏 V2技术分享

有2堆石子。A B两个人轮流拿，A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取。拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出2堆石子的数量，问最后谁能赢得比赛。
例如：2堆石子分别为3颗和5颗。那么不论A怎样拿，B都有对应的方法拿到最后1颗。
//打表找规律可知和黄金分割有关。这题卡精度需要模拟乘法。。。好神的模拟乘法。。。#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>#include<cmath>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define ll long longll read(){	ll x=0;char c=getchar();	while(!isdigit(c)) c=getchar();	while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();	return x;}ll ans[3]={618033988,749894848,204586834};const ll mod=1e9;int main(){	int t=read();ll a,b,aa,ab,ac,ad,ba,bb;double tp=(sqrt(5)+1)/2;	while(t--){		a=read(),b=read();		if(a>b) swap(a,b);		ba=(b-a)/mod,bb=(b-a)%mod;		aa=bb*ans[2];		ab=ba*ans[2]+aa/mod+bb*ans[1];		ac=ba*ans[1]+ab/mod+bb*ans[0];		ad=b-a+ba*ans[0]+ac/mod;		if(ad==a) puts("B");else puts("A");	}	return 0;}

　　

51nod 博弈论水题


联系
我们