先定義SG函數(shù)：sg(x)=mex{ sg(y) | y是x的后繼 }

這里后繼指在游戲合法操作下所能到達(dá)的下一個狀態(tài)。

關(guān)于mex函數(shù)，簡單來說就是當(dāng)前最小的不屬于這個集合的非負(fù)整數(shù)，這里不多介紹。

一般來說，對于一個無后繼節(jié)點(diǎn)，也就是當(dāng)前無法進(jìn)行下一步操作的點(diǎn)，其sg函數(shù)值應(yīng)當(dāng)為0。

那么通過逐級向上以游戲規(guī)則遞推，就可以將各個局面的sg值給求出來，進(jìn)而求總體異或和來求出整體局面的情況，或者加一些操作求必勝方案數(shù)等。

下面介紹兩種求sg函數(shù)的板子。

1.打表法；

f數(shù)組要從小到大排序！！！

#define ll long long ll f[N],vis[N],sg[N]; void SG() {for(int i=1;i<=n;++i){for(int j=1;f[j]<=i&&j<=N;++j){//枚舉所有操作 vis[sg[i-f[j]]]=i;//這里把vis標(biāo)記為i而不是1，//是因?yàn)槊看吻髆ex函數(shù)都是對于當(dāng)前的i統(tǒng)計的每一個數(shù)出現(xiàn)的//情況，如果標(biāo)記為1，就得每次重置vis數(shù)組，而因?yàn)閕各不相同//就起到了重置的作用； }for(int j=0;j<=n;++j){if(vis[j]!=i){sg[i]=j;break;}}} }

2.dfs

s數(shù)組同樣要從小到大排序！！！

#define ll long longll s[N],sg[N];//sg函數(shù)首先初始化為-1， ll vis[N];//標(biāo)記是否存在過，同上 //N是操作總數(shù) ll SG(ll x){if(sg[x]!=-1) return sg[x];memset(vis,0,sizeof vis);for(int i=0;i<=n&&x>=s[i];++i){SG(x-s[i]);vis[sg[x-s[i]]]=1;} for(int j=0;;++j){if(!vis[j]){sg[x]=j;break;}}return sg[x]; }

?以上就是兩種求sg函數(shù)的方法，其核心思路都一樣，就是枚舉，標(biāo)記，求mex函數(shù)，只是形式有差別。

上例題

牛客 游戲

大意?

對于每一堆石子（有m個），設(shè)他要取石子數(shù)為d，那么d必須是m的約數(shù)。

無法行動者輸。

對于當(dāng)前局面，要求求出所有必勝的方法數(shù)。

解法

求出所有局面的sg值，再枚舉所有的第一步的情況，如果第一步的sg值與其對應(yīng)的所有局面的sg值異或和為0，就是合法的。這是因?yàn)槲覀円尩谝徊叫纬杀財〉木置妗?/p>

首先先打表求sg值

void init() {sg[0]=0;for(int i=1;i<=N;++i){cnt++;for(int j=1;j<=sqrt(i);++j){if(i%j==0){//可以操作 vis[sg[i-j]]=cnt;//if(j*j!=i)vis[sg[i-i/j]]=cnt;}}//mex函數(shù)求sg for(int j=0;j<=N-10;j++){if(vis[j]!=cnt){sg[i]=j;break;}}} }

對于每一個i，如果其存在因子y，則i=y*k，所以k也是i的因子。

這里我們并沒有現(xiàn)成的f數(shù)組（上文的所有操作的集合）?，只能枚舉來找到i的因子，為了省時，我們只枚舉到sqrt（i），后面的對應(yīng)的因子k就有對應(yīng)的j來找到并標(biāo)記

if(i%j==0){//可以操作?
?? ??? ??? ??? ?vis[sg[i-j]]=cnt;
?? ??? ??? ??? ?//if(j*j!=i)//這個可寫可不寫，只是規(guī)避掉了重復(fù)標(biāo)記sqrt(i)的可能? ? ? ?
?? ??? ??? ??? ?vis[sg[i-i/j]]=cnt;
?? ??? ??? ?}

然后枚舉所有的第一步

for(int i=1;i<=n;++i){num^=sg[mas[i]];ll d=sqrt(mas[i]);for(int j=1;j<=d;++j){if(mas[i]%j==0){if((sg[mas[i]-j]^num)==0){//使后手局面必敗ans++; }if(j*j!=mas[i]&&(sg[mas[i]-mas[i]/j]^num)==0) ans++;}}num^=sg[mas[i]];}

因?yàn)榈谝徊阶咄曛?#xff0c;當(dāng)前所有的局面里并不會包括第一步前的那一堆的局面，所以先用num與sg[mas[i]]進(jìn)行異或操作，將其的效果抵消，最后再將其異或一次，相當(dāng)又恢復(fù)初始局面。然后這里同樣只枚舉到sqrt(i),所以大于sqrt（i）的因子k由j推出并操作。

完整代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const ll N=1e5+10; ll n; ll sg[N]; ll vis[N]; ll cnt=0; ll mas[N]; void init() {sg[0]=0;for(int i=1;i<=N;++i){cnt++;for(int j=1;j<=sqrt(i);++j){if(i%j==0){//可以操作 vis[sg[i-j]]=cnt;//if(j*j!=i)vis[sg[i-i/j]]=cnt;}}//mex函數(shù)求sg for(int j=0;j<=N-10;j++){if(vis[j]!=cnt){sg[i]=j;break;}}} } int main() {init();cin>>n;ll num=0;for(int i=1;i<=n;++i){cin>>mas[i];num^=sg[mas[i]];} ll ans=0; for(int i=1;i<=n;++i){num^=sg[mas[i]];ll d=sqrt(mas[i]);for(int j=1;j<=d;++j){if(mas[i]%j==0){if((sg[mas[i]-j]^num)==0){//使后手局面必敗ans++; }if(j*j!=mas[i]&&(sg[mas[i]-mas[i]/j]^num)==0) ans++;}}num^=sg[mas[i]];}cout<<ans<<endl;return 0;}

寒冬信使

注意，操作只有兩種，我們只需要對對應(yīng)的操作進(jìn)行討論就可以了。

注意到字符串的長度最大也只有10，這其實(shí)是在提醒我們可以枚舉字符串的所有情況，。

所以同樣是sg函數(shù)，但是這里的局面我們用01串來狀壓表示，另w代表1，b代表0.

就得到了一個01串s。

兩種操作，第一種相當(dāng)于將s的高位1變成0，再反轉(zhuǎn)一個低位，那么s的值必定是變小的。

第二種操做同理，把1變成0，s必定變小

所以發(fā)現(xiàn)無論進(jìn)行什么操作，s的值都在變小，換句話說，如果從小到大枚舉01串，我們枚舉到一個狀態(tài)的s時，通過對s進(jìn)行操作得到的01串s‘一定是已經(jīng)求過sg值的，這就符合我們之前講的sg函數(shù)的板子了。就可以快樂敲代碼了！

//vis是一個bitset void init() {for(int i=1;i<(1<<10);++i){vis.reset();//所有位重置為0for(int j=1;j<=10;++j){if((i>>(j-1))&1){//第j位為1 if(j==1) vis[sg[i^(1<<(j-1))]]=1; //代表操作2 else{for(int k=0;k<j-1;++k){vis[sg[i^(1<<(j-1))^(1<<(k))]]=1;}}}} for(int j=0;;j++){if(!vis[j]){sg[i]=j;break;}}} }

照著題意寫即可?

然后每次輸入時，枚舉字符串的每一位得到對應(yīng)的01串的數(shù)字，討論對應(yīng)的sg函數(shù)即可

完整代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const ll mod=1e9+7; const ll N=15; inline ll read() {int X=0; bool flag=1; char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}if(flag) return X;return ~(X-1); } ll ksm(ll x,ll y,ll z){ll ans=1;while(y){if(y&1) ans=ans*x%z;x=x*x%z;y>>=1;}return ans; }ll ksc(ll x,ll y,ll z){ll ans=0;while(y){if(y&1) ans=(ans+x)%z;x=(x+x)%z;y>>=1;}return ans; } ll inv(ll x){return ksm(x,mod-2,mod); } ll w(ll x){ll cnt=0;while(x){x/=2;cnt++;}return cnt; }ll C(ll a,ll b){ ll ans=1;for(ll i=a;i>=a-b+1;i--){ans=ans*i/(a+1-i);}return ans; }char s[N]; bitset<105> vis; ll t,n; ll sg[1<<10]; void init() {memset(sg,0,sizeof sg);for(int i=1;i<(1<<10);++i){vis.reset();//所有位重置為0for(int j=1;j<=10;++j){if((i>>(j-1))&1){//第j位為1 if(j==1) vis[sg[i^(1<<(j-1))]]=1; //代表操作2 else{for(int k=0;k<j-1;++k){vis[sg[i^(1<<(j-1))^(1<<k)]]=1;}}}} for(int j=0;;j++){if(!vis[j]){sg[i]=j;break;}}} } int main() {//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//多組樣例要清空！！！init();cin>>t;while(t--){cin>>n;cin>>s;ll ans=0;for(int i=0;i<n;++i){if(s[i]=='w') ans|=(1<<i);}//構(gòu)造出對應(yīng)的01串 if(sg[ans]){cout<<"Yes"<<endl;continue;}cout<<"No"<<endl;} }

總結(jié)

以上是生活随笔為你收集整理的SG函数解析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。