AtCoder Beginner Contest 454 题解

for-each2026年8月18日大约 24 分钟

AtCoder Beginner Contest 454 题解

项目	内容
比赛时间	2026-04-18
比赛链接	https://atcoder.jp/contests/abc454
题目数量	A–G 共 7 题

比赛概览

本场 A–G 难度递进合理：A 是区间计数热身题；B 考察"集合大小"的理解；C 是图论建模 + BFS；D 需要发现"规范形式（canonical form）"这一关键概念，用栈在线性时间内完成归约，是很有代表性的字符串题；E 是构造题，先用棋盘染色确定可行性条件，再通过"剥皮"式的递归构造出合法路径；F 通过差分数组把区间加操作转化为"两个位置的独立增减"，再配合排序贪心求解，思维含量很高；G 是树上启发式合并（DSU on Tree）的经典应用，数据范围高达 $N \le 2.5\times 10^6$ ，对实现效率与内存都有要求。建议重点掌握 D、F、G，尤其是 F 的两步换元思想与 G 的数组化小到大合并技巧。

A - Closed interval

题目链接：https://atcoder.jp/contests/abc454/tasks/abc454_a

题目大意

给定两个整数 $L, R$ （ $1 \le L \le R \le 100$ ），求闭区间 $[L, R]$ 内一共有多少个整数，输出该个数。

思路

区间 $[L, R]$ 内的整数为 $L, L+1, \dots, R$ ，个数显然是

R - L + 1.

关键是题目强调 inclusive（闭区间），所以不是 $R-L$ 而是 $R-L+1$ 。直接读入 $L, R$ 并输出 $R-L+1$ 即可，无需任何循环或特殊处理。

易错点：忘记 +1，或者把约束中 $L \le R$ 默认当作正确输入而不做处理——本题保证 $L \le R$ ，所以公式恒为正数。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int L, R;
    cin >> L >> R;
    cout << R - L + 1 << "\n";
    return 0;
}

官方题解同时提供了 Python 版本：

L, R = map(int, input().split())
print(R - L + 1)

复杂度分析

时间复杂度： $O(1)$
空间复杂度： $O(1)$

B - Mapping

题目链接：https://atcoder.jp/contests/abc454/tasks/abc454_b

题目大意

有 $N$ 个人、 $M$ 种衣服（编号 $1\sim M$ ），第 $i$ 个人穿的衣服类型为 $F_i$ （ $1 \le F_i \le M$ ）。回答两个 Yes/No 问题：

是否 $N$ 个人穿的衣服类型两两不同？
是否每种衣服类型都至少有一个人在穿？

思路

设 $S$ 为所有 $F_i$ 构成的集合（去重）， $|S|$ 表示其中不同元素的个数。则两个问题可以简洁地翻译成：

问题 1：是否 $|S| = N$ ？因为"所有人衣服两两不同"当且仅当 $N$ 个 $F_i$ 的值互不重复，即不同值的个数等于人数。
问题 2：是否 $|S| = M$ ？因为"每种类型都被穿到"当且仅当 $1\sim M$ 中每个值都出现，即不同值的个数等于类型总数。

由于 $1 \le F_i \le M$ ，必有 $|S| \le \min(N, M)$ ，因此例如 $N > M$ 时问题 1 必然为 No， $M > N$ 时问题 2 必然为 No（鸽巢原理），但统一用 $|S|$ 判断即可覆盖所有情况。

实现上，用一个长为 $M+1$ 的布尔数组 seen 记录每个类型是否出现过，边读边统计不同值的个数 distinct，最后与 $N$ 、 $M$ 分别比较输出。

易错点：问题是两行独立输出，且必须严格匹配大小写 Yes / No。

参考代码

#include <bits/stdc++.h>
using namespace std;

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

    int N, M;
    cin >> N >> M;

    vector<bool> seen(M + 1, false);
    int distinct = 0;
    for (int i = 0; i < N; ++i) {
        int f;
        cin >> f;
        if (!seen[f]) {
            seen[f] = true;
            ++distinct;
        }
    }

    cout << (distinct == N ? "Yes" : "No") << "\n";
    cout << (distinct == M ? "Yes" : "No") << "\n";
    return 0;
}

官方题解还给出使用 std::set 的写法（思路完全相同，只是借助标准库集合去重）。本题用布尔数组即可，常数更小。

复杂度分析

时间复杂度： $O(N + M)$
空间复杂度： $O(M)$

C - Straw Millionaire

题目链接：https://atcoder.jp/contests/abc454/tasks/abc454_c

题目大意

