集合-Nim游戏

本题用到了递归，判断先手是否胜利的依据还是根据nim游戏中的异或，这个递归思路非常的精妙
非常值得学习！！！

首先贴上nim游戏的思路和代码
思路：

代码：

#include<iostream>
using namespace std;
int main(){
    int n;
    int m;
    cin>>n;
    int res=0;
    while(n--){
        cin>>m;

        res=res^m;
    }
    if(res){
        cout<<"Yes"<<endl;
    }
    else
    cout<<"No"<<endl;
    return 0;
}

本题思路：

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
int n,m;
const int N=110,M=1e4+10;
int s[N];//存储能取石子数
int f[M];//存储石子个数
int sg(int x){


    if(f[x]!=-1)
    return f[x];
    set<int>S;
    for(int i=0;i<n;i++){
        int sum=s[i];
        if(x>=sum)S.insert(sg(x-sum));
    }
    for(int i=0;;i++){
        if(!S.count(i))
        {
            f[x]=i;
            return i;
        }
    }
}
int main(){

    cin>>n;
    for(int i=0;i<n;i++)cin>>s[i];
    cin>>m;
    int x;
    int res=0;
    memset(f,-1,sizeof f);
    for(int i=0;i<m;i++){
        cin>>x;
        res=res^sg(x);
    }
    if(res){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    return 0;

}