算法 博弈论(集合 Nim游戏)
程序员文章站
2023-12-30 10:25:52
给定n堆石子以及一个由k个不同正整数构成的数字集合S。现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合S,最后无法进行操作的人视为失败。问如果两人都采用最优策略,先手是否必胜。输入格式第一行包含整数k,表示数字集合S中数字的个数。第二行包含k个整数,其中第i个整数表示数字集合S中的第i个数si。第三行包含整数n。第四行包含n个整数,其中第i个整数表示第i堆石子的数量hi。输出格式如果先手方必胜,则输出“Yes”。否则,输出“No”。数据范围...
给定n堆石子以及一个由k个不同正整数构成的数字集合S。
现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合S,最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
输入格式
第一行包含整数k,表示数字集合S中数字的个数。
第二行包含k个整数,其中第i个整数表示数字集合S中的第i个数si。
第三行包含整数n。
第四行包含n个整数,其中第i个整数表示第i堆石子的数量hi。
输出格式
如果先手方必胜,则输出“Yes”。
否则,输出“No”。
数据范围
1≤n,k≤100,
1≤si,hi≤10000
输入样例:
2
2 5
3
2 4 7
输出样例:
Yes
#include<cstring>
#include<algorithm>
#include<unordered_set>
#include<iostream>
using namespace std;
const int N=110,M=10010;
int n,m;
int s[N],f[M];//s储存石子的个数,f储存SG的值
int SG(int x)
{if(f[x]!=-1)
return f[x];//避免f[x]重复计算
unordered_set<int> S;
for(int i=0;i<m;i++)
{
int sum=s[i];
if(x>=sum)
S.insert(SG(x-sum));
}
//寻找S集合之外的最小非负整数
for(int i=0;;i++)
if(!S.count(i))
return f[x]=i;
}
int main()
{
cin>>m;
for(int i=0;i<m;i++)
cin>>s[i];
cin>>n;
int res=0;
memset(f,-1,sizeof f);//因为SG(X)的值都是>0,可用-1表示这个数没有算过
while(n--)
{
int x;
cin>>x;
res^=SG(x);
}
if(res)
printf("Yes");
else cout<<"No";
}
MEX,SG与胜败补充
SG入门介绍
本文地址:https://blog.csdn.net/Kerryliuyue/article/details/107886245