Codeforces Trie 三题从字符串博弈到最大异或与动态 MEX

Trie 常被翻译成字典树，但“存一批单词”只是它最直观的外观。更本质的理解是：把所有对象按前缀合并，并在每一层只保留下一步可能走向哪里。 前缀可以是字符，也可以是整数从高到低的二进制位。

这一篇用三道题逐步改变“沿前缀走”的目标：先在字符 Trie 上做胜负博弈，再维护一个可增删的二进制多重集合，最后在整体异或不断累积时寻找最小缺失值。重点不是背三个模板，而是分清节点摘要、逐层贪心成立的条件，以及重复元素是否应该计数。

三道题分别多要求什么

题名、难度、标签与约束于 2026-10-04 通过 Codeforces 官方题目页核对。下表只概括算法任务，不复刻题面叙事。

题目与官方入口	难度	主要约束	Trie 中保存什么
455B A Lot of Games	1900	n ≤ 10^5，k ≤ 10^9；总字符数 ≤ 10^5	26 个字符后继、两类胜负状态
706D Vasiliy’s Multiset	1800	q ≤ 2×10^5，1 ≤ x ≤ 10^9	0/1 后继、经过节点的出现次数
842D Vitya and Strange Lesson	2000	n,m ≤ 3×10^5，0 ≤ a_i,x ≤ 3×10^5	0/1 后继、子树中的不同值数量

题号	官方标签
455B	dfs and similar、dp、games、implementation、strings、trees
706D	binary search、bitmasks、data structures、trees
842D	binary search、data structures

官方标签说明可能用到的思想，并不要求实现逐项对应。本篇三份程序都只使用确定性数组 Trie。

Trie 压缩的是共同决策前缀

把单词 ab、ac、b 插入 Trie 时，ab 与 ac 的第一个字符相同，所以共用根到 a 的边；到第二层才分叉。节点不必保存整段前缀，因为从根走来的边已经唯一确定它。

  flowchart TD
  R["根：空前缀"] --> A["a"]
  R --> B["b"]
  A --> AB["ab"]
  A --> AC["ac"]
  AB --> X["无后继"]
  AC --> Y["无后继"]
  B --> Z["无后继"]

如果对象是非负整数，就把“下一个字符”换成“下一位”。从最高位向最低位建二进制 Trie 后，同一子树中的数具有相同高位前缀。于是很多目标都能逐位决定：高位一旦更优，低位怎样变化都无法推翻它。

但三题需要的节点摘要不同：

任务	节点摘要	为什么足够
字符串博弈	当前行动者能否达到两种终局	后续只取决于可走的孩子状态
动态最大异或	子树内元素出现次数	删除后要判断分支是否仍有元素
异或后 MEX	子树内不同值数量	要判断一个完整值域是否已经填满

这也是使用 Trie 前最重要的问题：共享前缀之后，未来查询究竟需要知道数量、最值、终止标记，还是某种动态规划状态？

第一题 455B：一套胜负状态不够

两名玩家从空串开始轮流追加字符，追加后仍须是至少一个给定字符串的前缀。无法继续的人输掉这一局。共进行 k 局，上一局的失败者在下一局先手，最终只看第 k 局的胜者。

单局游戏天然落在字符 Trie 上：当前字符串就是一个节点，可选操作就是走向某个孩子，叶子表示无路可走。若只问一局，常规状态 win[v] 已经足够：

叶子没有合法操作，所以 win[v]=false；
非叶节点只要存在一个孩子 u 满足 win[u]=false，当前玩家就能把对手送进必败态，因此 win[v]=true。

问题在于多局之间由失败者取得下一局先手。仅知道普通单局的胜负，不足以描述“输掉当前局，反而取得下一局先手”的情况。还要对同一棵树计算第二个终局条件 lose[v]：把叶子视为 true，其余节点仍执行 存在孩子 u 使 !lose[u]。它表示在“无法移动者获胜”的反向终局规则下，当前行动者是否必胜。

