把字符串集合建成 Trie,在树上自底向上求先手「能否强行赢本轮」与「能否强行输本轮」两个布尔量,再按 k 的奇偶给出答案。
OJ: roj
题目 ID: 1819
难度:普及+/提高-
标签:Trie博弈论树形DPpython
创建: 2026-10-08 06:41
更新: 2026-10-08 06:41
形式化题目
给定
- 从空串开始,两人轮流在末尾追加一个字符;
- 追加后得到的串必须是
中某个串的前缀(空串本身也算合法前缀); - 轮到自己却无法追加的人输掉本轮。
第 1 轮由「第一轮先手」开始,此后每一轮由上一轮的输家先手;第 HY wins! 或 Teacher wins!。
规模:
正解
思路
第一步:把加字符的过程换成在 Trie 上走。
所有可以出现的串(
第二步:注意到多轮游戏的接力规则会翻转「赢」的价值。
对 Trie 上任意节点
:从 出发的这个人,是否存在一种策略,无论对手怎么应对都能强行赢下本轮; :从 出发的这个人,是否存在一种策略,无论对手怎么应对都能强行输掉本轮。
第三步:树形 DP 求这两个量。
设
-
叶子(
):轮到的人无路可走,本轮已经输定了,因此 , 。 这里最容易踩坑:「叶子」是 Trie 上没有子节点的点,不是某个串的结尾点。比如
,节点 a虽然是一个串的结尾,但它在 Trie 上还有儿子,游戏完全可以继续加b,所以它不是叶子。 -
内部节点:走一步到
后,轮到对手在 处行棋。要强行赢,就必须存在一个子节点 让对手无法强行赢;要强行输,就必须存在一个子节点 让对手无法强行输(对手无法强输,意味着他被迫赢,于是输的就是我):
两个转移互相独立,各自只用到子节点的同名量,所以一次自底向上的遍历就能同时算出。
第四步:把根节点的两个量翻译成
记
| 情况 | 第 1 轮先手的结局 |
|---|---|
| 无论怎么下,对手都有强赢策略;每轮先手都必输,输者又成为下一轮先手 → 先手连输 |
|
| 前 |
|
| 先手只能赢,于是每轮都是先手的一方获胜,胜负严格交替 → |
用三组样例各验证一支:
-
1 2 / ab:Trie 是根 -a-> A -b-> B,B是叶子(),于是 A(有子B),根 —— 命中第一行,输出 Teacher wins!。 -
2 3 / a, b:根有两个子节点,且两个都是叶子,、 —— 命中第三行, 为奇,输出 HY wins!。 -
3 2 / ab, ac, b:根的b子节点是叶子,a子节点有b、c两个叶子儿子。于是叶子、 a处一算,根处 (走 b,对手无路可走)、(走 a,对手在a上有两个叶子,被迫赢)—— 命中第二行,取什么都输出 HY wins!,也不例外。这正是「能输」比「能赢」多出来的那一半信息:先手第一轮可以故意输掉,第二轮再赢回来。 对照组
2 2 / a, bcd则属第三行:节点b只有一条单链b-c-d,长度固定,先手想输做不到(),所以 时输出 Teacher wins!。两条数据只差「有没有一条深度可控的分支」,结论正好相反。
为什么不需要枚举
代码
#!/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()/**
* 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 为
总结
本题的教学价值集中在「注意第二维状态」。第一眼的直觉是算单轮的胜负态就够,于是很容易只维护
两个实现细节值得固定下来:其一,叶子的判据是 Trie 上无子节点,而不是「是某个串的结尾」;其二,dfs 与 Python 的递归都会爆栈。多组数据时把节点计数和子节点数组整体重置,不要靠局部变量残留。
数据说明
本题素材(content.md / data/)来自题库重建,目录内附带了数据生成脚本,说明