AcWing893 集合-Nim(博弈论)

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

AcWing893 集合-Nim(博弈论)
#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;
}
View Code

 

AcWing893 集合-Nim(博弈论)

上一篇:docker-ce 在windows10下使用volume的注意事项


下一篇:C#字体选择框和颜色对话框