两套状态分别对应两种终局收益；每一套都假设对手尽力阻止当前玩家的目标。后面会证明，多局之间的衔接恰好只需要这两种叶子取值。

  flowchart TD
  A["从叶子向根计算"] --> B["win：叶子为 false"]
  A --> C["lose：叶子为 true"]
  B --> D["父状态 = 存在一个取反后为真的孩子"]
  C --> D
  D --> E{"根的 win / lose"}
  E -->|"false / 任意"| F["多局状态始终为 false"]
  E -->|"true / true"| G["多局状态始终为 true"]
  E -->|"true / false"| H["多局状态交替：看 k 奇偶"]

三种根状态怎样决定答案

`win[root]`	`lose[root]`	结论
false	任意	第一局先手必败，之后也无法扭转最终控制，输出 `Second`
true	true	剩余局数怎样变化，根状态都为真，输出 `First`
true	false	多局根状态随局数交替；k 为奇数时 `First`，否则 `Second`

win=false 时，无论 lose 是真是假都输出 Second，因此不必再拆分这两种情况。

以只有字符串 ab 为例，每局必走两步，先手无法继续而输掉该局；失败者下一局仍先手，所以初始先手每局都会输。只有字符串 a 时则相反：每局先手都赢，失败者接任下一局先手，最终胜者才随 k 的奇偶交替。

手算字符串集合	根的 win	根的 lose	k=1	k=2	k=3
`{ab}`	false	true	Second	Second	Second
`{a}`	true	false	First	Second	First
`{a, bb}`	true	true	First	First	First

正确性证明

对节点到叶子的最大距离做归纳。叶子无合法移动，第一套终局取值为假，第二套终局取值为真，符合定义。假设所有孩子状态正确，当前玩家选择一个孩子后双方身份交换，所以该选择能达到目标，当且仅当孩子状态为假；存在至少一个这样的选择时父状态为真。因此两套递推都正确。

再令 F(t) 表示从根开始、还有 t 局时，当前先手能否保证赢得最后一局。只有一局时，F(1)=win[root]。当 t>1，本局走到叶子后，无法移动的人输掉本局，但他会成为下一局先手，所以这个叶子对“当前行动者”的最终收益恰好是 F(t−1)。

如果 F(t−1)=false，所有叶子取 false，整棵树的计算就是 win；如果 F(t−1)=true，所有叶子取 true，计算就是 lose。因此有精确递推：

F(t) = F(t−1) ? lose[root] : win[root]。

由此可得：win 为 false 时 F 始终为 false；win、lose 均为 true 时 F 始终为 true；win 为 true 且 lose 为 false 时 F 从 true 开始交替。这证明了上表三种结论，无需模拟最多十亿局。

完整 C++17 实现

#include <array>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Node {
    array<int, 26> next{};
    bool win = false;
    bool lose = false;
    Node() { next.fill(-1); }
};

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

    int n;
    long long k;
    cin >> n >> k;
    vector<Node> trie(1);
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int node = 0;
        for (char ch : s) {
            int edge = ch - 'a';
            if (trie[node].next[edge] == -1) {
                trie[node].next[edge] = static_cast<int>(trie.size());
                trie.emplace_back();
            }
            node = trie[node].next[edge];
        }
    }

    for (int node = static_cast<int>(trie.size()) - 1; node >= 0; --node) {
        bool leaf = true;
        for (int child : trie[node].next) {
            if (child == -1) continue;
            leaf = false;
            trie[node].win = trie[node].win || !trie[child].win;
            trie[node].lose = trie[node].lose || !trie[child].lose;
        }
        if (leaf) trie[node].lose = true;
    }

    if (!trie[0].win) cout << "Second\n";
    else if (trie[0].lose) cout << "First\n";
    else cout << (k % 2 == 1 ? "First\n" : "Second\n");
}

孩子只会在父节点之后创建，编号必然大于父节点。因此按编号逆序处理，就能先计算孩子再计算父亲，避免长度十万的链导致递归栈溢出。直接扫描数组的时间为 O(S·|Σ|)，其中 S 是总字符数、|Σ|=26；空间 O(S·|Σ|)。保存实际孩子列表也可以把状态计算写成 O(S)。

