AcWing893 集合-Nim（博弈论）

如果了解sg函数，就知道如果全部相异或是0则必败，否则必胜

#include<iostream>
#include<unordered_map>
#include <unordered_set>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n,m;
int s[110];
int a[N];
int f[N];
int sg(int x){
    if(f[x]!=-1)
    return f[x];
    int i;
    unordered_set<int> m1;
    for(i=1;i<=m;i++){
        if(x>=s[i])
        m1.insert(sg(x-s[i]));
    }
    for(i=0;;i++){
        if(!m1.count(i)){
            f[x]=i;
            return f[x];
        }
    }
}
int main(){
    cin>>m;
    int i;
    for(i=1;i<=m;i++)
    cin>>s[i];
    cin>>n;
    memset(f,-1,sizeof f);
    int res=0;
    for(i=1;i<=n;i++){
        int x;
        cin>>x;
        res^=sg(x);
    }
    if(res==0)
    cout<<"No"<<endl;
    else
    cout<<"Yes"<<endl;
}