欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

算法 博弈论(集合 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
算法 博弈论(集合 Nim游戏)
算法 博弈论(集合 Nim游戏)

算法 博弈论(集合 Nim游戏)

#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入门介绍
算法 博弈论(集合 Nim游戏)
算法 博弈论(集合 Nim游戏)

本文地址:https://blog.csdn.net/Kerryliuyue/article/details/107886245

相关标签: 算法

上一篇:

下一篇: