7.16 D kAri427 學姐逗學弟——every-SG

427. 學姐逗學弟

時間限制 3000 ms  記憶體限制 131072 KB

題目描述

學弟們來了之後，學姐每天都非常高興的和學弟一起玩耍。這一天，學姐想出了這樣一個遊戲，她畫了一棵樹，樹上共有 n 個節點，現在學姐把 m(m≤n) 個石子随機放在節點上，每個節點可以放多個，每一次操作是指把每一個節點上的所有石子都往下移動到他某一個子節點（一個節點有多個石子可以分别移動到不同子節點），如果沒有子節點則不移動，無法移動的人輸。 學姐說，學弟是紳士應該讓學姐先走，其實學姐已經策劃好了自己一定會赢，但是這時學弟說，學姐先下那麼我來畫樹和放石子吧，學姐驚呆了。現在她來想知道在新的圖上，兩人都按最優方案走，自己還能不能赢。

輸入格式

輸入第一行為一個整數 T 表示資料組數，接下來 T 組資料，每組開頭為兩個整數 n,m ，表示節點個數和石子個數， 1≤m≤n≤100000 ，接下來一行 n−1 個整數，表示2到 n 節點的父親節點編号，接下來一行m個整數，表示每一個石子的位置。資料保證1為根節點。

輸出格式

如果學姐能勝利，輸出"MengMengDa!"，否則輸出"So sad..."。沒有引号。

輸入樣例

1
3 1
1 1
1
           

輸出樣例

MengMengDa!
           

分析：題意要求每次操作時，能移動的石子都要移動。屬于every-sg遊戲。      

EVERY-SG政策：對于自己必勝的遊戲，要讓遊戲盡可能晚的結束，對于自己必輸的遊戲，要讓遊戲盡早的結束。最後結束的遊戲，決定了雙方的輸赢。這樣，我們隻需要看最後所有單一遊戲最大的step那組的SG是0還是非0（或者是奇是偶）就可以斷定是否先手必勝了。 


    很容易得出：

    （u是v的子狀态）

    step[v] = 0；                 （v為終止狀态）

    step[v] = max{step[u]} + 1；  （sg[v]>0,sg[u]=0）

    step[v] = min{step[u]} + 1；  （sg[v]==0）




注意：對于該遊戲，我們不需要異或操作，我們隻關心每個狀态的SG是0非0，而不關心它的具體值。是以不需要具體計算mex，隻需要看其後繼狀态的SG是否存在為0.




代碼：
       
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;

vector <int> p[100010]; //p[i]儲存以i為父親節點的位置 
int step[100010];
int sg[100010];
int dp(int a)
{
    if(sg[a]>=0)
    {
        return sg[a];
    }
    if(p[a].size()==0) //如果為葉子節點，則為0 
    {					//step[v] = 0（v為終止狀态） 
        sg[a]=step[a]=0;
        return 0;
    }
    int mi=999999999,ma=0;
    for(int i=0;i<p[a].size();i++)
    {
        if(dp(p[a][i])==0)//若後繼狀态SG=0，則該點SG為1 
        {
            ma=max(ma,step[p[a][i]]);
            sg[a]=1;
        }
        else	
        {
            mi=min(mi,step[p[a][i]]);
        }
    }
    if(sg[a]==1)    //step[v] = max{step[u]} + 1；  （sg[v]>0,sg[u]=0） 
    {
        step[a]=ma+1;
        return 1;
    }
    step[a]=mi+1;	//step[v] = min{step[u]} + 1；  （sg[v]==0） 
    return sg[a]=0;
}
int main()
{
    int t,n,m,i,j,a;
    scanf("%d",&t);
    while(t--)
    {
        int ma=0,ma1=0;
        scanf("%d %d",&n,&m);
        memset(step,-1,sizeof(step));
        memset(sg,-1,sizeof(sg));
        for(i=0;i<=n;i++)
            p[i].clear();
        for(i=2;i<=n;i++)
        {
            scanf("%d",&a);
            p[a].push_back(i);
        }
        for(i=0;i<m;i++)
        {
            scanf("%d",&a);
            if(dp(a)==1)
                ma=max(ma,step[a]);
            else
                ma1=max(ma1,step[a]);
        }		//	ma1表示後手必勝遊戲中最大步數 
        if(ma>ma1)//ma表示先手必勝遊戲中最大步數 
            printf("MengMengDa!\n");
        else
            printf("So sad...\n");
    }
    return 0;
}
           
        







最後判定也可以寫成這樣：

        for(i=0;i<m;i++)
        {
            scanf("%d",&a);
  dp(a);
            ma=max(ma,step[a]);
        } 
        if(ma%2==1)
            printf("MengMengDa!\n");
        else
            printf("So sad...\n");