字符串游戏

GitHub跳转原题关系图返回列表

把字符串集合建成 Trie,在树上自底向上求先手「能否强行赢本轮」与「能否强行输本轮」两个布尔量,再按 k 的奇偶给出答案。

OJ: roj

题目 ID: 1819

难度:普及+/提高-

标签:Trie博弈论树形DPpython

创建: 2026-10-08 06:41

更新: 2026-10-08 06:41

形式化题目

给定 nn 个只含小写字母的字符串的集合 SS,以及轮数 kk。游戏进行 kk 轮,每轮的过程相同:

  • 从空串开始,两人轮流在末尾追加一个字符;
  • 追加后得到的串必须是 SS 中某个串的前缀(空串本身也算合法前缀);
  • 轮到自己却无法追加的人输掉本轮。

第 1 轮由「第一轮先手」开始,此后每一轮由上一轮的输家先手;第 kk 轮的胜者赢得整个游戏。双方都最优决策,问第一轮先手能否获胜。多组数据读到文件结尾,每组输出一行 HY wins! 或 Teacher wins!。

规模:1⩽n⩽1051 \leqslant n \leqslant 10^5,1⩽k⩽1091 \leqslant k \leqslant 10^9,每组字符串长度之和不超过 10510^5,数据组数不超过 1010。

正解

思路

第一步:把加字符的过程换成在 Trie 上走。

所有可以出现的串(SS 中每个串的所有前缀)恰好就是 SS 的 Trie 里的节点:根是空串,从节点 uu 沿字符 cc 走到 vv,等价于在串尾追加字符 cc。于是单轮游戏就是:从根出发,两人轮流沿一条树边往下走,走到叶子的人赢(因为对手下一步无路可走)。这是一张有向无环图,每轮游戏必然在有限步内结束,不存在平局。

第二步:注意到多轮游戏的接力规则会翻转「赢」的价值。

kk 轮的连接方式是「输者下一轮先手」。也就是说赢下第 rr 轮是要付出代价的:第 r+1r+1 轮你就变成了后手。反过来说,「第 1 轮的先手」这个身份是可以一直握在手里的——只要他在前 k−1k-1 轮里故意输。于是单轮里「想赢」和「想输」这两种能力都要算,不能只算传统的胜负态。

对 Trie 上任意节点 uu(轮到在 uu 处行棋的人视角),定义两个独立的布尔量:

  • win(u)\mathrm{win}(u):从 uu 出发的这个人,是否存在一种策略,无论对手怎么应对都能强行赢下本轮;
  • lose(u)\mathrm{lose}(u):从 uu 出发的这个人,是否存在一种策略,无论对手怎么应对都能强行输掉本轮。

lose\mathrm{lose} 的定义听起来别扭,但它是完全对称的:它就是「把同一个游戏当成我的目标」求必胜,只是把"我赢"换成"我输"。

第三步:树形 DP 求这两个量。

设 uu 的子节点为 v1…vmv_1 \dots v_m。

  • 叶子(m=0m = 0):轮到的人无路可走,本轮已经输定了,因此 win(u)=false\mathrm{win}(u) = \text{false},lose(u)=true\mathrm{lose}(u) = \text{true}。

    这里最容易踩坑:「叶子」是 Trie 上没有子节点的点,不是某个串的结尾点。比如 S={a,ab}S = \{\texttt{a}, \texttt{ab}\},节点 a 虽然是一个串的结尾,但它在 Trie 上还有儿子,游戏完全可以继续加 b,所以它不是叶子。

  • 内部节点:走一步到 vv 后,轮到对手在 vv 处行棋。要强行赢,就必须存在一个子节点 vv 让对手无法强行赢;要强行输,就必须存在一个子节点 vv 让对手无法强行输(对手无法强输,意味着他被迫赢,于是输的就是我):

win(u)=⋁i=1m¬win(vi),lose(u)=⋁i=1m¬lose(vi).\mathrm{win}(u) = \bigvee_{i=1}^{m} \neg \mathrm{win}(v_i), \qquad \mathrm{lose}(u) = \bigvee_{i=1}^{m} \neg \mathrm{lose}(v_i).

两个转移互相独立,各自只用到子节点的同名量,所以一次自底向上的遍历就能同时算出。

