写一些博弈模板,借用51Nod上的题目: Bash游戏: 有一堆石子共有N个。A B两个人轮流拿,A先拿。每次最少拿1颗,最多拿K颗,拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过
写一些博弈模板,借用51Nod上的题目:
Bash游戏:
有一堆石子共有N个。A B两个人轮流拿,A先拿。每次最少拿1颗,最多拿K颗,拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出N和K,问最后谁能赢得比赛。
#include <bits/stdc++.h>using namespace std;
int main(){
int t,n,k;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
if(n <= k) printf("A\n");
else{
if(n%(k+1) == 0) printf("B\n");
else printf("A\n");
}
}
return 0;
}
Bash游戏V2:
using namespace std;
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
if(n%7 == 0||n%7 == 2) printf("B\n");
else printf("A\n");
}
return 0;
}
有一堆石子共有N个。A B两个人轮流拿,A先拿。每次拿的数量只能是2的正整数次幂,比如(1,2,4,8,16....),拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出N,问最后谁能赢得比赛
#include <bits/stdc++.h>using namespace std;
char s[1005];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
int n=strlen(s);
int ans=0;
for(int i=0;i<n;i++)
{
ans=ans+(s[i]-'0');
}
if(ans%3)
printf("A\n");
else
printf("B\n");
}
return 0;
}
Bash游戏V4:
有一堆石子共有N个。A B两个人轮流拿,A先拿。每次拿的数量最少1个,最多不超过对手上一次拿的数量的2倍(A第1次拿时要求不能全拿走)。拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出N,问最后谁能赢得比赛。
using namespace std;
const int maxn=50;
long long f[50];
int main()
{
f[1]=1,f[2]=2;
for(int i=3;i<maxn;i++)
f[i]=f[i-1]+f[i-2];
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int sign=1;
for(int i=1;i<maxn;i++)
{
if(f[i]>n)
break;
if(f[i]==n)
{
sign=0;
break;
}
}
if(sign)
printf("A\n");
else
printf("B\n");
}
return 0;
}
威佐夫游戏(精度控制):
有2堆石子。A B两个人轮流拿,A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子,但不可不取。拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出2堆石子的数量,问最后谁能赢得比赛。
#include <cmath>
using namespace std;
typedef unsigned long long ULL;
const ULL Gold[3] = {618033988, 749894848, 204586834};
const ULL MOD = 1000000000;
int main()
{
int t;
cin >> t;
ULL a, b;
while (t--)
{
cin >> a >> b;
if (a < b)
{
swap(a, b);
}
ULL dist = a - b;
ULL pre = dist / MOD, las = dist % MOD;
ULL a1 = las * Gold[2];
ULL a2 = pre * Gold[2] + las * Gold[1] + a1 / MOD;
ULL a3 = pre * Gold[1] + las * Gold[0] + a2 / MOD;
ULL a4 = dist + pre * Gold[0] + a3 / MOD;
cout << (a4 == b ? 'B' : 'A') << endl;
}
}
Nim游戏:
有N堆石子。A B两个人轮流拿,A先拿。每次只能从一堆中取若干个,可将一堆全取走,但不可不取,拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出N及每堆石子的数量,问最后谁能赢得比赛。
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int ans=0,x;
for(int i=1; i<=n; i++)
{
scanf("%d",&x);
ans=ans^x;
}
if(ans==0)
printf("B\n");
else
printf("A\n");
}