模板 – SG函数

https://scut.online/p/93

每次取走的石子是b的幂次。打表暴力发现规律。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;const int MAXN=1000005;
//f[i]:可改变i状态的方式
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
vector<int> f[MAXN];
int SG[MAXN],S[MAXN];
void  getSG(int n){
    for(int i = 1; i <= n; i++){
        int l=f[i].size();
        //后继状态 最多有l 种
        for(int j=0;j<=l;j++){
            S[j]=0;
        }
        for(auto vi:f[i]){
            //vi：从i状态能取走的石子数
            S[SG[i-vi]]=1;
        }
        for(int j=0;j<=l;j++){
            if(!S[j]){
                SG[i] = j;
                break;
            }
        }
        cout<<"SG["<<i<<"]="<<SG[i]<<endl;
    }}int N=120;void enque(int id){
    ll cur=1,b=8;
    while(id>=cur){
        f[id].push_back(cur);
        cur*=b;
    }
}int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    for(int i=0;i<=N;i++){
        enque(i);
    }
    getSG(N);
}

https://scut.online/p/42

每次有1或2两种取法，直接求sg然后异或一起？鹏哥有个记忆化搜索的写法感觉更巧妙一些。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
const int MAXN=1000005;
//f[i]:可改变i状态的方式
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
vector<int> f[MAXN];
int SG[MAXN],S[MAXN];
void  getSG(int n){
    for(int i = 1; i <= n; i++){
        int l=f[i].size();
        //后继状态 最多有l 种
        for(int j=0;j<=l;j++){
            S[j]=0;
        }
        for(auto vi:f[i]){
            //vi：从i状态能取走的石子数
            S[SG[i-vi]]=1;
        }
        for(int j=0;j<=l;j++){
            if(!S[j]){
                SG[i] = j;
                break;
            }
        }
        cout<<"SG["<<i<<"]="<<SG[i]<<endl;
    }}int N=120;void enque(int id){
    if(id>=1)
        f[id].push_back(1);
    if(id>=2)
        f[id].push_back(2);
}
*/
int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    /*for(int i=0;i<=N;i++)
        enque(i);
    getSG(N);*/
    int T;
    scanf("%d",&T);
    int n,m;
    while(T--){
        scanf("%d%d",&n,&m);
        int sg=(n%3)^(m%3);
        puts(sg?"Naive is excited.":"Excited is naive.");
    }
}