有 $N$ 种物品（编号 $1\sim N$ ），高桥初始只拥有物品 1。他有 $M$ 个朋友，若把物品 $A_i$ 交给第 $i$ 个朋友，就能换得物品 $B_i$ （ $A_i \ne B_i$ ）。求高桥最终能够拥有的物品种类总数（包含初始的物品 1）。

思路

把问题建模成有向图： $N$ 个顶点对应 $N$ 种物品，每条交换关系 $A_i \to B_i$ 是一条有向边。

关键观察：高桥每次交换只能给出当前持有的那一件物品，并且换得物品后原来那件就不在了。因此任何一条合法的"获得物品 $t$ "的过程，都对应着图中从顶点 1 出发到达顶点 $t$ 的一条有向路径：

1 = u_0 \to u_1 \to u_2 \to \cdots \to u_k = t,

其中第 $j$ 步正是"把物品 $u_{j-1}$ 给对应朋友，换得 $u_j$ "。反之，只要存在这样一条路径，高桥就能顺着它一步一步完成交换。路径中的顶点互不相同（取简单路径即可），所用的边对应不同的朋友，互不冲突。于是：

高桥能获得的物品集合 = 从顶点 1 出发在有向图上可达的全部顶点。

因此从顶点 1 做一次 BFS（或 DFS）统计可达顶点个数即可，答案包含顶点 1 本身。

易错点：这是有向图，不是无向图——朋友关系只能从 $A_i$ 走向 $B_i$ ，方向不能反；样例 2 中边是 $2\to 1$ 、 $3\to 2$ ，从 1 出发没有任何出边，答案就是 1。

参考代码

#include <bits/stdc++.h>
using namespace std;

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

    int N, M;
    cin >> N >> M;

    vector<vector<int>> g(N + 1);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
    }

    vector<bool> vis(N + 1, false);
    queue<int> q;
    vis[1] = true;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; ++i) {
        if (vis[i]) ++ans;
    }
    cout << ans << "\n";
    return 0;
}

官方题解提供的 Python BFS 版本：

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    g[x - 1].append(y - 1)

q = deque()
d = [False] * n
q.append(0)
d[0] = True
while q:
    x = q.popleft()
    for i in g[x]:
        if d[i]:
            continue
        d[i] = True
        q.append(i)
print(d.count(True))

复杂度分析

时间复杂度： $O(N + M)$ （每个顶点、每条边各访问一次）
空间复杂度： $O(N + M)$ （邻接表 + 访问标记）

D - (xx)

题目链接：https://atcoder.jp/contests/abc454/tasks/abc454_d

题目大意

给定由 (、x、) 组成的字符串 $A$ 和 $B$ 。可以对 $A$ 任意次、任意顺序地执行下面两种操作：

把 $A$ 中出现的某个子串 (xx) 替换为 xx；
把 $A$ 中出现的某个子串 xx 替换为 (xx)。

判断能否通过若干次操作把 $A$ 变成 $B$ 。共 $T$ 组询问，所有询问的 $|A|+|B|$ 之和不超过 $2\times 10^6$ 。

思路

第一步：把问题化归为"规范形式"

注意到两种操作互为逆操作（(xx) ↔ xx），所以" $A$ 能变成 $B$ "是一个等价关系： $A \to B$ 当且仅当 $A$ 与 $B$ 可以归约到同一个不可再变的串。

对任意串 $S$ ，定义它的规范形式 $f(S)$ 为：反复把其中的子串 (xx) 替换为 xx，直到不存在 (xx) 为止所得的串。

先证明 $f(S)$ 与归约顺序无关（唯一性）：

对 $S$ 的长度归纳。任意两个 (xx) 出现位置必然互不相交（它们若重叠，一个长度为 4 的子串不可能在内部同时容纳两个长度为 4 的相同子串）。若 $S$ 中恰有一个 (xx)，替换它之后长度减少 2，由归纳假设余下归约唯一；若有两个 (xx)，记为 $a, b$ ，替换 $a$ 不会影响 $b$ 的存在性。先换 $a$ 再处理 $b$ 、与先换 $b$ 再处理 $a$ ，两者都归结为对同一中间串继续归约，由归纳假设殊途同归。故归约顺序不影响最终结果。

进而有等价关系：

$A$ 可以通过操作变成 $B$ $\iff$ $f(A) = f(B)$ 。

证明也很直观：

（ $\Leftarrow$ ）把 $A$ 按归约序列变成 $f(A)$ ，再把 $B$ 的归约序列逆着执行（每次把 xx 扩展回 (xx)），就能从 $f(A) = f(B)$ 变回 $B$ 。
（ $\Rightarrow$ ）单次操作保持 $f$ 不变（由唯一性，无论对 $S$ 还是对操作后的 $S'$ 归约都得到同一个 $f$ ），所以整条操作链首尾的 $f$ 相同。

