Games

CF#260 B. A Lot of Games

传送门

Description

有两个人在玩游戏，一共玩 $k(1\le k \le 10^9)$轮，每一轮的一开始有一个空串，双方每一回合需要在空串后面加一个字符，但必须要满足加完这个字符之后的字符串是给定大小为 $n(1\le n\le 10^5)$ 的母串集合中任意一个串的前缀，不能操作者输，规定第一轮的先手为第一个人，接下来每一轮的先手为上一轮的输家，规定最终的赢家是第 $k$ 轮的赢家，在双方都采取最优策略的情况下，求最终的赢家是第一轮的先手还是后手.

Solution

先单独考虑每一轮的游戏，发现本质上就是对母串建 Trie 树并在 Trie 树上每次向下移动，不能移动的输

所以可以先 dp 出对于 Trie 树上每一个节点，能获得的最终状态是怎样的.

观察发现，如果一个位置往下走既可以到必胜态又可以必败态，那么就可以通过这个位置控制下一局的先后手

进一步发现，如果某一方既可以必胜又可以必败，那么其必然能获得最终的胜利.

考虑如果子游戏中不存在这样的状态，那么如果先手必败则后手赢，如果先手必胜则胜负由 k 的奇偶性决定.

所以只需要 dp 记录维护 4 种值，分别表示 (能必胜，能必败，既能必胜又能必败，什么都不能)，枚举后继的状态转移

Code

char s[maxn];
int ch[maxn][30], f[maxn], k , n, tot;
void insert(char *s){
    int p = 1, len = strlen(s);
    for(int i = 0; i < len; i++){
        int c = s[i] - 'a';
        if(!ch[p][c]) ch[p][c] = ++tot;
        p = ch[p][c];
    }
}
constexpr int win = 1, lose = 2, allcan = 3, neither = 4;
int main()
{
    close;
    tot = 1;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> s;
        insert(s);
    }
    // cout << "fuck " << endl;
    function<void (int)> dfs = [&](int u){
        f[u] = lose;
        int Win = 0, Lose = 0, All = 0;
        for(int c = 0; c < 26; c++){
            if(ch[u][c]){
                int v = ch[u][c] ;
                dfs(v);
                All++;
                if(f[v] == lose) Win = 1;
                if(f[v] == win) Lose = 1;
                if(f[v] == neither) {
                    return f[u] = allcan, void();
                }
            }
        }
        if(Win && Lose) {
            return f[u] = allcan, void();
        }
        if(!Win && !Lose && All) {
            return f[u] = neither, void();
        }
        if(Win)f[u] = win;
        if(Lose) f[u] = lose;
    };
    dfs(1);
    if(f[1] == 3) {
        cout << "First" << endl;return 0;
    }
    if(f[1] == 2 || f[1] == 4) {
        cout << "Second" << endl;
        return 0;
    }
    cout << ((k & 1)?"First":"Second") << endl;
    return 0;
}