第四步:把根节点的两个量翻译成 kk 轮的结果。

记 W=win(root)W = \mathrm{win}(\text{root}),L=lose(root)L = \mathrm{lose}(\text{root})。注意 Trie 每轮都一样,所以「身为先手时的 W,LW, L」对所有轮都适用。

情况 第 1 轮先手的结局
W=falseW = \text{false} 无论怎么下,对手都有强赢策略;每轮先手都必输,输者又成为下一轮先手 → 先手连输 kk 轮,必败
W=true,  L=trueW = \text{true},\; L = \text{true} 前 k−1k-1 轮故意输(把先手权牢牢留在自己手里),第 kk 轮改用强赢策略 → 任意 kk 必胜
W=true,  L=falseW = \text{true},\; L = \text{false} 先手只能赢,于是每轮都是先手的一方获胜,胜负严格交替 → kk 为奇数必胜、kk 为偶数必败

用三组样例各验证一支:

  • 1 2 / ab:Trie 是 根 -a-> A -b-> B,B 是叶子(win=0,lose=1\mathrm{win}=0,\mathrm{lose}=1),于是 A(有子 B)win=1,lose=0\mathrm{win}=1,\mathrm{lose}=0,根 win=0\mathrm{win}=0 —— 命中第一行,输出 Teacher wins!。

  • 2 3 / a, b:根有两个子节点,且两个都是叶子,win(root)=¬0=1\mathrm{win}(\text{root}) = \neg 0 = 1、lose(root)=¬1=0\mathrm{lose}(\text{root}) = \neg 1 = 0 —— 命中第三行,k=3k=3 为奇,输出 HY wins!。

  • 3 2 / ab, ac, b:根的 b 子节点是叶子,a 子节点有 b、c 两个叶子儿子。于是叶子 lose=1\mathrm{lose}=1、a 处 win=lose=0\mathrm{win}=\mathrm{lose}=0 一算,根处 win=1\mathrm{win}=1(走 b,对手无路可走)、lose=1\mathrm{lose}=1(走 a,对手在 a 上有两个叶子,被迫赢)—— 命中第二行,kk 取什么都输出 HY wins!,k=2k=2 也不例外。这正是「能输」比「能赢」多出来的那一半信息:先手第一轮可以故意输掉,第二轮再赢回来。

    对照组 2 2 / a, bcd 则属第三行:节点 b 只有一条单链 b-c-d,长度固定,先手想输做不到(lose(root)=0\mathrm{lose}(\text{root})=0),所以 k=2k=2 时输出 Teacher wins!。两条数据只差「有没有一条深度可控的分支」,结论正好相反。

为什么不需要枚举 kk 轮? 因为单轮结构在每轮完全相同,玩家的能力集只有「能赢 / 不能赢」与「能输 / 不能输」四种组合,而多轮的接力规则只按「谁是先手」翻面。上面三行把 kk 轮的走向一次性穷尽了,所以 kk 只以奇偶性进入答案,k⩽109k \leqslant 10^9 也无需模拟。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 06:41
# update_at: 2026-10-08 06:41

import sys
from collections.abc import Iterator

HY = 'HY wins!'
TEACHER = 'Teacher wins!'

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Trie = list[dict[int, int]]  # ch[u][字符] = 子节点编号,节点 u 代表某个前缀,0 号是空串根
type RootAbility = tuple[bool, bool]  # 根节点的 (先手能否强行赢本轮, 先手能否强行输本轮)


def read_groups(tokens: Iterator[bytes]) -> Iterator[tuple[int, list[bytes]]]:
    """按 EOF 逐组产出 (轮数 k, 这一组的 n 个串);n 只用来切出这一组的串。"""
    while (head := next(tokens, None)) is not None:
        n, k = int(head), int(next(tokens))
        yield k, [next(tokens) for _ in range(n)]


def build_trie(words: list[bytes]) -> Trie:
    """把所有串插进 Trie,返回 ch[u] = {字符: 子节点编号}。"""
    ch: Trie = [{}]
    for s in words:
        cur = 0
        for c in s:  # bytes 迭代出的是字符的 ASCII 码,直接当字典键
            nxt = ch[cur].get(c)
            if nxt is None:
                ch.append({})
                nxt = len(ch) - 1
                ch[cur][c] = nxt
            cur = nxt
    return ch