于是问题变成：计算 $f(A)$ 与 $f(B)$ 并比较是否相等。

第二步：用栈在线性时间内计算 $f(S)$

维护一个字符串 $T$ ，从左到右扫描 $S$ ：

把当前字符追加到 $T$ 末尾；
若 $T$ 的最后 4 个字符恰好是 (xx)，就把它们替换成 xx。

为什么"只检查末尾 4 个字符"就足够？因为每当某个 (xx) 的右括号 ) 被压入的瞬间，这 4 个字符正好位于 $T$ 的末尾，一定会被立刻归约；归约后 $T$ 以 xx 结尾，虽然可能为新的 (xx) 埋下伏笔（例如处理 ((xx))：压入第 5 个字符后得到 ((xx)，末尾 4 个字符恰为 (xx)，立即归约为 (xx，再压入最后一个 ) 后再次构成 (xx) 并归约为 xx），但新的 (xx) 必然以下一次压入的字符作为右括号，因此在下一次循环中必然被检查到。所以算法结束时 $T$ 中不存在任何 (xx) 子串，且 $T$ 是由 $S$ 通过合法归约得到的，由唯一性知 $T = f(S)$ 。

复杂度：每个字符被压入一次，每次归约减少 2 个字符，归约次数不超过 $|S|/2$ ，故单串总时间为 $O(|S|)$ 。

易错点

(xx) 的替换是"末尾 4 个字符"，要正确写出末尾子串的比较（如 T.compare(T.size()-4, 4, "(xx)")）。
注意归约后可能连锁产生新的 (xx)，所以每次压入字符后都要检查一次，而不是只在出现 ) 时检查。

参考代码

#include <bits/stdc++.h>
using namespace std;

string canonical(const string& S) {
    string T;
    for (char ch : S) {
        T.push_back(ch);
        if (T.size() >= 4 && T.compare(T.size() - 4, 4, "(xx)") == 0) {
            T.resize(T.size() - 4);
            T += "xx";
        }
    }
    return T;
}

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

    int T;
    cin >> T;
    while (T--) {
        string A, B;
        cin >> A >> B;
        cout << (canonical(A) == canonical(B) ? "Yes" : "No") << "\n";
    }
    return 0;
}

复杂度分析

时间复杂度：每组 $O(|A| + |B|)$ ，总 $O\left(\sum (|A|+|B|)\right) \le 2\times 10^6$
空间复杂度： $O(|A| + |B|)$ （临时串的长度不超过原串）

E - LRUD Moving

题目链接：https://atcoder.jp/contests/abc454/tasks/abc454_e

题目大意

在 $N\times N$ 网格上，棋子初始在 $(1,1)$ 。执行恰好 $N^2-2$ 次移动（每次移动到相邻的上/下/左/右格子），最终到达 $(N,N)$ ，且要求恰好访问一次除 $(A,B)$ 外的每个格子（起点终点不能中途经过）。判断是否可行；可行时输出任意一条合法的 L/R/U/D 移动序列。共 $T$ 组询问， $\sum N^2 \le 10^6$ 。

思路

第一步：棋盘染色给出可行性必要条件

把格子按 $i+j$ 的奇偶染色： $i+j$ 为偶数的格子记为黑，奇数的记为白。由于每次移动都会改变 $i+j$ 的奇偶，棋子每走一步颜色必定翻转。

起点 $(1,1)$ 与终点 $(N,N)$ 的 $i+j$ 都是偶数（ $2$ 与 $2N$ ），所以都是黑格。整个访问序列长为 $N^2-1$ （除 $(A,B)$ 外全部格子），颜色序列为黑→白→黑→白→…，且首尾都是黑。

若 $N$ 为奇数： $N^2-1$ 为偶数，序列长为偶数且以黑开头，则最后一步落在白格；但终点 $(N,N)$ 是黑格，矛盾，答案为 No。
若 $N$ 为偶数： $N^2-1$ 为奇数，序列以黑开头、以黑结尾，其中黑格数 $=\frac{N^2}{2}$ ，白格数 $=\frac{N^2}{2}-1$ 。网格中黑格总数恰为 $\frac{N^2}{2}$ ，因此被跳过的 $(A,B)$ 必须是白格，即

A + B \equiv 1 \pmod 2.

若 $A+B$ 为偶数，则 $(A,B)$ 是黑格，访问的黑格数将变成 $\frac{N^2}{2}-1$ ，同样矛盾，答案为 No。

因此答案是 Yes 的必要条件为： $N$ 为偶数且 $A+B$ 为奇数。官方题解证明了该条件同时也是充分的，下面给出构造。

第二步：递归"剥皮"构造