边界与错误	正确处理
一个字符串是另一个的前缀	到达单词结尾不能主动停止；有后继就仍可走
k 可达 10^9	只需要奇偶，不模拟 k 局
只算一套 `win`	无法区分终局奇偶是否可控
把重复单词建成重复分支	Trie 边应复用；重复字符串不增加新操作

第二题 706D：动态多重集合需要计数

集合初始含有 0，之后支持插入一个数、删除一次出现、查询 x xor y 的最大值。若每次查询遍历整个集合，最坏会达到 O(q²)。排序结构也不容易直接比较异或大小，因为普通数值顺序与异或后的顺序不同。

从第 30 位到第 0 位建立二进制 Trie。查询 x 时，在当前位 b 上优先走与 x 的该位相反的分支，这会让答案的第 b 位变成 1。若相反分支没有仍存活的元素，才走相同分支。

为什么逐位贪心正确

假设更高位已经固定。两个候选答案第一次不同的位置是 b，那么第 b 位为 1 的答案至少比第 b 位为 0 的答案大 2^b，而所有更低位之和最多为 2^b−1。因此只要相反分支中还有元素，高位得到 1 永远优于放弃它换取任意低位组合。

  flowchart TD
  A["从最高位读取 x 的当前位 b"] --> B{"相反位分支计数 > 0 吗"}
  B -->|"是"| C["走相反分支，答案该位写 1"]
  B -->|"否"| D["走相同分支，答案该位写 0"]
  C --> E{"还有更低位吗"}
  D --> E
  E -->|"有"| A
  E -->|"无"| F["得到最大异或值"]

删除让问题从普通集合变成多重集合。不能删掉一条共享路径，因为其他数可能仍经过它；也不能只记“节点存在”，因为同一个数可插入多次。每个节点保存经过它的当前元素出现次数，插入沿路加一，删除沿路减一，查询只走计数为正的孩子。

当前集合	查询 x=3	候选异或值
0, 1, 6, 8, 9, 11	3 xor 0	3
同上	3 xor 6	5
同上	3 xor 8	11
同上	3 xor 9	10
同上	3 xor 11	8

最高位选择首先把 8、9、11 留在候选中，后续再逐位细分，最终得到 11。这个过程从未需要知道完整排序。

完整 C++17 实现

#include <array>
#include <iostream>
#include <vector>
using namespace std;

struct Node {
    array<int, 2> next{-1, -1};
    int count = 0;
};

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

    int q;
    cin >> q;
    vector<Node> trie(1);
    trie.reserve((q + 1) * 31);

    auto update = [&](int value, int delta) {
        int node = 0;
        trie[node].count += delta;
        for (int bit = 30; bit >= 0; --bit) {
            int edge = (value >> bit) & 1;
            if (trie[node].next[edge] == -1) {
                trie[node].next[edge] = static_cast<int>(trie.size());
                trie.push_back(Node{});
            }
            node = trie[node].next[edge];
            trie[node].count += delta;
        }
    };

    auto maximumXor = [&](int value) {
        int node = 0;
        int answer = 0;
        for (int bit = 30; bit >= 0; --bit) {
            int edge = (value >> bit) & 1;
            int wanted = edge ^ 1;
            int child = trie[node].next[wanted];
            if (child != -1 && trie[child].count > 0) {
                answer |= 1 << bit;
                node = child;
            } else {
                node = trie[node].next[edge];
            }
        }
        return answer;
    };

    update(0, 1);
    while (q--) {
        char operation;
        int x;
        cin >> operation >> x;
        if (operation == '+') update(x, 1);
        else if (operation == '-') update(x, -1);
        else cout << maximumXor(x) << '\n';
    }
}

每次操作固定检查 31 位，时间 O(31q)，最坏新增 O(31q) 个节点。题目保证删除前该值存在，且 0 始终保留，因此查询时相同分支一定有路可走。

