ICPC 江西邀请赛 2026 题解

2026-05-15

🎴

2026 年 5 月 17 日，ICPC 全国邀请赛（南昌）在江西师范大学举行。304 所院校、384 支队伍参赛。本文整理了 12 道题的题解。

官方题面已上传至 Codeforces Gym（待确认 Gym ID），本文基于参赛回忆和补题整理。

A — 签到题

题意：输入两个数 m, n，计算 m mod n 和 n mod m。

解法：直接输出 m % n 和 n % m。注意输入顺序和格式。

签到题，但题面有点迷惑性，注意读题。

复杂度 O(1)。

B — 性质题

题意：给定一个序列，有某种特殊性质。

解法：这道题关键在于观察性质。数据范围很小，O(n²) 暴力即可通过。

一些队伍在这题卡了，实际上直接暴力枚举所有可能的情况就能过。

复杂度 O(n²)。

C — 矩阵快速幂最短路

题意：给定一个图，每条边有通过时间。时间以某种形式存储在矩阵中。有多次修改操作，每次修改后求某个时间相关的最值。

解法：将时间信息存入矩阵，把矩阵乘法中的加法改为取 min，乘法改为取 max。

这样矩阵快速幂就变成了 Floyd 的加速版本。每次修改后重新计算矩阵幂即可。

复杂度 O(n³ log T) 每次修改。

D — 换根 DP

题意：树上每个节点有权值。对于每个节点，求以它为根的某种权值统计。

解法：经典换根 DP（rerooting DP）。

第一次 DFS：固定根（比如 1），预处理子树信息（大小、权值和等）
第二次 DFS：从根向子节点转移，利用父节点的答案计算子节点的答案

转移公式因具体统计量而异，核心思想是：ans[v] = ans[u] - 贡献(v 的子树) + 贡献(其余部分)。

复杂度 O(n)。

E — 数据结构

题意：比较困难的数据结构问题。

解法：（待补全，题目细节需要参考官方题面。）

F — 传送点

题意：图中有若干对传送点。一对传送点可以看作缩成一个点。与传送点相连的道路数量差值不超过 2，且差值 > 0 只能在端点出现。求某种最优方案。

解法：

将每对传送点缩成一个节点
传送点所连道路数量的差值 ≤ 2
可以通过网络流或欧拉路径构造求解

具体地，将问题转化为图论中的某种匹配或路径覆盖问题。

G — 线段树 + 字符串

题意：字符串匹配问题，需要维护失配指针的前后缀信息。

解法：用线段树维护区间内的失配前后缀。

关键观察：失配指针（border）的前缀和后缀信息可以合并。线段树每个节点维护：

区间字符串的前缀失配信息
区间字符串的后缀失配信息

查询时合并左右区间信息。

复杂度 O((n+q) log n)。

H — Nim 博弈

题意：Nim 游戏的变体。与二进制末位 1 的奇偶性有关。

解法：分析二进制表示。

设 x = a xor b，其中 a、b 是某两个数。考察 x 的二进制末位 1 的位置：

如果 x 是奇数（末位为 1），先手胜
否则，递归考虑 x/2

这本质上是 Nim 游戏的一种变体，SG 函数可以通过递归构造。

I — 找规律 / 打表

题意：给定某个递推关系或条件，求某种计数。

解法：数据范围暗示可以通过打表找规律。小范围暴力计算，观察输出序列的规律（周期性、递推式等）。

J — 独立题

题意：（待补全）

解法：（待补全）

K — BSGS

题意：求解离散对数问题。求最小的 x 满足 a^x ≡ b (mod p)。

解法：Baby Step Giant Step 算法（BSGS）。

将 x 写成 x = i·m - j，其中 m = ceil(sqrt(p))。预处理 a^j 的哈希表，然后枚举 i 查找。

注意处理边界情况和无解的情况。

复杂度 O(sqrt(p))。

L — 数论 + 莫队

题意：涉及 φ(xy) = φ(x)φ(y)gcd(x,y) / φ(gcd(x,y)) 的公式，区间查询。

解法：利用欧拉函数的乘积公式：

$$φ(xy) = φ(x)φ(y)\frac{gcd(x,y)}{φ(gcd(x,y))}$$

区间查询需要维护 gcd 信息。可以用莫队离线处理查询，配合维护每个数的因子信息。

复杂度 O((n+q) sqrt(n))。

总结

这场 12 道题覆盖了图论、树 DP、博弈、数论、字符串、数据结构等多个方向。金牌线大约 7-8 题。

官方题面待上传到 Codeforces Gym 后补链接和更详细的代码实现。

发现新版本