CFR 455 B. A Lot of Games ( Game Theory + Trie )

Problem - 455B - Codeforces
題意：
玩連續 K 輪遊戲。每輪遊戲規則都一樣，初始時為空字串，輪流向字串結尾添加一個新的字元，操作後必須是字典中某個字的前綴。若無法進行合法的操作，則判為失敗。敗者為下一輪遊戲的先手。兩人採取最優策略爭奪第 K 輪的勝利，求先手或後手勝出。
解法：
首先建一棵 trie，計算出該遊戲支出使盤面對於先手是 必勝 / 可擇勝擇敗 / 只能任對手擇勝擇敗 / 必敗，這四種狀態中哪一個。如果是後兩者之一，那麼先手不可能得到第 K 輪的勝利。如果是第二者，則一定可以勝利。如果是第一者，則對應於 K 的奇偶性。

int N, K;
vs word;

void init(){
    cin >> N >> K;
    word = vs( N );
    for( int i = 0; i < N; ++i )
        cin >> word[ i ];
}

struct trie{
    trie *ch[ 26 ];
    trie(){
        for( int i = 0; i < 26; ++i )
            ch[ i ] = NULL;
    }
    friend void add( trie *&t, const string &s, int x ){
        if( x == s.size() )
            return;
        if( t->ch[ s[ x ] - 'a' ] == NULL )
            t->ch[ s[ x ] - 'a' ] = new trie();
        add( t->ch[ s[ x ] - 'a' ], s, x + 1 );
    }
} *root_trie;

int state; // 0 : win, 1 : controlable, 2 : uncontrolable, 3 : lose 

int dfs( const trie *t ){
    vi chstcnt( 4 ); // children state count
    for( int i = 0; i < 26; ++i ){
        if( t->ch[ i ] )
            ++chstcnt[ dfs( t->ch[ i ] ) ];
    }
    if( chstcnt[ 2 ] or ( chstcnt[ 0 ] and chstcnt[ 3 ] ) )
        return 1;
    if( chstcnt[ 3 ] )
        return 0;
    if( chstcnt[ 0 ] or ( chstcnt[ 0 ] + chstcnt[ 1 ] + chstcnt[ 2 ] + chstcnt[ 3 ] == 0 ) )
        return 3;
    return 2;
}

void preprocess(){
    root_trie = new trie();
    for( int i = 0; i < N; ++i )
        add( root_trie, word[ i ], 0 );
    state = dfs( root_trie );
}

void solve(){
    if( state == 2 or state == 3 )
        cout << "Second" << endl;
    else{
        if( state == 1 )
            cout << "First" << endl;
        else{
            if( K & 1 )
                cout << "First" << endl;
            else
                cout << "Second" << endl;
        }
    }
}