常见错误	后果
删除时把孩子指针改成 −1	破坏与其他数共享的前缀
节点只记布尔存在	重复插入后删除一次会误判为空
从低位开始贪心	低位收益可能牺牲更重要的高位
位宽不足或移位到符号位	本题处理 29..0 已足够；代码统一用 30..0，避免对有符号 int 执行 `1 << 31`

第三题 842D：异或不必真的修改整棵树

给定一个数组，每次查询把所有元素与 x 异或，并输出新数组的 MEX。操作会累积。若真的遍历数组修改，再从 0 扫描缺失值，每次可能 O(n)。

连续异或满足结合律和自反性：

((a xor x1) xor x2) = a xor (x1 xor x2)。

因此只需维护累计掩码 mask ^= x，原集合保持不动。重复值不影响 MEX，所以先去重；这也是本题与 706D 节点计数含义不同的地方。

用子树容量判断哪里有缺口

所有数与掩码异或后，要找最小的缺失结果 y。仍从高位向低位决定 y，优先尝试令当前结果位为 0。若 y 的当前位取 0，则原数对应位必须等于 mask 的当前位。

深度来到 bit 时，该候选子树覆盖所有剩余 bit 个低位，共有 2^bit 个不同值：

若子树中的不同值数量小于 2^bit，说明里面至少有一个缺口，可以保持 y 的当前位为 0；
若数量恰好为 2^bit，该半边已经填满，只能把 y 的当前位设为 1，转向另一半。

  flowchart TD
  A["累计 mask ^= x"] --> B["从最高位尝试让 MEX 当前位为 0"]
  B --> C["查看原数位 = mask 位的子树"]
  C --> D{"不同值数量 < 该子树容量吗"}
  D -->|"是，有缺口"| E["保持结果位 0，进入该子树"]
  D -->|"否，已填满"| F["结果位写 1，进入另一子树"]
  E --> G{"低位处理完了吗"}
  F --> G
  G -->|"否"| B
  G -->|"是"| H["得到最小未出现值"]

一次手算

原集合为 {0,1,5,6}，查询 x=1 后，结果集合为 {1,0,4,7}，MEX 是 2。

决策范围	优先检查的结果半边	对应原集合半边	是否填满	MEX 决策
0..7	结果最高位 0	原最高位 0	未填满	最高位取 0
0..3	结果下一位 0	原该位等于 mask 位 0	0、1 对应结果 0、1，已填满	该位取 1
2..3	结果最低位 0	对应原值 3，不存在	未填满	最低位取 0

得到二进制 010，即 2。注意算法查的是“某一整块值域是否填满”，不是把已存在的数按普通大小二分。

正确性证明

保持不变量：进入某个 Trie 节点前，已经确定的 y 高位是所有可能缺失值中字典序最小的高位前缀，并且当前节点对应与该前缀一致的原数范围。

在 bit 位，结果位 0 对应原数位 mask_bit。若该子树计数小于容量，根据抽屉原理其中至少缺少一个完整低位组合，所以存在以当前最小前缀继续的缺失值；选择 0 最优。若计数等于容量，所有低位组合都存在，结果位 0 不可能形成缺失值，只能选择 1。两种转移都保持不变量。处理完最低位后，所得 y 存在缺口且按高位优先规则最小，因此正是 MEX。

完整 C++17 实现

#include <array>
#include <iostream>
#include <vector>
using namespace std;

