题解归档 - cf455B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf455B
• 本地来源：problems/cf455B/idea.md
• 题目链接：https://codeforces.com/contest/455/problem/B
• 原始标题：CF455B — A Lot of Games

思路

CF455B — A Lot of Games

题意

给定 $n$ 个非空字符串（总长 $\le 10^5$）。两人轮流在空串末尾追加一个字母，当前串必须是某个给定串的前缀；无法操作者输。

共进行 $k$ 局。第 $i$ 局败者先手下一局。问第 $k$ 局在双方都最优时，先手（第一局先手者）胜还是败。

思路

单局博弈

把所有串建成 Trie。节点表示当前前缀；若某节点无子节点，则轮到该位置的玩家无法走，该节点为 必败态。

自底向上 DP：

• 无儿子 → 必败
• 存在儿子为必败 → 当前必胜
• 否则必败

根节点（空串）的胜负即「单局先手是否必胜」。

多局传递

每局都在同一 Trie 根上博弈，仅先后手轮换。

设根为必胜态：

• 奇数局：原先手赢第 $k$ 局 → First
• 偶数局：原后手赢 → Second

设根为必败态：

• 每局先手都输，故第 $k$ 局胜者恒为原后手 → Second

只需判断 $k$ 奇偶（根必胜时）。

复杂度

• 建树 + DFS：$O(\text{总长度})$
• 空间：$O(\text{总长度})$

验证

• 样例 1：a,b 根有两条一步到必败叶 → 根必胜，$k=3$ 奇 → First
• 样例 3：唯一串 ab，根只能走到必胜子 a → 根必败 → Second

代码

来源：problems/cf455B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:31:54
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
ll ch[maxn+5][26],win[maxn+5],ptr,n,k,i,j,c,u,pd;
string s;
stack<pair<ll,ll>>st;
int main(){
    cin>>n>>k;
    ptr=0;
    for(i=0;i<n;i++){
        cin>>s;
        u=0;
        for(j=0;j<(ll)s.size();j++){
            c=s[j]-'a';
            if(!ch[u][c]) ch[u][c]=++ptr;
            u=ch[u][c];
        }
    }
    st.push({0,0});
    while(!st.empty()){
        u=st.top().first;
        pd=st.top().second;
        st.pop();
        if(pd==0){
            st.push({u,1});
            for(c=0;c<26;c++) if(ch[u][c]) st.push({ch[u][c],0});
        }else{
            win[u]=0;
            for(c=0;c<26;c++) if(ch[u][c] and !win[ch[u][c]]) win[u]=1;
        }
    }
    if(!win[0]) cout<<"Second\n";
    else if(k&1) cout<<"First\n";
    else cout<<"Second\n";
    return 0;
}