把问题推广为 $H\times W$ 网格、从 $(1,1)$ 走到 $(H,W)$ 、避开 $(A,B)$ 的哈密顿路径。

剥行：若 $A > 2$ （禁区不在最上面两行），可以用前缀

\underbrace{RR\cdots R}_{W-1}\ D\ \underbrace{LL\cdots L}_{W-1}\ D

把最上面两行全部蛇形走完（沿第 1 行向右、下到第 2 行、向左、下到第 3 行），恰好落在 $(3,1)$ ，问题化为 $(H-2, W, A-2, B)$ 。若 $A \le 2$ ，则禁区在最上面两行，改为在后缀上剥掉最下面两行：用上述串的逆序 $D\ L^{W-1}\ D\ R^{W-1}$ 作为结尾，问题化为 $(H-2, W, A, B)$ 。反复执行直到 $H=2$ 。

剥最下面两行作为"后缀"的理由：后缀在整条路径的末尾被逆序应用——先解决内部子问题到达 $(H-2, W)$ ，再用 $D\ L^{W-1}\ D\ R^{W-1}$ 走完最下面两行并停在 $(H,W)$ 。

剥列： $H=2$ 后，若 $B > 2$ ，用前缀 DRUR（在 $2\times W$ 网格中恰好走完左边一个 $2\times 2$ 方块并落到下一列顶部），问题化为 $(2, W-2, A, B-2)$ ；若 $B \le 2$ ，用后缀 RURD 剥掉最右边两列。反复执行直到 $W=2$ 。
基元：剩 $2\times 2$ 时，由于坐标每次减 2 不改变奇偶， $A+B$ 为奇数保证禁区在 $2\times 2$ 中只能是 $(1,2)$ 或 $(2,1)$ 。前者从 $(1,1)$ 出发用 DR（下、右），后者用 RD（右、下），都能访问其余 3 格并停在 $(2,2)$ 。

正确性：每次剥皮都保证被剥的 2 行/2 列中不含禁区（剥行时 $A>2$ 或 $A\le H-2$ ；剥列时 $B>2$ 或 $B\le W-2$ ，且过程保持 $H,W\ge 4$ ），路径在剥下的带状区域内部蛇形走满、不重复；前缀与后缀分别从两头"包夹"，最终拼接即完整覆盖除禁区外的所有格子。边界情况 $N=2$ 时两个循环都不执行，直接落到基元，答案分别是 DR 或 RD。

输出格式：Yes 换行后输出移动串（长度为 $N^2-2$ ）。

参考代码

#include <bits/stdc++.h>
using namespace std;

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

    int T;
    cin >> T;
    while (T--) {
        int N, A, B;
        cin >> N >> A >> B;

        if (N % 2 == 1 || (A + B) % 2 == 0) {
            cout << "No\n";
            continue;
        }

        int a = A - 1, b = B - 1;              // 转为 0-indexed
        vector<string> pre, suf;

        // 行剥皮：剥顶 2 行（前缀）或底 2 行（后缀）
        string row(N - 1, 'R');
        row += "D";
        row += string(N - 1, 'L');
        row += "D";
        for (int it = 0; it < N / 2 - 1; ++it) {
            if (a >= 2) {
                pre.push_back(row);
                a -= 2;
            } else {
                string t = row;
                reverse(t.begin(), t.end());
                suf.push_back(t);
            }
        }

        // 列剥皮：剥左 2 列（前缀）或右 2 列（后缀）
        for (int it = 0; it < N / 2 - 1; ++it) {
            if (b >= 2) {
                pre.push_back("DRUR");
                b -= 2;
            } else {
                suf.push_back("RURD");
            }
        }

        // 基元 2x2
        if (a == 0 && b == 1) pre.push_back("DR");
        else pre.push_back("RD");

        string ans;
        for (const string& s : pre) ans += s;
        for (int i = (int)suf.size() - 1; i >= 0; --i) ans += suf[i];

        cout << "Yes\n" << ans << "\n";
    }
    return 0;
}

官方题解提供的 Python 版本（逻辑相同）：