struct Node {
    array<int, 2> next{-1, -1};
    int distinct = 0;
};

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

    constexpr int BITS = 19;
    constexpr int LIMIT = 1 << BITS;
    int n, m;
    cin >> n >> m;
    vector<Node> trie(1);
    trie.reserve(1 + n * BITS);
    vector<char> present(LIMIT, false);

    auto insert = [&](int value) {
        if (present[value]) return;
        present[value] = true;
        int node = 0;
        ++trie[node].distinct;
        for (int bit = BITS - 1; bit >= 0; --bit) {
            int edge = (value >> bit) & 1;
            if (trie[node].next[edge] == -1) {
                trie[node].next[edge] = static_cast<int>(trie.size());
                trie.push_back(Node{});
            }
            node = trie[node].next[edge];
            ++trie[node].distinct;
        }
    };

    for (int i = 0; i < n; ++i) {
        int value;
        cin >> value;
        insert(value);
    }

    auto countOf = [&](int node) {
        return node == -1 ? 0 : trie[node].distinct;
    };

    int mask = 0;
    while (m--) {
        int x;
        cin >> x;
        mask ^= x;
        int node = 0;
        int answer = 0;
        for (int bit = BITS - 1; bit >= 0; --bit) {
            int maskBit = (mask >> bit) & 1;
            int preferred = node == -1 ? -1 : trie[node].next[maskBit];
            int capacity = 1 << bit;
            if (countOf(preferred) < capacity) {
                node = preferred;
            } else {
                answer |= 1 << bit;
                node = trie[node].next[maskBit ^ 1];
            }
        }
        cout << answer << '\n';
    }
}

数组值和查询值都不超过 300000，小于 2^19；累计异或仍落在 19 位内。由于不同元素最多 300000 个，小于 2^19，整棵值域不可能全部填满，MEX 也一定能在 19 位范围内找到。时间 O((n+m)·19)，空间 O(n·19+2^19)。

边界与错误	正确处理
输入含重复值	MEX 只关心是否出现，插入前必须去重
多次查询	维护累计 `mask`，不能只使用本次 x
用节点总出现次数判断填满	重复值会把计数抬高，应统计不同值
子指针不存在	计数视为 0，说明该范围立即有缺口
容量写成 `2^(bit+1)`	当前选定一侧后只剩 bit 个低位，容量是 2^bit

三题放在一起，真正可迁移的是什么

对比维度	455B	706D	842D
前缀单位	字符	从高到低的二进制位	从高到低的二进制位
是否动态修改	否	插入与删除	原集合不变，只改懒掩码
重复元素	不增加新操作	必须保留出现次数	必须去重
查询决策	子节点胜负取反	优先让异或位为 1	优先让 MEX 位为 0
正确性核心	树上极小极大归纳	高位收益压过所有低位	子树计数与值域容量比较

二进制 Trie 的两道题看起来都在“按位贪心”，方向却相反：最大异或希望尽早得到 1；MEX 希望尽早保持 0，但只有候选半边尚未填满时才能这样做。把“优先走哪边”背成模板，很容易在目标稍变时写反。更可靠的方法是明确比较对象和节点摘要，再证明高位决策不会被低位推翻。

提交前检查清单

字符串结尾是否真的意味着游戏结束，还是只在没有后继时结束？
节点统计的是出现次数还是不同值数量？
删除一个重复值后，共享前缀是否仍保持可用？
位宽是否覆盖输入、累计运算和可能答案？
贪心优先分支为空、已满或计数归零时，备用分支是否安全？
多次整体异或能否合并成一个懒标记，而不是修改所有元素？
复杂度按元素数计算，还是按“元素数 × 位数 / 字符总长”计算？

验证说明

tests/verify-trie-three-article.cjs 从本文提取三份 C++17 代码，以 -O2 -Wall -Wextra -pedantic 编译，并执行 808 次程序。455B 的参考模型直接展开多局完整博弈，由两名玩家分别最大化和最小化最终胜负，另穷举六个短单词的全部 63 个非空子集与 1 到 6 局的组合；706D 用普通多重集合逐项枚举最大异或；842D 对累计掩码显式变换集合后重新计算 MEX。最大查询规模专项使用全为零的原数组，以“累计掩码为零则 MEX=1，否则为 0”独立核验。

当前共核对 307,591 个胜负或数值结果，覆盖 10 万字符、20 万次动态集合操作、30 万个输入值与 30 万次 MEX 查询，以及重复插入删除和高位边界。三份代码均无编译警告，全部结果与独立参考模型一致。

来源

题目事实来自上述官方页面；算法推导、示例组织、证明与代码均为本站原创整理。