思路与算法

把所有字符串插入Trie，状态仅取决于当前前缀。维护win表示能否迫使对方本局无路可走，lose表示能否迫使自己本局无路可走。叶子win=false、lose=true；非叶子两者均按“存在某个孩子对应标记为false”递推。若根win为假，HY不能保证最后获胜；若win和lose都真，HY可控制前面各局的先手并赢最后一局；若只有win真，则胜者逐局交替，K奇数时HY获胜。

正确性说明

对Trie高度归纳，走向某孩子后交换行动方，因此存在孩子不能保证相同目标时，当前方能保证该目标，递推正确。若初始先手不能迫胜，末局无法强求胜利；若既可迫胜又可迫败，便可决定下局由谁先手，使自己获得末局优势；若只能迫胜而不能迫败，每局胜者的变化完全由局数奇偶决定。这覆盖全部根状态，得到判定公式。

复杂度

设总字符数L，字母表26。读入、节点初始化、建Trie与逆序计算总O(26L+n)，空间O(26L+n)；多组峰值由最大组决定，总工作量按所有组L累计。

易错点

完整单词若还有孩子，不代表游戏结束；只有无法添加任何合法字符才输。重复串不改变可走边。注意每局失败者成为下一局先手，输出HY或Teacher，EOF多组需清空状态。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Node {
    array<int, 26> next{};
    bool win = false, lose = false;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long K;
    while (cin >> n >> K) {
        vector<string> words(n);
        size_t total = 0;
        for (auto &s : words) {
            cin >> s;
            total += s.size();
        }
        vector<Node> trie;
        trie.reserve(total + 1);
        trie.push_back(Node());
        for (auto &s : words) {
            int u = 0;
            for (char c : s) {
                int letter = c - 'a';
                if (!trie[u].next[letter]) {
                    trie[u].next[letter] = trie.size();
                    trie.push_back(Node());
                }
                u = trie[u].next[letter];
            }
        }
        for (int u = (int)trie.size() - 1; u >= 0; u--) {
            bool leaf = true;
            for (int v : trie[u].next)
                if (v) {
                    leaf = false;
                    trie[u].win = trie[u].win || !trie[v].win;
                    trie[u].lose = trie[u].lose || !trie[v].lose;
                }
            if (leaf)
                trie[u].lose = true;
        }
        bool first = trie[0].win && (trie[0].lose || (K & 1));
        cout << (first ? "HY wins!" : "Teacher wins!") << '\n';
    }
}