for _ in range(int(input())):
    n, a, b = map(int, input().split())
    a, b = a - 1, b - 1
    if n % 2 == 1 or (a + b) % 2 == 0:
        print("No")
        continue
    s1 = []
    s2 = []
    for _ in range(n // 2 - 1):
        s = "R" * (n - 1) + "D" + "L" * (n - 1) + "D"
        if a >= 2:
            s1.append(s)
            a -= 2
        else:
            s2.append(s[::-1])
    for _ in range(n // 2 - 1):
        s = "DRUR"
        if b >= 2:
            s1.append(s)
            b -= 2
        else:
            s2.append(s[::-1])
    assert (a, b) in ((0, 1), (1, 0))
    if (a, b) == (0, 1):
        s1.append("DR")
    else:
        s1.append("RD")
    ans = "".join(s1) + "".join(s2[::-1])
    print("Yes")
    print(ans)

复杂度分析

时间复杂度：每个询问 $O(N^2)$ （输出串本身就有 $N^2-2$ 个字符），总 $O(\sum N^2) \le 10^6$
空间复杂度： $O(N^2)$ （存储答案串）

F - Make it Palindrome 2

题目链接：https://atcoder.jp/contests/abc454/tasks/abc454_f

题目大意

给定长度 $N$ 的整数序列 $A$ （ $0 \le A_i < M$ ）。每次操作选择 $1 \le l \le r \le N$ ，把 $A_l,\dots,A_r$ 都加上 $1$ （对 $M$ 取模）。求使 $A$ 成为回文（ $A_i = A_{N+1-i}$ 对所有 $i$ 成立）所需的最少操作次数。共 $T$ 组询问， $\sum N \le 2\times 10^5$ ， $M$ 可达 $10^9$ 。

思路

第一步：禁止跨越中点的操作

先考虑"跨过 $A$ 中点的操作"。记 $N' = \lfloor N/2\rfloor$ ，定义差值序列

B_i = (A_i - A_{N+1-i}) \bmod M \qquad (1 \le i \le N').

$A$ 是回文当且仅当所有 $B_i = 0$ 。

一次区间加操作 $[l,r]$ （加 $1$ ）对 $B$ 的影响：左侧 $i \in [l,r]\cap[1,N']$ 的 $B_i$ 加 $1$ （因为 $A_i$ 变大）；右侧镜像 $i \in [N+1-r,\ N+1-l]\cap[1,N']$ 的 $B_i$ 减 $1$ （因为 $A_{N+1-i}$ 变大）。若操作跨越中点（ $l \le N' < r$ ），则左侧区间是 $[l,N']$ ，右侧镜像区间是 $[N+1-r,\ N']$ ，两者在 $[\max(l, N+1-r),\ N']$ 上重叠并互相抵消，净效果等价于在 $[l,\ N+1-r-1]$ 上加 $1$ ——这恰是一个不跨中点的左半区间操作（ $N$ 为奇数时中点格子的加 1 不影响任何 $B_i$ ，同理）。因此任何跨越中点的操作都可以被替换为不跨越中点的操作，不影响最少次数。

于是操作只剩两类：在左半区间 $[l,r]\subseteq[1,N']$ 上加 $+1$ （或 $-1$ ，等价地由右半操作提供）。问题转化为：

反复选择 $1 \le l \le r \le N'$ 和 $c \in\{-1,1\}$ ，把 $B_l,\dots,B_r$ 每个都加 $c$ （模 $M$ ），使 $B$ 全变为 $0$ 的最少操作次数。

第二步：差分数组化区间加为单点

对 $B$ 取差分：令 $B_0 = B_{N'+1} = 0$ ，定义

C_i = (B_i - B_{i-1}) \bmod M \qquad (1 \le i \le N'+1).

对 $B_l,\dots,B_r$ 整体加 $c$ ，等价于 $C_l$ 加 $c$ 、 $C_{r+1}$ 减 $c$ （均模 $M$ ）。于是问题再次转化为：

反复选择两个下标 $i,j$ ，把 $C_i$ 加 $1$ （模 $M$ ）、 $C_j$ 减 $1$ （模 $M$ ），使全部 $C$ 变为 $0$ 的最少操作次数。

原问题天然满足 $i\ne j$ ；放宽为允许 $i=j$ （此时是空操作）不改变答案。记 $N''=N'+1$ 。

第三步：按"只增/只减"划分下标

对同一元素既加又减没有意义（可以约去），所以最优解中每个下标要么只接受加、要么只接受减。设 $X$ 为只被减的下标集合，其余下标只被加；把 $C_i=0$ 的元素放进 $X$ （贡献为 0，放哪边都行）。

记 $S=\sum_{i=1}^{N''} C_i$ 。由于

S \equiv \sum_i (B_i - B_{i-1}) = B_{N'+1} - B_0 = 0 \pmod M,

$S$ 是 $M$ 的整数倍。

减的总次数： $S_X = \sum_{i\in X} C_i$ 。
加的总次数： $\sum_{i\notin X}(M - C_i) = M(N''-|X|) - S + S_X$ 。

一次操作同时贡献 1 次加和 1 次减，故总操作次数为两者取大：

\text{ops}(X) = \max\left(S_X,\ M(N''-|X|)-S+S_X\right) = S_X + M\cdot\max\left(N''-|X|-\frac SM,\ 0\right).

第四步：贪心选取最优 $X$

当 $|X|=k$ 固定时， $\text{ops}(X)$ 只通过 $S_X$ 依赖 $X$ 的具体构成，因此取 $C$ 中最小的 $k$ 个元素即可最小化 $S_X$ 。

再看 $k$ 的选取： $k$ 每增大 1， $S_X$ 至多增加 $M-1$ （新增元素值 $<M$ ）；而在 $k < N''-S/M$ 时，第二项 $M\max(\cdots,0)$ 会减少 $M$ 。净效果 $M-1$ 与 $-M$ 之差仍为负，说明增大 $k$ 严格更优，直到 $k$ 达到 $N''-S/M$ ；此后第二项恒为 0， $\text{ops}=S_X$ ，再增大 $k$ 只会增加和，不再更优。

故最优解取

k = N'' - \frac{S}{M},

此时操作次数恰为 $C$ 中最小的 $k$ 个元素之和。

总结算法

计算 $B_i = (A_i - A_{N+1-i}) \bmod M$ （ $i=1..N'$ ）；
计算差分数组 $C$ （长 $N''=N'+1$ ，含 $B_0=B_{N'+1}=0$ 两端）；
将 $C$ 排序，求 $S=\sum C$ ，输出前 $k = N'' - S/M$ 小的元素之和。

易错点：所有模运算要保证结果非负（C++ 中 $x \% m$ 可为负，需 $(x \% m + m) \% m$ ）； $S/M$ 是精确整除（ $S$ 是 $M$ 的倍数）； $M$ 可能很大，要用 64 位整数。

参考代码

#include <bits/stdc++.h>
using namespace std;

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        long long m;
        cin >> n >> m;

        vector<long long> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];

        int np = n / 2;                 // N'
        vector<long long> c;            // 差分数组 C，长 N'' = N' + 1
        c.reserve(np + 1);

        long long prev = 0;             // B_0 = 0
        for (int i = 0; i < np; ++i) {
            long long bi = (a[i] - a[n - 1 - i]) % m;
            if (bi < 0) bi += m;
            long long ci = (bi - prev) % m;
            if (ci < 0) ci += m;
            c.push_back(ci);
            prev = bi;
        }
        long long last = (m - prev) % m; // C_{N''} = (B_{N'+1} - B_{N'}) mod M, B_{N'+1}=0
        c.push_back(last);

        sort(c.begin(), c.end());

        long long S = 0;
        for (long long x : c) S += x;
        long long k = (long long)c.size() - S / m;

        long long ans = 0;
        for (long long i = 0; i < k; ++i) ans += c[i];
        cout << ans << "\n";
    }
    return 0;
}

官方题解提供的 Python 版本（非常简洁）：

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = [0] + [(a[i] - a[n - 1 - i]) % m for i in range(n // 2)] + [0]
    c = [(b[i + 1] - b[i]) % m for i in range(len(b) - 1)]
    c.sort()
    print(sum(c[:len(c) - sum(c) // m]))

复杂度分析

时间复杂度：每个询问 $O(N\log N)$ （瓶颈为排序），总 $O(\sum N \log N)$
空间复杂度： $O(N)$

G - Mode in the Subtree

题目链接：https://atcoder.jp/contests/abc454/tasks/abc454_g

题目大意

给定一棵以 1 为根的树，顶点 $i$ 的父亲为 $p_i$ （保证 $p_i < i$ ），每个顶点有颜色 $c_i \in [1,N]$ 。对每个顶点 $v$ ，设 $f_i$ 为子树 $v$ 中颜色 $i$ 的个数，令 $m_v$ 为所有 $f_i$ 的最大值， $k_v$ 为达到该最大值的颜色种数。输出

\left(\sum_{i=1}^{N} (m_i \oplus i)\times(k_i \oplus i)\right) \bmod 998244353.

其中 $\oplus$ 为按位异或。数据范围 $N \le 2.5\times 10^6$ ，树与颜色由给定的伪随机生成器生成。

思路

第一步：重建输入

题目输入了 $N, \text{seed}, M, F$ 、 $q_2,\dots,q_M$ 与 $d_1,\dots,d_M$ ，需要按如下伪代码重建 $p_i$ 与 $c_i$ ：

state = seed
for i = 2..N:
    if i <= M: p[i] = q[i]
    else:
        p[i] = (state mod (i-1)) + 1
        state = (state * 1103515245 + 12345) mod 2^31
for i = 1..N:
    if i <= M: c[i] = d[i]
    else:
        c[i] = (state mod F) + 1
        state = (state * 1103515245 + 12345) mod 2^31

注意 state 的递推中乘法可能溢出 32 位，必须用 64 位整数保存；模 $2^{31}$ 可用 % (1LL<<31) 或按位与 & ((1LL<<31)-1)。由于 $p_i < i$ ，树天然满足拓扑序，这给后续自底向上计算带来了便利。

第二步：DSU on Tree（树上启发式合并）

朴素做法：对每个顶点都开一个"颜色 $\to$ 次数"的哈希表并向上合并，总复杂度近似 $O(N^2)$ 且常数巨大。官方做法利用 DSU on Tree：每个顶点复用其重儿子（子树最大的儿子）的表，只把轻儿子的子树重新插入。

为每个顶点维护一张"当前子树表"，需要支持三种操作：

add(v)：把顶点 $v$ 的颜色信息插入表；
query(v)：回答"整棵子树 $v$ 的众数"，即 $(m_v, k_v)$ ；
reset：清空表（用于丢弃轻儿子算完的结果）。

递归框架如下：

dfs(c):
  先对每个轻儿子 d 执行 dfs(d)，随后 reset()   # 轻儿子的表用完即弃
  若 c 非叶，dfs(重儿子)                        # 重儿子的表保留复用
  把每个轻儿子子树中的所有顶点 add 进表
  add(c)
  query(c)

复杂度分析：顶点 $v$ 被 add 的次数 =（根到 $v$ 路径上的轻边数）+ 1。轻边的定义满足"沿轻边上跳子树大小至少减半"，所以每个顶点至多经过 $O(\log N)$ 条轻边，总 add 调用数为 $O(N\log N)$ ；query 恰好 $N$ 次，reset 为 $O(N)$ 次。只要三种操作本身够快，总复杂度即为 $O(N\log N)$ 。

第三步：用数组实现三种操作

本题颜色编号不超过 $N$ ，无需哈希表，直接开数组即可：

cnt[x]：当前表中颜色 $x$ 出现的次数；
num[t]：当前恰好出现 $t$ 次的颜色种数；
mx：当前最大出现次数。
add(v)：设 $x=c_v$ ，令 num[cnt[x]]--; cnt[x]++; num[cnt[x]]++; mx = max(mx, cnt[x])。
query(v)：答案即 (mx, num[mx])。
reset(子树 d)：把 cnt 中属于子树 $d$ 的颜色全部清零，并把 num[0..mx] 清零、mx=0。不需要清空整个数组：只要按欧拉序把子树 $d$ 的每个顶点对应颜色清零即可，因为 reset 发生时表里恰好就是子树 $d$ 的内容。

正确性：DSU on Tree 维护的"当前表"在每次 dfs(c) 开始时是空的（轻儿子处理完即 reset，重儿子递归前父节点的表也是空的）；处理完重儿子后表 = 重儿子的整棵子树，再把各轻儿子子树顶点与 $c$ 本身加入，正好构成子树 $c$ 的完整信息。因此每个 query 得到的众数都是对的。

第四步：实现细节（针对 $N$ 大的工程问题）

重儿子前置：利用 $p_i<i$ 的拓扑序，逆序一趟求出子树大小 sub，同时找出每个顶点的重儿子，并把重儿子交换到孩子列表最前面（CSR 存储）。
欧拉序：用显式栈做 DFS（避免递归爆栈），得到 down[v]、up[v]，使子树 $v$ 的顶点落在欧拉序区间 $[\text{down}[v], \text{up}[v])$ 。这样"把轻儿子整棵子树加入"和"reset 子树"都变成对欧拉序区间的循环， $O(|\text{subtree}|)$ 。
DSU 遍历也改写成显式栈：用事件栈模拟递归（事件 = 顶点 + 阶段，阶段 0/1/2 对应"处理轻儿子 / 处理重儿子 / 合并并回答"；另设 reset 事件）。树高最大 $O(N)$ ，显式栈可避免栈溢出。
答案累加：使用 64 位整数，边乘边取模，防止溢出。

参考代码

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 998244353;

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

    int N, M, F;
    long long seed;
    cin >> N >> seed >> M >> F;

    vector<int> q(M + 1), d(M + 1);
    for (int i = 2; i <= M; ++i) cin >> q[i];
    for (int i = 1; i <= M; ++i) cin >> d[i];

    // 重建 p[1..N], col[1..N]
    vector<int> p(N + 1, 0), col(N + 1, 0);
    long long state = seed;
    for (int i = 2; i <= N; ++i) {
        if (i <= M) {
            p[i] = q[i];
        } else {
            p[i] = (int)(state % (i - 1)) + 1;
            state = (state * 1103515245 + 12345) % 2147483648LL;
        }
    }
    for (int i = 1; i <= N; ++i) {
        if (i <= M) {
            col[i] = d[i];
        } else {
            col[i] = (int)(state % F) + 1;
            state = (state * 1103515245 + 12345) % 2147483648LL;
        }
    }

    // 孩子列表 CSR：start[v] .. start[v+1]-1
    vector<int> deg(N + 2, 0);
    for (int i = 2; i <= N; ++i) deg[p[i]]++;
    vector<int> start(N + 3, 0);
    for (int i = 1; i <= N + 1; ++i) start[i + 1] = start[i] + deg[i];
    vector<int> child(N);              // 共 N-1 条孩子边
    {
        vector<int> cur(N + 3);
        for (int i = 1; i <= N + 1; ++i) cur[i] = start[i];
        for (int i = 2; i <= N; ++i) child[cur[p[i]]++] = i;
    }

    // 自底向上求子树大小（利用 p_i < i 的拓扑序）
    vector<int> sub(N + 1, 1);
    for (int i = N; i >= 2; --i) sub[p[i]] += sub[i];

    // 重儿子交换到孩子列表最前
    for (int v = 1; v <= N; ++v) {
        int best = start[v];
        for (int j = start[v] + 1; j < start[v + 1]; ++j) {
            if (sub[child[j]] > sub[child[best]]) best = j;
        }
        if (best != start[v]) swap(child[start[v]], child[best]);
    }

    // 欧拉序（显式栈），子树区间 [down[v], up[v])
    vector<int> down(N + 1), up(N + 1), euler(N);
    int idx = 0;
    vector<int> st;
    st.reserve(2 * N + 4);
    st.push_back(0);    // 根结束哨兵
    st.push_back(1);
    while (!st.empty()) {
        int c = st.back();
        st.pop_back();
        if (c > 0) {                        // 顶点
            down[c] = idx;
            euler[idx] = c;
            ++idx;
            for (int j = start[c + 1] - 1; j >= start[c]; --j) {
                int d = child[j];
                st.push_back(~d);           // 结束哨兵
                st.push_back(d);
            }
        } else if (c == 0) {
            up[1] = idx;
        } else {
            up[~c] = idx;
        }
    }

    // DSU on Tree（事件栈模拟递归）
    vector<int> cnt(N + 1, 0);        // cnt[颜色]
    vector<int> num(N + 2, 0);        // num[次数]
    num[0] = N;
    int mx = 0;
    long long ans = 0;

    auto add = [&](int v) {
        int x = col[v];
        --num[cnt[x]];
        ++cnt[x];
        ++num[cnt[x]];
        if (cnt[x] > mx) mx = cnt[x];
    };

    auto reset_subtree = [&](int d) {
        for (int i = down[d]; i < up[d]; ++i) cnt[col[euler[i]]] = 0;
        for (int i = 0; i <= mx; ++i) num[i] = 0;
        mx = 0;
    };

    // 事件 = (顶点<<2) | 阶段；阶段 0/1/2 分别处理轻儿子/重儿子/合并回答，3 = reset
    vector<int> events;
    events.reserve(2 * (N + 5));
    events.push_back((1 << 2) | 0);

    while (!events.empty()) {
        int e = events.back();
        events.pop_back();
        int v = e >> 2, type = e & 3;

        if (type == 0) {
            events.push_back((v << 2) | 1);
            for (int j = start[v + 1] - 1; j >= start[v] + 1; --j) {
                int d = child[j];
                events.push_back((d << 2) | 3);   // 处理完 d 后 reset
                events.push_back((d << 2) | 0);
            }
        } else if (type == 1) {
            events.push_back((v << 2) | 2);
            if (start[v] < start[v + 1]) {
                events.push_back((child[start[v]] << 2) | 0); // 重儿子
            }
        } else if (type == 2) {
            for (int j = start[v] + 1; j < start[v + 1]; ++j) {
                int d = child[j];
                for (int i = down[d]; i < up[d]; ++i) add(euler[i]);
            }
            add(v);
            ans = (ans + (long long)(mx ^ v) * (num[mx] ^ v)) % MOD;
        } else {
            reset_subtree(v);
        }
    }

    cout << ans << "\n";
    return 0;
}

说明：官方题解另给出了一份 Python 实现，思路与本代码完全一致；但本题 $N$ 高达 $2.5\times 10^6$ ，树深可能极大，Python 的递归 DFS 需要显式提高递归上限，实践中更推荐使用本代码这类迭代写法。官方题解还特别指出：若采用 unordered_map 实现合并，会因过大的常数因子（时间与空间）而难以通过，因此数组化的 DSU on Tree 才是本题的可行方案。

复杂度分析

时间复杂度： $O(N\log N)$ （每个顶点被 add 的次数为 1 加上其轻祖先个数，后者为 $O(\log N)$ ）
空间复杂度： $O(N)$ （若干长度为 $N$ 的整数数组）