Nim游戏

#include<cstdio>

using namespace std;

int main()
{
    int a=0;
    int n,m;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&m);
        a^=m;
    }
    if(a)   puts("Yes");
    else    puts("No");
    return 0;
}

台阶Nim

#include<cstdio>

using namespace std;

int main()
{
    int n; 
    scanf("%d",&n);
    int a,res=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        if(i&1) res^=a;
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

集合Nim

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>

using namespace std;

const int N=105,M=1e4+5;
int sg[M],s[N];
int n,k;

int Sg(int m)
{
    if(~sg[m])  return sg[m];
    set<int> S;
    for(int i=1;i<=k;i++)
    {
        if(m<s[i])  break;
        S.insert(Sg(m-s[i]));
    }
    for(int i=0; ; i++)
        if(!S.count(i))
            return sg[m]=i;
}

int main()
{
    cin>>k;
    for(int i=1;i<=k;i++)
        scanf("%d",&s[i]);
    sort(s+1,s+1+k);
    memset(sg,-1,sizeof sg);
    cin>>n;
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int cnt;
        scanf("%d",&cnt);
        res^=Sg(cnt);
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

拆分Nim

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>

using namespace std;

const int N=105;
int sg[N];

int Sg(int x)
{
    if(~sg[x])  return sg[x];
    set<int> S;
    for(int i=x-1;~i;i--)
        for(int j=i;~j;j--)
        S.insert(Sg(i)^Sg(j));
    for(int i=0;;i++)
        if(!S.count(i))
            return sg[x]=i;
}

int main()
{
    memset(sg,-1,sizeof sg);
    int n;
    cin>>n;
    int a,res=0;
    while(n--)
    {
        scanf("%d",&a);
        res^=Sg(a);
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}