数学基础

更新: 12/19/2024 字数: 0 字 时长: 0 分钟

博弈论

sg函数

#include <bits/stdc++.h>

using namespace std;

const int N=110,M=10010;
int n,m;
int f[M],s[N];

int sg(int x){
    if(f[x]!=-1) return f[x];  //如过使用过，直接返回
    set<int> S;                //使用二叉树来存储是否使用过。
    for(int i=0;i<n;i++){      //遍历所有的拿去可能1
        int sum=s[i];
        if(x>=sum) S.insert(sg(x-sum));    //递归到下一层，并且将这个数据记住
    }
    for(int i=0;;i++){                     
        if(!S.count(i)) return f[x]=i;     //利用循环查找未出现的最小数
    }
}

int main(){
    cin>>n;
    for (int i=0;i<n;i++) cin>>s[i];
    cin>>m;
    int res=0;
    memset(f,-1,sizeof f);   //用于存储每一个x对应的值，初始化为-1
    for(int i=0;i<m;i++){
        int x;
        cin>>x;
        res^=sg(x);
    }
    if(!res)cout<<"No";   //由于拿的数量有限制，所以不一定到0才会结束，对应异或值只要不为0就是必输
    else cout<<"Yes";
}