def root_ability(ch: Trie) -> RootAbility:
    """自底向上求根节点的两维能力:能否强行赢、能否强行输。"""
    order: list[int] = []
    stack = [0]
    while stack:  # 迭代式先序遍历,避免 1e5 深链时超递归深度
        u = stack.pop()
        order.append(u)
        stack.extend(ch[u].values())

    win = bytearray(len(ch))  # win[u]:轮到 u 处行棋的人能否强行赢下本轮
    lose = bytearray(len(ch))  # lose[u]:同上,能否强行输掉本轮(把先手权让出去)
    for u in reversed(order):  # 先序的逆序 = 每个点都排在它的子节点之后
        if not ch[u]:  # 叶子:轮到的人无路可走,本轮已经输了
            lose[u] = 1
            continue
        kids = ch[u].values()
        win[u] = any(not win[v] for v in kids)   # 走到对手无法强赢的点
        lose[u] = any(not lose[v] for v in kids)  # 走到对手无法强输的点(对手只能赢,于是自己输)
    return bool(win[0]), bool(lose[0])


def verdict(k: int, ability: RootAbility) -> str:
    """把根节点的两维能力和轮数 k 翻译成最终胜者。"""
    win, lose = ability
    if not win:  # 一轮也赢不了:输者仍是下一轮先手,Teacher 连赢 k 轮
        return TEACHER
    if lose:  # 可自选胜负:先连输 k-1 轮保持先手,最后一轮赢
        return HY
    return HY if k % 2 else TEACHER  # 只能赢不能输:胜负交替,只看 k 的奇偶


def solve() -> None:
    out: list[str] = []
    for k, words in read_groups(iter(sys.stdin.buffer.read().split())):
        out.append(verdict(k, root_ability(build_trie(words))))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 06:41
 * update_at: 2026-10-08 06:41
 */

// 1819《字符串游戏》:把「轮流在末尾加字符、只能保持是某个串的前缀」看成在 Trie 上走一条根到叶的路径,
// 于是单轮就是一个「走到叶子的人赢(走不动的人输)」的无环博弈。
// 多轮的关键是:某一轮的输家成为下一轮的先手,所以「能不能故意输」和「能不能赢」一样重要。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int SIGMA = 26;       // 字符集只有小写字母
const int MAXNODE = 100005; // 每组数据「所有串长度之和」≤ 1e5,Trie 节点数 ≤ 总和 + 1

struct Node {
    int ch[SIGMA]; // 子节点编号,-1 表示这条转移不存在
    bool can_win;  // 轮到 u 处行棋的人,能否强行赢下本轮
    bool can_lose; // 轮到 u 处行棋的人,能否强行输掉本轮(即主动把先手权让给对方)
};

Node trie_node[MAXNODE]; // 动态化静态:trie_node[u] 就是编号 u 的节点,0 号是根(空串)
int node_cnt;            // 已开出的节点数(根算第 0 个)

int order[MAXNODE];     // 先序遍历序列(父一定排在子之前),逆序就是自底向上的处理顺序
int stack_buf[MAXNODE]; // 手写栈,避免 1e5 深链时递归爆栈

// 清空 Trie,只留下代表空串的根节点
void trie_init() {
    node_cnt = 0;
    trie_node[0].can_win = false;
    trie_node[0].can_lose = false;
    for (int c = 0; c < SIGMA; c++) trie_node[0].ch[c] = -1;
}

// 新开一个 Trie 节点(动态开点),返回它的编号
int new_node() {
    node_cnt++;
    trie_node[node_cnt].can_win = false;
    trie_node[node_cnt].can_lose = false;
    for (int c = 0; c < SIGMA; c++) trie_node[node_cnt].ch[c] = -1;
    return node_cnt;
}

// 把一个字符串插入 Trie
void trie_insert(const string &s) {
    int cur = 0;
    for (char c : s) {
        int x = c - 'a';
        if (trie_node[cur].ch[x] == -1) trie_node[cur].ch[x] = new_node();
        cur = trie_node[cur].ch[x];
    }
}

// 自底向上算出每个节点的 can_win / can_lose,结果留在全局的 trie_node 里
void dfs_dp() {
    // 迭代式先序遍历:先把父压进序列,再压子,保证父一定先于子出现
    int top = 0, cnt = 0;
    stack_buf[top++] = 0;
    while (top > 0) {
        int u = stack_buf[--top];
        order[cnt++] = u;
        for (int c = 0; c < SIGMA; c++)
            if (trie_node[u].ch[c] != -1) stack_buf[top++] = trie_node[u].ch[c];
    }

    // 逆序处理:任意节点的所有子节点都排在它前面,天然是自底向上
    for (int i = cnt - 1; i >= 0; i--) {
        int u = order[i];
        bool is_leaf = true;
        for (int c = 0; c < SIGMA; c++) {
            int v = trie_node[u].ch[c];
            if (v == -1) continue;
            is_leaf = false;
            // 走到一个「对手无法强赢」的点,本轮就由自己赢
            if (!trie_node[v].can_win) trie_node[u].can_win = true;
            // 走到一个「对手无法强输」的点,对手只能赢,于是本轮由自己输
            if (!trie_node[v].can_lose) trie_node[u].can_lose = true;
        }
        // 叶子:轮到的人无路可走,本轮已经输了 —— 所以「想赢」做不到,「想输」天生成立
        if (is_leaf) trie_node[u].can_lose = true;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, k;
    while (cin >> n >> k) { // 多组数据,读到 EOF
        trie_init();

        string s;
        for (ll i = 0; i < n; i++) {
            cin >> s;
            trie_insert(s);
        }

        dfs_dp();
        bool can_win = trie_node[0].can_win;
        bool can_lose = trie_node[0].can_lose;

        if (!can_win) {
            // 先手一轮也赢不了:每轮的输者都还是先手,Teacher 连赢 k 轮
            cout << "Teacher wins!\n";
        } else if (can_lose) {
            // 先手可自选胜负:前 k-1 轮故意输(下一轮仍自己先手),第 k 轮再赢
            cout << "HY wins!\n";
        } else {
            // 先手只能赢不能输:胜负严格交替,看最后一轮 k 的奇偶
            cout << (k % 2 == 1 ? "HY wins!\n" : "Teacher wins!\n");
        }
    }
    return 0;
}

复杂度

建 Trie 为 O(∑∣S∣)O(\sum |S|)。DP 用先序遍历的逆序代替递归后序(∣S∣|S| 可达 10510^5,深链会爆递归栈),每个节点扫 2626 条转移,总时间 O(26∑∣S∣)O(26 \sum |S|);节点数不超过 ∑∣S∣+1\sum |S| + 1,空间 O(26∑∣S∣)O(26 \sum |S|),两组数据间清空 Trie 即可复用。1010 组数据、每组 10510^5 字符时总量约 10610^6,时限 1000 ms1000\text{ ms} 下余量很大。

总结

本题的教学价值集中在「注意第二维状态」。第一眼的直觉是算单轮的胜负态就够,于是很容易只维护 win\mathrm{win}。但多轮接力规则把「赢一轮」变成了——下一轮让出先手权的代价,因此一个只会赢不会输的玩家会被迫和对手交替获胜,kk 的奇偶直接决定生死。补上 lose(u)=⋁¬lose(v)\mathrm{lose}(u) = \bigvee \neg \mathrm{lose}(v) 这一维后,三行判定就覆盖了全部情况,kk 从 10910^9 退化成一次取奇偶。

两个实现细节值得固定下来:其一,叶子的判据是 Trie 上无子节点,而不是「是某个串的结尾」;其二,10510^5 级别深链必须用迭代遍历,C++ 的 dfs 与 Python 的递归都会爆栈。多组数据时把节点计数和子节点数组整体重置,不要靠局部变量残留。

数据说明

本题素材(content.md / data/)来自题库重建,目录内附带了数据生成脚本,说明 1010 个测试点是按题面自造的而非官方原件;题面与 Codeforces 455B A Lot of Games 的叙述和样例完全一致,可视为同源经典题,但出题意图与官方原题仍可能有偏差。本解法的正确性以三组样例 + 全部 1010 个自造点为准,并另写了 kk 轮 Minimax 暴力在小规模随机数据上对拍验证。