2026 NOI 全题解析 · 优编程教练团复盘

　　基于 NOI 2026 官方题面、官方测试数据与公开题解，写给所有在学信息学竞赛、关心国内命题风向的同学。

　　写在前面：写在我们自己学生第一次站上 NOI 赛场之后

　　今年对优编程具有特殊意义：优编程学员首次进入 NOI 全国决赛赛场，共 4 名学员获奖，获得 1 枚银牌、3 枚铜牌。

　　这 4 名学员分属两条培养路径。其中，江西一位高二同学获银牌、429 分，山东一位九年级同学获铜牌、336 分；这两位系 2021 年首批长线零基础 C++ 学员，入学时无任何编程基础，于 2020 至 2021 年间在优编程前身——新东方东方优播“英才计划”起步，历经语法入门、CSP-J/S、省选等阶段的系统培养进入国赛。另两位云南同学，八年级获 296 分、高一获 288 分，均来自优编程合作办学培养体系，我们对其入学前背景不作未经证实的描述。文中以省份与年级称呼他们，是出于对学生隐私的尊重。

　　这篇复盘里，关于赛场气氛、临场状态、六道题上手感受的第一手材料，部分来自上述同学赛后与教练团队的复盘交流，经我们整理汇总；这也使今年的复盘多了一些来自我们自己学员的现场视角。

　　我们为什么带大家看 NOI？客观而言，NOI 是国内信息学竞赛的最高舞台，也是志在强基计划、争取保送的同学的终极目标。多数同学未必会走到 NOI，但 NOI 的命题风格与方向会向下传导至 NOIP、CSP-S，提前了解，有助于明确平时训练的方向。对走中考科技特长生、高中升大学综合评价等渠道的同学，了解 NOI 亦有参考价值；对志在保送或强基破格的同学，则是必须认真研究的内容。

　　因此，我们将今年这六道题逐一拆解，供不同目标的同学各取所需：冲国决的同学深究正解与常数，打 NOIP、CSP-S 的同学把握命题方向，走综合评价、科技特长生渠道的同学了解其整体脉络即可。

　　教练团提醒：题目范围、特殊性质和评分规则以 CCF 官方题面为准。下文依据官方题面与接口，并结合公开题解核对推导；代码另用官方公开数据和独立小规模程序验证。

　　关于文中代码：六题均给出完整接口实现，main 由评测程序提供。《布丁》使用洛谷 P17142 的完整提交格式，以函数声明代替 pudding.h，提交时选择 C++17 或更高版本。其余五题保留官方头文件，代码兼容 C++11。官方比赛使用 C++14；本地核验结果及《布丁》的满分询问资源见文末说明。

　　一、这届 NOI 是个什么局面

　　第 43 届 CCF NOI 于 2026 年 7 月 18 日至 24 日在山东省青岛市城阳第一高级中学举行，32 个省市自治区、约 804 名师生参赛。比赛分两天，Day 1 为线段、传送、布丁三题，Day 2 为中位数、木棉、彩虹树三题，每题 100 分。本届共颁出金牌 54 枚，其中前 50 名入选国家集训队；银牌 146 枚。

　　金牌榜前列（按官方名单，列为实际总分／政策加分后总分）：

姓名	就读学校	省份	实际总分	加分后
郑煦翔	南京外国语学校	江苏	700	705
姜博闻	华东师范大学第二附属中学	上海	699	704
周以山	杭州第二中学	浙江	697	697
许淇文	南京外国语学校	江苏	688	693
韩书简	华东师范大学第二附属中学	上海	691	691
杨永昌	青岛市城阳第一高级中学	山东	671	676
戴睿宸	华南师范大学附属中学	广东	670	675

　　六道题摊开，三个趋势很清楚：

　　题型回归传统，工程要求在涨。 segment 是区间图弦图性质的扫描线计数，teleport 是树上最短期望路径，pudding 是 gcd 探针交互，median 是二分答案加小段数 DP 与大段数贪心判定，kapok 把 Prüfer 解码翻译成三维数点，rainbow 是 n=200 的树形 DP。没有一道是“背个模板就能过”的，常数和时限都是考点。

　　函数式提交需要专门训练。六道题都由评测程序调用指定接口，其中《布丁》还需要调用交互库；选手应熟悉头文件、编译链接、多次调用和本地对拍。题面样例评测程序与赛后公开的正式评测程序可能采用不同的输入输出包装。

　　子任务与资源评分提供了不同切入点。五道传统题按测试点计分，数据规模和特殊性质支持逐步改进算法；《布丁》还根据询问次数与总询问长度计算得分。不能将六题一概描述为同一套规模台阶或线性资源给分。

　　二、Day 1 三题详解

　　T1 线段（segment）

　　1. 题目概述与数据范围

　　给定 n 条闭区间 [,]。对每个 s=1,…,k，统计选出恰好 s 条线段后，相交图是一棵树的方案数，对 998244353 取模。线段按输入编号区分，即使两个区间完全相同，也属于不同元素。端点相同算相交，长度为 0 的线段也合法。

　　官方限制为 1≤n≤3000，1≤m≤1000，1≤≤≤m，1≤k≤n。每个测试点有 1≤t≤20 组数据；令 K 为这些数据的 k 之和，则 K≤200。时限 2.5 秒，内存 512 MiB，25 个测试点等分。

　　这是函数式提交题，需要实现 init 和 segment。每次 segment 返回恰好 k+1 个整数，首项为 0，后 k 项依次是答案；同一测试点可能多次调用，不能遗留上一组的状态。

　　2. 题意翻译与建模

　　把每条选中的区间作为一个顶点，两区间有公共点就连边。相交图为树，等价于选中区间的并集连通，且任何位置最多被两条选中区间覆盖。

　　理由是：区间图没有长度至少为 4 的无弦环。取一个环中右端点最小的区间，它在环上的两个邻居都包含这个右端点，因此这两个邻居相交，形成弦或三角形。另一方面，三条两两相交的区间必有公共点。所以只要覆盖深度不超过 2，就没有三角形，进而没有任何环；再要求连通即可。

　　3. 部分分与特殊性质

　　测试点 1～3：n≤20，m≤100，K≤20。可枚举子集，用并查集或搜索判定连通且边数为顶点数减一；朴素复杂度为 O(·n²)，实现时可预存相交关系。

　　测试点 4、5：k≤2；测试点 6～8：k≤3。两组均为 n≤3000、m≤1000、K≤200。k=2 时统计相交区间对；k=3 时要排除三角形，不能直接枚举所有三元组并声称能通过最大规模。

　　测试点 9、10：n≤500，m≤1000，K≤200，满足 A。A 表示任意两条不同线段互不包含。测试点 11～15：n≤3000，m≤1000，K≤200，满足 B。B 表示对原编号 i，区间 i 包含区间 j，或两者不相交。

　　测试点 16～18：n≤200，m≤500，K≤50；测试点 19～21：n≤500，m≤1000，K≤200。两组均满足 C，即全部 2n 个端点互不相同。

　　测试点 22、23：n≤1000，m≤100，K≤30；测试点 24、25：n≤3000，m≤1000，K≤200。两组都没有额外性质。以下算法统一处理全部数据。

　　4. 正解思路

　　将区间按左端点非降序排列，记排序后区间为 [,]，下标从 0 开始。预处理 nxt[x]，表示第一个满足 >x 的下标，不存在时为 n。

　　定义 (i,r)：从下标 i 开始的后缀中再选 s 条区间，接到已有连通部分上的方案数。r>0 时，已有部分在后续扫描中只剩一条可能与新区间相交的区间，其右端点为 r；r=0 表示尚未选任何区间。每次接入都保持连通且无三重覆盖。

　　不选第 i 条区间，直接转移到 (i+1,r)。若 r=0 且选它，就建立初始连通部分，转移到 (i+1,)。若 r>0，则只有 ≤r 才能接入。

　　接入后，记 q=min(r,)、r′=max(r,)。从当前左端点到 q，两条区间同时活跃，因此后续选择的区间必须满足左端点严格大于 q；于是跳到 nxt[q]，转移到 (nxt[q],r′)。

　　第二个公式只在 r>0 且 ≤r 时加入第二项；否则只保留“不选”的转移。所有加法都对模数取模。

　　边界为 (i,r)=1；对于 s>0，(n,r)=0。答案为 (0,0)。按 s 递增、i 递减计算，用两层数组保存 s 与 s−1。

　　5. 正确性与端点边界

　　对任意合法集合，按上述固定顺序考察每条区间，其“选或不选”路径唯一。第一条选中区间建立连通部分；此后的每条选中区间都必须与唯一仍可能活跃的区间相交，否则会断开。接入第二条后，所有左端点不超过两者较小右端点的后续区间都会形成三角形，必须跳过；更晚开始的区间只需记住较大的右端点。因此转移既不遗漏合法集合，也不会计入非法集合。

　　闭区间的边界必须分清两种情况。已有一条区间在 x 结束，新区间在 x 开始，两者可以相连。例如 [1,2] 与 [2,3] 构成一棵二点树。只有当前已经有两条区间覆盖 x 时，才必须跳过在 x 开始的第三条区间。nxt 使用 upper_bound，正是为了实现这里的严格大于。

　　两条区间右端点相同时，nxt[r] 后所有区间的左端点均大于 r，无法再接入；只有“剩余选择数为 0”的状态保留一次计数，不需要额外增加答案。

　　6. 复杂度

　　单组时间复杂度为 O(n log n+m log n+knm)，空间复杂度为 O(nm)。两个整数 DP 表在 n=3000、m=1000 时合计约 23 MiB，不能只计算其中一层。对多组数据，应使用题面给出的 Σk≤200 估算总开销。

　　7. 参考代码

　　#include

　　#include "segment.h"

　　using namespace std;

　　const int MOD = 998244353;

　　void init(int c, int t) {}

　　std::vector

　　// 按左端点排序

　　vector

　　for (int i = 0; i < n; i++) v[i] = {l[i], r[i]};

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

　　vector

　　for (int i = 0; i < n; i++) { L[i] = v[i].first; R[i] = v[i].second; }

　　// nxt[x] = 第一个 L[i] > x 的下标

　　vector

　　for (int x = 0; x <= m; x++)

　　nxt[x] = upper_bound(L.begin(), L.end(), x) - L.begin();

　　int K = k;

　　// prev[i][r] = f[s-1][i][r], curr[i][r] = f[s][i][r]

　　vector

　　vector

　　// s=0: 选 0 条，任何状态都是 1 种方案

　　for (int i = 0; i <= n; i++)

　　for (int rr = 0; rr <= m; rr++) prev[i][rr] = 1;

　　vector

　　for (int s = 1; s <= K; s++) {

　　for (int i = 0; i <= n; i++)

　　fill(curr[i].begin(), curr[i].end(), 0);

　　for (int i = n - 1; i >= 0; i--) {

　　int ri = R[i];

　　// skip: curr[i][r] = curr[i+1][r]

　　memcpy(curr[i].data(), curr[i+1].data(), (m + 1) * sizeof(int));

　　// take: r=0 新开连通分量（取 i 后从 i+1 继续考虑延伸）

　　{

　　int add = prev[i + 1][ri];

　　int &dst = curr[i][0];

　　dst += add; if (dst >= MOD) dst -= MOD;

　　}

　　// take: r>0 且 L[i]<=r 延伸当前分量

　　for (int rr = L[i]; rr <= m; rr++) {

　　int nr = rr > ri ? rr : ri;

　　int cut = rr < ri ? rr : ri;

　　int nj = nxt[cut];

　　int add = prev[nj][nr];

　　int &dst = curr[i][rr];

　　dst += add; if (dst >= MOD) dst -= MOD;

　　}

　　}

　　ans[s] = curr[0][0];

　　swap(prev, curr);

　　}

　　vector

　　for (int i = 1; i <= K; i++) ret[i] = ans[i];

　　return ret;

　　}

　　代码核验：使用 C++11 编译并链接官方评测程序，官方公开数据 25/25 个测试点答案一致；另外对 15000 组小规模随机区间，与枚举子集判树的结果一致。这里报告的是本地验证结果。

　　8. 教练点评

　　本题的关键是把“区间图为树”转成“连通且覆盖深度不超过 2”，再把两条活跃区间之间不能继续选线段的部分整体跳过。解析中的状态、转移与代码必须一致；尤其不能用“先删除右端点为 x 的区间，再加入左端点为 x 的区间”处理闭区间。

　　T2 传送（teleport）

　　1. 题目概述与数据范围

　　n 个城市构成一棵树，编号为 0,…,n−1。沿一条边移动耗时 1；使用一次传送门也耗时 1，并等概率到达全部 n 个城市之一，包括当前城市。每次询问给出不同的起点 x 和终点 y，要求所有期望耗时有限的固定通行策略中的最小期望，返回最简分数。

　　官方限制为 2≤n≤5×，1≤m≤，0≤,且 ≠。时限 3.5 秒，内存 1024 MiB，20 个测试点等分。只需实现 teleport，返回长度恰好为 m 的 vector；每个测试点调用一次。

　　2. 题意翻译与建模

　　固定终点 y，设 (v) 为从 v 到 y 的最优期望， 为立即使用一次传送门的期望代价。传送后的分布与出发城市无关，所以 对所有 v 相同。

　　如果准备在走若干步后再传送，那么直接传送可以省掉之前的步数。因此最优选择只有沿最短路一直走到 y，或者立即传送；距离恰好等于 时，两者代价相同。

　　最后一个方程的左端关于 连续、严格递增（>0 时至少终点贡献 ），从 0 增长到无穷，因此有唯一解。查询答案就是 min(dist(x,y),)。

　　3. 部分分与特殊性质

　　测试点 1：n≤4、m≤20；测试点 2、3：n≤5、m≤30；测试点 4～6：n≤100、m=1。可以对每个终点求全部距离，再逐层计算精确分数，无需用浮点迭代恢复分数。

　　测试点 7、8：n≤1000、m≤2000，满足 A；测试点 9：n≤1000、m≤，无额外性质。A 表示第 i 条边恰好为 (i,i+1)，树是一条路径。

　　测试点 10、11：n≤、m≤，满足 A；测试点 12～15：同样的规模，没有额外性质。测试点 16：n≤5×、m≤5×，满足 B，即所有终点均为 0。测试点 17～20：n≤5×、m≤，无额外性质。

　　对相同终点缓存结果可以减少重复计算，但一般树上每个不同终点都完整 BFS 的最坏复杂度仍为 O(n²)，不能作为最大规模算法。

　　4. 正解思路

　　定义 (h) 为到 y 的距离不超过 h 的点数，(h) 为这些点到 y 的距离和。设 h 是使下式成立的最小非负整数：

　　则 h<≤h+1，并且：

　　这个半开区间的方向要保持一致。 为整数时，应取 h=−1；距离恰好等于 的点可走路也可传送，不影响答案。

　　用点分治预处理距离分布。对每个重心 c，保存当前连通块中到 c 的距离计数和距离和的前缀数组；同时对删除 c 后的每个分支保存同样的数组，距离仍然从 c 计算。距离是从 0 开始的整数，可按深度直接建立数组，不必排序或二分距离列表。

　　查询以 y 为中心、半径 h 的球时，沿 y 的重心祖先链，先加入重心 c 的整块统计，再减去 y 所在分支的统计。设 d=dist(y,c)，查数组的半径为 h−d，距离和还要加上 d 乘以点数。减去分支后留下的点，其到 y 的路径经过 c；每个点恰好在一个重心处计入。因此一次查询为 O(log n)。

　　还能去掉对每个终点的二分。若 y、z 在原树中相邻，则 |dist(v,y)−dist(v,z)|≤1。代入前面的单调方程可得 |−|≤1，因而两个最小整数半径 、 的差也不超过 1。

　　先求根的半径；随后按原树从父亲到孩子的顺序处理。孩子从 max(0,−1) 开始检查，最多检查三个半径就能找到自己的最小半径。根从 0 逐步检查，最多 O(n) 次，不改变整体复杂度。

　　5. 正确性与实现细节

　　令 (h)=(h+1)(h)−(h)。直接整理可得 (h+1)−(h)=(h+1)>0，所以半径判定具有单调性；第一个 (h)≥n 的位置正好满足 h<≤h+1。

　　相邻终点半径的证明也不依赖猜测：对任意 v，有 +1−dist(v,y)≥−dist(v,z)。将非负部分相加，y 的方程在 +1 处左端至少为 n，故 ≤+1；交换 y、z 得另一方向。

　　树上距离使用倍增 LCA。原树的遍历、子树大小计算和距离收集均使用显式序列，点分治本身只递归 O(log n) 层。距离和、分子以及比较中的乘法使用 long long；分母是点数，不超过 n。最终通过最大公约数约分。

　　6. 复杂度

　　点分治的深度计数数组、重心祖先信息及 LCA 预处理均为 O(n log n) 时间和空间；全部终点的半径计算为 O(n log n) 时间。m 次距离询问共 O(m log n)，返回答案另需 O(m) 空间。总时间为 O((n+m) log n)，总空间为 O(n log n+m)。

　　7. 参考代码

　　#include

　　#include "teleport.h"

　　using namespace std;

　　typedef long long ll;

　　const int MAXN = 500005, LOG = 20;

　　int n0, fa[LOG][MAXN], dep[MAXN], par[MAXN], siz[MAXN];

　　int ac[LOG][MAXN], ad[LOG][MAXN], ab[LOG][MAXN], alen[MAXN];

　　int rad[MAXN], bc;

　　ll num[MAXN], den[MAXN], qc, qs;

　　bool removed[MAXN];

　　vector

　　vector

　　int lca(int x, int y) {

　　if (dep[x] < dep[y]) swap(x, y);

　　int d = dep[x] - dep[y];

　　for (int j = 0; j < LOG; j++) if (d >> j & 1) x = fa[j][x];

　　if (x == y) return x;

　　for (int j = LOG - 1; j >= 0; j--)

　　if (fa[j][x] != fa[j][y]) x = fa[j][x], y = fa[j][y];

　　return fa[0][x];

　　}

　　ll gcdll(ll x, ll y) { return y ? gcdll(y, x % y) : x; }

　　// 只有点分治层数递归；原树的遍历均使用显式序列。

　　void build(int rt, int level) {

　　nd.clear(); nd.push_back(rt); par[rt] = -1;

　　for (int i = 0; i < (int)nd.size(); i++) {

　　int u = nd[i];

　　for (int v : e[u]) if (!removed[v] && v != par[u]) {

　　par[v] = u; nd.push_back(v);

　　}

　　}

　　int total = nd.size(), cent = rt;

　　for (int i = total - 1; i >= 0; i--) {

　　int u = nd[i], mx = 0; siz[u] = 1;

　　for (int v : e[u]) if (!removed[v] && par[v] == u) {

　　siz[u] += siz[v]; mx = max(mx, siz[v]);

　　}

　　mx = max(mx, total - siz[u]);

　　if (mx <= total / 2) cent = u;

　　}

　　removed[cent] = true;

　　cnt[cent].assign(1, 1);

　　ac[level][cent] = cent; ad[level][cent] = 0;

　　ab[level][cent] = -1; alen[cent] = level + 1;

　　for (int v : e[cent]) if (!removed[v]) {

　　int id = bc++;

　　subcnt[id].assign(2, 0);

　　nd.clear(); nd.push_back(v); par[v] = cent;

　　ad[level][v] = 1;

　　for (int i = 0; i < (int)nd.size(); i++) {

　　int u = nd[i], d = ad[level][u];

　　ac[level][u] = cent; ab[level][u] = id;

　　alen[u] = level + 1;

　　if ((int)cnt[cent].size() <= d) cnt[cent].resize(d + 1);

　　if ((int)subcnt[id].size() <= d) subcnt[id].resize(d + 1);

　　cnt[cent][d]++; subcnt[id][d]++;

　　for (int w : e[u]) if (!removed[w] && w != par[u]) {

　　par[w] = u; ad[level][w] = d + 1; nd.push_back(w);

　　}

　　}

　　subsum[id].resize(subcnt[id].size());

　　for (int d = 1; d < (int)subcnt[id].size(); d++) {

　　subsum[id][d] = subsum[id][d-1] + 1LL * d * subcnt[id][d];

　　subcnt[id][d] += subcnt[id][d-1];

　　}

　　}

　　sumd[cent].resize(cnt[cent].size());

　　for (int d = 1; d < (int)cnt[cent].size(); d++) {

　　sumd[cent][d] = sumd[cent][d-1] + 1LL * d * cnt[cent][d];

　　cnt[cent][d] += cnt[cent][d-1];

　　}

　　for (int v : e[cent]) if (!removed[v]) build(v, level + 1);

　　}

　　// 返回到 y 的距离不超过 h 的点数 qc 和距离和 qs。

　　void query(int y, int h) {

　　qc = qs = 0;

　　for (int j = 0; j < alen[y]; j++) {

　　int c = ac[j][y], d = ad[j][y], t = h - d;

　　if (t < 0) continue;

　　int r = min(t, (int)cnt[c].size() - 1);

　　qc += cnt[c][r]; qs += sumd[c][r] + 1LL * d * cnt[c][r];

　　int id = ab[j][y];

　　if (id >= 0) {

　　r = min(t, (int)subcnt[id].size() - 1);

　　qc -= subcnt[id][r];

　　qs -= subsum[id][r] + 1LL * d * subcnt[id][r];

　　}

　　}

　　}

　　vector

　　vector

　　n0 = n; bc = 0;

　　for (int i = 0; i < n; i++) {

　　e[i].clear(); cnt[i].clear(); sumd[i].clear();

　　subcnt[i].clear(); subsum[i].clear(); removed[i] = false;

　　}

　　for (int i = 0; i < n - 1; i++) {

　　e[u[i]].push_back(v[i]); e[v[i]].push_back(u[i]);

　　}

　　ord.clear(); ord.push_back(0); fa[0][0] = 0; dep[0] = 0;

　　for (int i = 0; i < n; i++) {

　　int a = ord[i];

　　for (int b : e[a]) if (b != fa[0][a]) {

　　fa[0][b] = a; dep[b] = dep[a] + 1; ord.push_back(b);

　　}

　　}

　　for (int j = 1; j < LOG; j++)

　　for (int i = 0; i < n; i++) fa[j][i] = fa[j-1][fa[j-1][i]];

　　build(0, 0);

　　for (int y0 : ord) {

　　int h = y0 ? max(0, rad[fa[0][y0]] - 1) : 0;

　　for (;; h++) {

　　query(y0, h);

　　if (n + qs <= 1LL * (h + 1) * qc) break;

　　}

　　rad[y0] = h; num[y0] = n + qs; den[y0] = qc;

　　}

　　vector

　　for (int i = 0; i < m; i++) {

　　int d = dep[x[i]] + dep[y[i]] - 2 * dep[lca(x[i], y[i])];

　　ll a = num[y[i]], b = den[y[i]];

　　if (1LL * d * b <= a) ans[i] = make_pair(d, 1);

　　else {

　　ll g = gcdll(a, b);

　　ans[i] = make_pair(a / g, (int)(b / g));

　　}

　　}

　　return ans;

　　}

　　代码核验：C++11 与官方评测程序链接成功，官方公开数据 20/20 个测试点答案一致。另在 5000 棵小树上，对所有有序起终点与逐终点 BFS 的精确分数结果比较，共 4486246 次询问一致。

　　8. 教练点评

　　先把全局传送代价写成一个未知数，期望问题就变成了距离分布问题。进一步利用相邻终点的代价差不超过 1，可以把“每个点独立二分”改成沿树传播半径。整数判定、分支去重和最简分数是实现中必须逐一对齐的细节。

　　T3 布丁（pudding）

　　1. 题目概述与评分规则

　　这是交互题。隐藏整数 w 满足 1≤w≤m≤3000。每次提交一个非空整数序列 A，元素必须在 [1,4500] 内，可以有重复值。交互库将 w 作为新元素加入，排序后返回相邻元素的 gcd 之和。交互库不是适应性的，w 在本次调用开始时已经确定。

　　每次 find_tastiness 最多询问 15 次，所有询问序列长度之和最多为 3000；任意违规或最终答案错误，该测试点得 0 分。时限 10 秒，内存 1024 MiB。选手实现 init 与 find_tastiness，通过 query_tastiness 询问；不能自行读出隐藏数。

　　官方有三个测试点，分值依次为 10、20、70。第 1 点 t=35、m=35；第 2 点 t=430、m=3000，保证 w 为质数；第 3 点 t=3000、m=3000，无额外性质。一般范围为 1≤t≤3000。

　　令 Q 为同一测试点中各次调用的最大询问次数，S 为最大总询问长度。得分是向下取整的 f(Q)·g(S)·该点分值。Q≤4 时 f(Q)=1；5≤Q≤15 时 f(Q)=。g(S) 的官方定义如下：

　　S≤35 时，g(S)=1；36≤S≤75 时，g(S)=1−(S−35)/100；76≤S≤235 时，g(S)=0.2+√((235−S)/1000)；236≤S≤3000 时，g(S)=0.2×。因此满分资源条件是 Q≤4 且 S≤35，这是题面明文规定。

　　2. 题意翻译与建模

　　一次询问会按返回值把候选数分组。设 A 已按升序排列，B(A) 是 A 本身的相邻 gcd 之和，R(A,w) 是把候选数 w 插入 A 后应有的返回值。枚举候选数并计算 R(A,w)，保留与实际返回值相同的那些数，就能缩小范围。

　　若 w 插入相邻的 x、y 之间，原来的 gcd(x,y) 被两个新贡献代替：

　　若 w 插到首尾，则只增加与原首项或末项的 gcd。代码用第一个不小于 w 的位置确定插入点；即使 w 与 A 中的元素相等，这个公式也成立。每次模拟只需定位插入点，并计算至多三个 gcd。

　　3. 部分分思路

　　如果直接询问 A=[1,2,…,m]，原序列相邻 gcd 之和为 m−1。隐藏的 w 与已有的 w 相邻后，额外贡献 w，因此返回值减去 m−1 就是答案。该方法 Q=1、S=m，在 m=35 的第 1 点已达到满分资源要求。

　　这个性质对任意升序候选集 C 都成立：只要真实 w 属于 C，询问 C 的返回值减去 C 原来的相邻 gcd 之和，就能得到 w。因此，满分方案可以先用短询问缩小候选集合，最后把剩余候选一起询问。

　　单元素询问只能得到 gcd(w,N)。例如许多大质数对同一个合数探针都会返回 1；多元素询问还利用插入位置造成的贡献变化，能进一步区分这些候选数。

　　4. 满分方案与固定询问的构造

　　第一次询问固定为 =[270,720,1200,1650,2145,2730]，长度为 6。它原来的相邻 gcd 依次为 90、240、150、165、195，总和是 840。不同插入区间会减去不同的旧贡献，有助于区分候选数。

　　这类询问可以通过交替改变两个因子的乘积来构造，使相邻元素保留一个较大的公共因子，再按候选数的分布调整间隔。构造时枚举全部候选数，评价每个返回值对应的集合大小，保留划分效果较好的询问。下面代码直接使用已经构造并完整核验的常量，运行时枚举比较七组备选询问。

　　令 表示 1～3000 中所有满足 R(,w)=r 的候选数。预处理按 r 分组；第一次实际询问后，取对应集合，并去掉大于 m 的数。最大的 有 129 个元素，其中大小超过 29 的集合恰好有 35 个。

　　若当前只剩一个候选，直接返回。若候选数不超过 29，直接询问整个候选集，此时总长度不超过 6+29=35。只有候选数超过 29 时，才需要第二次固定询问。

　　七组备选询问 ,…, 的具体数值见代码数组 a。对每个较大的 ，设第二次询问选择 后，某个返回值 v 对应的候选数最多为下式中的最大值。将询问 的长度和这个最大值相加，定义代价：

　　在 init 中枚举 j=1,…,7，选取代价最小的一组，存入 plan[r]。对这 35 个集合，逐一枚举全部候选数得到的最小代价均不超过 29，最大值恰好为 29。这个性质由代码中八行固定询问共同保证；修改这些常量后，需要重新核验。

　　第二次询问后，按实际返回值再次筛选。若只剩一个候选，就直接返回；否则询问整个剩余候选集，用返回值减去它原来的相邻 gcd 之和得到答案。m=1 时无需询问，直接返回 1。

　　5. 正确性证明

　　初始范围包含真实 w。每次筛选都使用公开题意精确计算 R(A,w)，并与交互库返回值比较，因此真实 w 始终保留，候选集不会为空。去掉大于 m 的数也不会删除真实答案。

　　候选集只剩一个元素时，它必然就是真实答案。否则将真实 w 再插入包含它的候选集，排序后相同的两个 w 相邻；所有原来的相邻 gcd 贡献仍保留，只多出 gcd(w,w)=w。故最后一次询问必能唯一确定答案。

　　所有固定询问都已升序排列，元素在 [1,4500] 内。最终询问中的候选数在 [1,m] 内，也满足范围要求。询问序列非空，且最终返回值正确。

　　6. 资源与复杂度

　　不进行第二次固定询问时，总长度至多为 6+29=35；进行第二次固定询问时，总长度至多为 6+(r)≤35。把 限制到 w≤m 后，每个返回值对应的候选数只会减少，因此同样的上界对全部 m≤3000 成立。总询问次数至多为 3，满足 Q≤4、S≤35 的满分条件。

　　记 U=3000、R=40005，大小超过 29 的初始集合数为 B=35。七组备选询问及其长度均为常数，预处理时间为 O(U log 4500+BR+R)，其中 BR 来自逐组清空 freq 数组；额外空间为 O(U+R)。单次 find_tastiness 至多处理 129 个候选数，时间为 O(129 log 4500)，最后一次询问的排序由交互库完成。

　　任意固定询问的长度至多为 8。加入 w 后有至多 8 对相邻元素，每个 gcd 至多为 4500，因此返回值不超过 36000，作为 MAXR=40005 的数组下标是安全的。最后一次询问只需要计算相邻 gcd 之和，不使用返回值作数组下标。

　　7. 参考代码

　　以下是洛谷 P17142 的完整提交代码。按洛谷题面要求，选择 C++17 或更高版本，直接复制整段提交即可。代码已声明 init、find_tastiness 和 query_tastiness；main 和 query_tastiness 的实现由交互库提供。洛谷版本使用这些声明代替 pudding.h。本地运行时，需要与官方 pudding_grader.cpp 一起编译。

　　#include

　　using namespace std;

　　void init(int c, int t);

　　int find_tastiness(int c, int m);

　　int query_tastiness(vector

　　// 每行第一个数是询问长度，其余数是布丁的美味度。

　　// 第 0 行用于第一次询问，第 1～7 行用于第二次询问。

　　int a[8][10] = {

　　{6, 270, 720, 1200, 1650, 2145, 2730},

　　{5, 504, 1575, 1980, 2210, 3600},

　　{7, 770, 854, 915, 975, 1040, 1120, 1190},

　　{5, 1200, 1300, 1404, 1512, 1568},

　　{8, 2232, 2294, 2368, 2432, 2508, 2574, 2652, 2720},

　　{5, 350, 420, 510, 595, 700},

　　{6, 1700, 1800, 1890, 1974, 2068, 2112},

　　{8, 44, 104, 156, 216, 2736, 2812, 2886, 2964}

　　};

　　const int MAXR = 40005;

　　vector

　　int base[8], plan[MAXR], freq[MAXR];

　　int cand[3005];

　　int my_gcd(int x, int y) {

　　return y ? my_gcd(y, x % y) : x;

　　}

　　// 按公开题意计算：若隐藏数是 w，第 id 组询问会返回什么。

　　int response(int id, int w) {

　　int k = a[id][0], p = 1, res = base[id];

　　while (p <= k && a[id][p] < w) p++;

　　if (p > 1) res += my_gcd(a[id][p - 1], w);

　　if (p <= k) res += my_gcd(w, a[id][p]);

　　if (p > 1 && p <= k)

　　res -= my_gcd(a[id][p - 1], a[id][p]);

　　return res;

　　}

　　int ask(int id) {

　　vector

　　for (int i = 1; i <= a[id][0]; i++) q.push_back(a[id][i]);

　　return query_tastiness(q);

　　}

　　void init(int c, int t) {

　　for (int r = 0; r < MAXR; r++) possible[r].clear();

　　memset(base, 0, sizeof(base));

　　for (int id = 0; id < 8; id++)

　　for (int i = 2; i <= a[id][0]; i++)

　　base[id] += my_gcd(a[id][i - 1], a[id][i]);

　　for (int w = 1; w <= 3000; w++)

　　possible[response(0, w)].push_back(w);

　　// 给每个较大的候选集合选择第二次询问。

　　for (int r = 0; r < MAXR; r++) {

　　if (possible[r].size() <= 29) continue;

　　int best = 3001;

　　for (int id = 1; id < 8; id++) {

　　memset(freq, 0, sizeof(freq));

　　int mx = 0;

　　for (int w : possible[r])

　　mx = max(mx, ++freq[response(id, w)]);

　　int cost = a[id][0] + mx;

　　if (cost < best) {

　　best = cost;

　　plan[r] = id;

　　}

　　}

　　// 这 7 组询问对所有合法候选集合均满足 best <= 29。

　　}

　　}

　　int find_tastiness(int c, int m) {

　　if (m == 1) return 1;

　　int r = ask(0), n = 0;

　　for (int w : possible[r])

　　if (w <= m) cand[n++] = w;

　　if (n > 29) {

　　int id = plan[r], res = ask(id), cnt = 0;

　　for (int i = 0; i < n; i++)

　　if (response(id, cand[i]) == res) cand[cnt++] = cand[i];

　　n = cnt;

　　}

　　if (n == 1) return cand[0];

　　// 真实答案就在 cand 中。再插入一次它，gcd 和恰好增加 w。

　　vector

　　int sum = 0;

　　for (int i = 0; i < n; i++) {

　　q.push_back(cand[i]);

　　if (i) sum += my_gcd(cand[i - 1], cand[i]);

　　}

　　return query_tastiness(q) - sum;

　　}

　　代码核验：C++17 编译并链接官方交互评测程序，三个测试点全部识别正确，最大资源分别为 (Q,S)=(2,16)、(3,35)、(3,35)，按官方评分公式得到 10+20+70=100 分。独立模拟器另穷举所有 1≤w≤m≤3000，共 4501500 组 (m,w)，答案全部正确，最大 Q=3、S=35。这些结果来自本地核验。

　　8. 教练点评

　　本题将交互策略分成两个任务：先设计短询问，把相同返回值对应的候选集合压小；再利用“候选集中已经包含真实答案”的性质完成识别。固定询问的资源保证依赖有限范围内的完整枚举，实际询问后的筛选与最终求值则有直接的等式证明。题解需要同时说明这两部分，才能解释代码为什么正确、为什么达到满分。

　　三、Day 2 三题详解

　　T1 中位数（median）

　　1. 题目概述与数据范围

　　把长度为 n 的序列划分成恰好 k 个非空连续段。每段求一次中位数，再对这 k 个中位数求中位数，最大化最终结果。本题的中位数是从大到小排序后第 ⌈长度/2⌉ 个数；偶数长度时取两个中间值中较大的那个。例如 [1,9] 的中位数是 9。

　　官方限制为 5≤n≤，2≤k≤n，1≤≤n。每个测试点有 1≤t≤20 组数据，所有组的 n 之和 N≤。时限 1 秒，内存 1024 MiB，20 个测试点等分。需实现 init 和 median；同一测试点会多次调用 median。

　　2. 二分答案与判定模型

　　二分答案 X，把 ≥X 的元素记为 +1，其余记为 −1。按照本题的较大中位数定义，一段的中位数至少为 X，当且仅当它的段和非负。奇数长度时段和不可能为 0，实际要求正数；偶数长度时段和为 0 也合法。

　　称段和非负的段为好段，其余为坏段。目标是恰好分成 k 段，其中至少 ⌈k/2⌉ 个好段。阈值 X 降低只会把部分 −1 变成 +1，故可行性单调。由于 1≤≤n，可以直接在整数区间 [1,n] 二分。

　　3. 部分分与特殊性质

　　测试点 1、2：N≤40、n≤20。测试点 3～6：N≤800、n≤80，其中 3～5 满足 A。测试点 7～9：N≤8000、n≤800，其中 7、8 满足 A。A 表示所有 ≤2。

　　测试点 10～15：N、n 均不超过 2×；k 的限制依次为 2、3、5（第 12、13 点）、不超过 10（第 14 点）、偶数（第 15 点）。测试点 16、17：N、n 均不超过 ，且 k>5；测试点 18～20：同样规模，无额外性质。

　　小规模可以枚举切点，或使用按前缀、段数、好段数分类的 DP。下面对 k≤5 使用精确 DP，对 k>5 使用有证明支持的线性判定。

　　4. k≤5 时的精确 DP

　　设 f[i][j][g] 为：处理前 i 个元素，已经闭合 j 个不作要求的段、g 个要求为好段的段，另有一个尚未闭合的当前段时，当前段和的最大值。未到达的状态设为负无穷。这里只记录最大段和，因为它对继续延长和判断能否闭合为好段都不劣。

　　加入第 i 个元素时，可以延长当前段；也可以把原当前段闭合为一个不作要求的段，然后新开一段；若原当前段和非负，还可将它闭合为一个要求为好段的段。最后闭合当前段，要求总计 floor(k/2) 个不作要求的段和 ceil(k/2) 个好段。

　　“不作要求”不等于“必须是坏段”：这些段也可以恰好是好段。这样恰好表示至少 ceil(k/2) 段为好段，不能将状态错误地解释为精确坏段数。两层滚动数组即可，单次判定为 O(nk²)。

　　5. k>5 时的线性判定与证明

　　记 C 为 +1 的总数。先让每个 +1 各形成一个好段，每个极大的连续 −1 块形成一个坏段。可以把长度为 1 的负块并入相邻的一个 +1，把长度为 2 的负块拆开并入两侧的 +1；每个 +1 最多接收一个 −1。这样好段数仍为 C，但坏段数减少。

　　从左到右处理负块。长度为 1 时优先使用左侧尚未占用的 +1，没有则使用右侧；长度为 2 时必须同时具有两个尚未占用的邻居。首尾负块只能使用内侧邻居。记处理后剩余负块数为 B。

　　这个贪心能消去最多的负块。使用空闲左邻居不会影响后面的块；需要使用右邻居时，如果某个最优方案把它留给后面的块，可以改为先消去当前块，至多失去后面的一个被消去块，消去总数不减。依次交换即可得到贪心方案。

　　还需证明 C−B 是任意划分能达到的最大“好段数减坏段数”。对任意一个段，设其中有 a 个 +1、q 个负块，总有 q≤a+1。坏段拆成上述基本形式后，差值至少为 −1。好段中的 −1 总数不超过 a，故 q≤a；如果 q≤a−1，拆开后的差值至少为 1；如果 q=a，则每个负块都只有一个 −1，至少可吸收一个，差值仍至少为 1。对原划分的所有段这样处理，再合并相接的负块；对于没有被完全吸收的负块，可将已吸收的边缘负数放回去，坏段数不增。整个过程不会降低差值。因此某个基本形式至少和任意原划分一样好；贪心又将基本形式的差值最大化，结论成立。

　　对于 k>5，最终判定条件为：C≥ceil(k/2)，且 k 为偶数时 C−B≥0，k 为奇数时 C−B≥1。前者保证有足够多的 +1 支撑好段，后者保证多数条件。

　　充分性还取决于能否调到恰好 k 段。若基本划分的段数小于 k，可以拆开负块，或把好段中吸收的 −1 拆出，每次增加一段且保持好段数 C，直到 k 段。若段数大于 k，先在奇偶性不一致时合并一对包含好段的相邻段，差值至多下降 1，仍满足所需多数条件。

　　此后每次合并三个相邻段，使段数减少 2。若好坏差值比最低要求至少多 2，任意三段合并后差值至多下降 2。若差值已经最低，只需找到三段中至少有两个坏段，合并后差值不会降低。若找不到，任意两坏段之间至少有两个好段；差值为 0 时总段数至多 4，差值为 1 时总段数至多 7。因此，在目标为偶数 k≥6 或奇数 k≥7、当前段数仍大于 k 时，一定能继续合并。这就证明了判定的充分性，也解释了为何小 k 需要单独处理。

　　6. 复杂度

　　二分进行 O(log n) 次。k≤5 时 O(nk²)，这里 k² 是常数；k>5 时 O(n)。总时间 O(n log n)，空间 O(n)，另有常数大小的滚动 DP。数组必须按 n≤ 开设，不能按 5× 估算。

　　7. 参考代码

　　#include "median.h"

　　#include

　　using namespace std;

　　void init(int c, int t) {}

　　const int inf = 1e9;

　　int p[1000005], b[1000005], N, K;

　　int f[2][6][6];

　　// j 个不作要求的段，k 个要求段和非负的段。

　　static bool finalOK(int j, int k) {

　　int cur = N & 1;

　　if (j >= 1 && f[cur][j-1][k] > -N) return true;

　　if (k >= 1 && f[cur][j][k-1] >= 0) return true;

　　return false;

　　}

　　// k<=5 时的精确 DP 判定

　　static bool check_dp(int x) {

　　int cnt = 0;

　　for (int i = 1; i <= N; i++) {

　　p[i] = (b[i] >= x ? 1 : -1);

　　if (p[i] == 1) cnt++;

　　}

　　p[N + 1] = 0;

　　int po = K / 2, op = (K + 1) / 2;

　　for (int j = 0; j <= po; j++)

　　for (int k = 0; k <= op; k++)

　　f[1][j][k] = -inf;

　　f[1][0][0] = p[1];

　　for (int i = 2; i <= N; i++) {

　　int cur = i & 1, prv = cur ^ 1;

　　for (int j = 0; j <= po; j++)

　　for (int k = 0; k <= op; k++)

　　f[cur][j][k] = -inf;

　　for (int j = 0; j <= po; j++)

　　for (int k = 0; k <= op; k++) {

　　if (f[prv][j][k] > -inf / 2)

　　f[cur][j][k] = max(f[cur][j][k], f[prv][j][k] + p[i]);

　　if (j && f[prv][j-1][k] > -inf / 2)

　　f[cur][j][k] = max(f[cur][j][k], p[i]);

　　if (k && f[prv][j][k-1] >= 0)

　　f[cur][j][k] = max(f[cur][j][k], p[i]);

　　}

　　}

　　return finalOK(po, op);

　　}

　　// k>5 时的贪心判定

　　static bool check_greedy(int x) {

　　int cnt = 0;

　　for (int i = 1; i <= N; i++) {

　　p[i] = (b[i] >= x ? 1 : -1);

　　if (p[i] == 1) cnt++;

　　}

　　p[N + 1] = 0;

　　if (cnt < (K + 1) / 2) return 0;

　　int num = 0;

　　for (int i = 1; i <= N; i++)

　　if (p[i] == -1 && p[i + 1] != -1) num++;

　　if ((K & 1) && cnt > num) return 1;

　　if (K % 2 == 0 && cnt >= num) return 1;

　　int ok = -1, lst = 0, now = 0, del = 0;

　　for (int i = 1; i <= N; i++) {

　　if (p[i] == -1) now++;

　　else {

　　if (now && ((lst && now <= 2) || (!lst && now == 1))) {

　　if (now == 1 && lst) {

　　if (ok == lst) ok = i; else ok = lst;

　　del++;

　　} else if (ok != lst) {

　　ok = i;

　　del++;

　　}

　　}

　　lst = i; now = 0;

　　}

　　}

　　if (now == 1 && ok != lst) del++;

　　num -= del;

　　if ((K & 1) && cnt > num) return 1;

　　if (K % 2 == 0 && cnt >= num) return 1;

　　return 0;

　　}

　　bool check(int x) {

　　if (K < 1 || K > N) return false;

　　if (K <= 5) return check_dp(x);

　　return check_greedy(x);

　　}

　　int median(int n, int k, std::vector

　　for (int i = 1; i <= n; i++) b[i] = a[i - 1];

　　N = n; K = k;

　　int lo = 1, hi = n, ans = 1;

　　while (lo <= hi) {

　　int mid = (lo + hi) / 2;

　　if (check(mid)) { ans = mid; lo = mid + 1; }

　　else hi = mid - 1;

　　}

　　return ans;

　　}

　　代码核验：C++11 与官方评测程序链接成功，官方公开数据 20/20 个测试点答案一致；对长度 1～15 的全部二值序列及所有合法段数，与独立区间 DP 比较，共 917506 次判定一致。小于题面最小规模的数据也用于检查边界，但不改变题面范围。

　　8. 教练点评

　　本题需要先严格对齐中位数定义，再证明“大段数时可以调整到恰好 k 段”。只统计 +1 和负块而不给出调整证明，或把小 k 的 DP 当作随机试错后的补丁，都不足以说明整个算法正确。

　　T2 木棉（kapok）

　　1. 题目概述与数据范围

　　给定长度 n 的数组 a。每个询问给出左闭右开区间 [l,r) 及两个结点 x、y。令 k=r−l+2，用 =min(,k−1)（0≤t）作为 Prüfer 序列，还原结点编号为 0,…,k−1 的树，判断 x、y 是否相邻。

　　官方限制为 1≤n,m≤2×，0≤，0≤l≤r≤n，0≤x,y。允许 l=r，也允许 x=y。空序列对应只有一条边 (0,1) 的二点树；同一结点不与自身相邻。

　　时限 2 秒，内存 1024 MiB，25 个测试点等分。实现 kapok，返回恰好 m 个布尔值，每个测试点调用一次。

　　2. Prüfer 解码与最后一条边

　　标准解码过程是：将各结点度数初始化为出现次数加一；依次取出编号最小的叶子，与当前 Prüfer 元素连边并删去该叶子；当前元素度数减一，若成为叶子则加入候选。最后将剩余两个结点相连。

　　最大编号 k−1 不会在前 k−2 步被删除：当它是叶子时，树中至少还有另一片编号更小的叶子；当它不是叶子时，更不可能被选中。因此最后一条边必含 k−1。

　　对于非空 Prüfer 序列，若最后一个元素为 p≠k−1，最后一条边就是 (p,k−1)。若最后一个元素等于 k−1，那么 k−1 在最后一次删除前始终不是叶子；k−2 一旦是叶子，就还有另一片更小的叶子，因此也不会先被删除，最后一条边为 (k−2,k−1)。空序列直接得到 (0,1)。下面的代码统一用删除时刻判断，无需读取空序列的末项。

　　3. 部分分与特殊性质

　　测试点 1、2：n,m≤500；测试点 3～5：n,m≤5000。可对每个询问直接解码；使用小根堆时单次 O(k log k)，采用 Prüfer 解码的线性指针实现时可做到 O(k)，不能把普通堆实现的复杂度写成 O(k)。

　　测试点 6、7：所有 <10；测试点 8、9：所有 <1000。测试点 10、11：所有询问的 x、y<10；测试点 12、13：所有询问的 x、y<1000。以上各组 n,m 均可到 2×。

　　测试点 14～16：给定 l、r 后，(x,y) 从全部合法有序点对中独立均匀随机产生。测试点 17～19：所有 r=n，这是固定右端点的后缀区间，不是前缀区间。测试点 20～22：n,m≤；测试点 23～25：n,m≤2×，均无额外性质。

　　4. 把删除时刻变成计数条件

　　考虑 x。设 t0 为 x 在当前 Prüfer 序列中最后出现的位置加一，没出现时 t0=0；从 t0 开始，x 才成为叶子。记 (t) 为后缀 ,…, 中严格小于 x 的不同值的个数。

　　编号小于 x 的结点共有 x 个；在第 t 步开始时，已有 x−(t) 个成为过叶子。定义 F(t)=x−(t)−t。随着 t 增加一，至多释放一个新的小编号叶子，所以 F 每步只会不变或减少 1。记 t* 为首次 F(t)≤0 的时刻，则 x 的删除时刻为：

　　为什么可以取这个最大值？在 F 首次降到 0 之前，每一步都有小于 x 的叶子，必须先删它们。在此之后，小编号叶子的积压至多为 1；若 x 尚未成为叶子，则在 x 最后出现的那一步，释放的是 x 而非更小的结点，之前的小编号积压也已处理完，所以 x 会在 t0 立即被删。若 t0 更早，就等到 t*。把 =k−2 视为没有在前 k−2 步删除。

　　由于 x，条件 与原数组 等价，截断操作不会影响这部分统计。问题只剩下离线维护“后缀中小于 x 的不同值数”。

　　5. 离线树套树与下标边界

　　令 next[p] 为原数组中 的下一次出现位置，没有则记 n。p 是该值在 [l,r) 内最后出现的位置，当且仅当 l≤p且 next[p]≥r。这里必须是大于等于：下一次恰好出现在 r，也已经位于询问区间之外。

　　按 x 从小到大离线处理，回答 x 的询问时，只插入 的位置。外层 Fenwick 按 p+2 维护，内层动态线段树按 next[p]+2 维护。回答完 x 的询问，再插入值等于 x 的位置，严格对应“小于 x”的定义。

　　固定 r、x，设 T 为所有满足 p、、next[p]≥r 的位置数；C(i) 为其中满足 p的位置数。对 i∈[l,r]，后缀 [i,r) 中小于 x 的不同值数就是 T−C(i)，因此所需条件为：

　　原位置 i 对应外层坐标 z=i+1；在这个坐标查询，恰好统计 p+2≤i+1，即 p。因此代码中的阈值 now=x+1+l−T。T=queryBIT(r+1,r+2,n)，其中 r+1 限定 p，r+2 限定 next[p]≥r。

　　函数 i−C(i) 单调不减，因为 i 每增加一，C(i) 最多增加一。Fenwick 从最高位向最低位倍增，找到最后一个不满足阈值的坐标 u，原数组中第一个满足条件的位置恰为 i=u；减去 l，再与 x 的最后出现位置加一取最大值，就得到 。

　　对 x、y 分别计算删除时刻。若 ，检查 min(,k−1) 是否等于 y；对 y 同理。若二者都未被删除，且 x≠y，则它们就是最后一条边的两端。最大结点直接将删除时刻设为 k−2。

　　6. 复杂度

　　每个位置插入 O(log²n)，每个端点询问的统计与 Fenwick 倍增均为 O(log²n)。总时间 O((n+m)log²n)。动态线段树的保守空间上界为 O(n log²n)，另需 O(n+m) 存储输入、分组与答案，不能未经证明将此实现的空间写成 O(n log n)。

　　7. 参考代码

　　#include "kapok.h"

　　#include

　　using namespace std;

　　// 动态开点线段树结点（按需 vector 申请，避免巨型静态数组）

　　struct Seg { int Ls, Rs, tot; };

　　static vector

　　static vector

　　static vector

　　static vector

　　static int newNode() { seg.push_back({0,0,0}); return (int)seg.size()-1; }

　　static int addSeg(int u, int x, int l, int r) {

　　 if (!u) u = newNode();

　　 seg[u].tot++;

　　 if (l == r) return u;

　　 int mid = (l+r)>>1;

　　 if (x <= mid) {

　　 int w = addSeg(seg[u].Ls, x, l, mid);

　　 seg[u].Ls = w;

　　 } else {

　　 int w = addSeg(seg[u].Rs, x, mid+1, r);

　　 seg[u].Rs = w;

　　 }

　　 return u;

　　}

　　static int querySeg(int u, int ql, int qr, int l, int r) {

　　 if (!u || ql > r || qr < l) return 0;

　　 if (ql <= l && r <= qr) return seg[u].tot;

　　 int mid = (l+r)>>1;

　　 return querySeg(seg[u].Ls, ql, qr, l, mid) + querySeg(seg[u].Rs, ql, qr, mid+1, r);

　　}

　　static void addBIT(int p, int nxt, int n) {

　　 for (int i = p; i <= n+1; i += i & -i) rt[i] = addSeg(rt[i], nxt, 1, n+2);

　　}

　　static int queryBIT(int p, int nxt, int n) {

　　 int s = 0;

　　 for (int i = p; i > 0; i -= i & -i) s += querySeg(rt[i], nxt, n+2, 1, n+2);

　　 return s;

　　}

　　vector

　　 vector

　　 (void)c;

　　 seg.assign(1, {0,0,0});

　　 rt.assign(n+5, 0); vec.assign(n+5, {}); q.assign(n+5, {});

　　 ans.assign(2*m, 0); a = A; // 值域到 n+1，按 n+5 开数组

　　 for (int i = 0; i < n; i++) vec[a[i]].push_back(i);

　　 for (int i = 0; i < m; i++) {

　　 int s = R[i]-L[i]+2;

　　 if (X[i]==s-1) ans[i<<1]=s-2; else q[X[i]].push_back({L[i],R[i],X[i],i<<1});

　　 if (Y[i]==s-1) ans[i<<1|1]=s-2; else q[Y[i]].push_back({L[i],R[i],Y[i],i<<1|1});

　　 }

　　 for (int i = 0; i <= n+1; i++) {

　　 // 回答时只包含值严格小于 i 的位置。

　　 for (auto query : q[i]) {

　　 int l = query[0], r = query[1], x = query[2], t = query[3];

　　 int lst=-1;

　　 auto it=upper_bound(vec[x].begin(),vec[x].end(),r-1);

　　 if(it!=vec[x].begin()) lst=*prev(it);

　　 int now=x+1+l-queryBIT(r+1,r+2,n);

　　 int u=0,v=0;

　　 for(int y=1<

　　 int tmp=querySeg(rt[u+y],r+2,n+2,1,n+2);

　　 if(u+y-v-tmp

　　 }

　　 ans[t]=max(lst-l+1,u-l);

　　 }

　　 for (size_t u = 0; u < vec[i].size(); u++)

　　 addBIT(vec[i][u]+2, (u+1

　　 }

　　 vector

　　 for (int i = 0; i < m; i++) {

　　 if (X[i]==Y[i]) continue;

　　 int s=R[i]-L[i]+2, flag=0, u=ans[i<<1], v=ans[i<<1|1];

　　 if (u

　　 if (v

　　 flag|=(u>=s-2 && v>=s-2); // 特殊边两端必含 k-1

　　 Ans[i]=flag;

　　 }

　　 return Ans;

　　}

　　代码核验：C++11 与官方评测程序链接成功，官方公开数据 25/25 个测试点答案一致；与独立的 Prüfer 解码器对拍 500000 次询问，覆盖空区间、重复值、截断及 x=y。动态结点容器扩容后可能改变存储地址，递归返回值先存入局部整数再写回，避免依赖 C++17 的赋值求值顺序。

　　8. 教练点评

　　这题真正需要固定的是三个口径：区间是 [l,r)，统计范围是编号严格小于 x 的结点，内层统计 next[p]≥r。代码中的每个“+1”“+2”都应能从这三个定义推出。随机对拍可以发现边界错误，但不能代替这些等价关系的证明。

　　T3 彩虹树（rainbow）

　　1. 题目概述与数据范围

　　给定一棵以 0 为根的树。对 1≤i，结点 i 的父亲为 ，且 0≤。每个结点可染任意颜色。记 为 u 的子树内不同颜色的个数，整个序列 (,…,) 称为缤纷度。

　　对每个集合 S⊆{1,…,n−1}，要求其中每个结点与某个严格祖先同色；不属于 S 的结点没有此要求，也可以与祖先同色。令 为满足限制的不同缤纷度序列数，求所有 之和，对 998244353 取模。

　　官方限制为 1≤n≤200。时限 1 秒，内存 1024 MiB，25 个测试点等分。实现 rainbow，参数 f 长度为 n，且 =0；每个测试点调用一次。

　　2. 计数对象与关键状态

　　同一个缤纷度序列可以由很多种染色实现，但对固定 S 只能计数一次；如果它在不同 S 下都可行，则分别计数。DP 要计数的是“子树中的 S 与缤纷度序列”，不能计数具体染色。

　　对固定的子树信息，令 x=，z 为使该信息可实现，严格祖先中最少需要提供的不同颜色数。z 是最小需求，不是某次具体染色与祖先实际共有的颜色数。同一份子树信息只有一个这样的最小值，这正是避免重复计数的关键。

　　定义 dp[u][x][z] 为具有上述 x 和最小需求 z 的子树信息数量。暂时允许祖先提供足够多的颜色，最后在根处只接受 z=0。根不能属于 S。

　　3. 部分分与特殊性质

　　测试点 1：n≤4；第 2 点：n≤8；第 3、4 点：n≤16；第 5～7 点：n≤50。测试点 8、9：n≤100 且满足 B；第 10～12 点：n≤100；第 13～15 点：n≤150。

　　测试点 16：n≤200 且满足 A；第 17～19 点：n≤200 且满足 B；第 20～25 点：n≤200，无额外性质。A 表示 =i−1，即链；B 表示每个结点至多有两个孩子。

　　n≤8 时可以枚举集合划分来表示染色，计算缤纷度以及“与某个祖先同色”的结点集 T；对每个 S⊆T，将缤纷度加入该 S 的集合去重。这里枚举的是有限的颜色等价关系，不是给无限种颜色逐一编号枚举。

　　4. 合并子树时的最小需求

　　先把 u 本身视为一个 (x,z)=(1,1) 的单元，再与所有孩子合并。设这些单元的颜色数及最小需求为 (,)，并记 A=Σ、B=Σ、=max 、=max 、d=A−B。

　　合并后的颜色总数 X 可以取 到 A 的任意整数。为了得到 X，需要使不同单元的颜色共减少 A−X 种。尽量让需要祖先提供的颜色重合后，最小需求为：

　　下界来自两个限制：合并后至少要满足需求最大的单元，所以 Z≥；每合并掉一种颜色，需求最多减少一，所以 Z≥B−(A−X)。这些界可以达到：先让各单元的需求颜色尽可能共用；达到共同的 种后，再合并其余颜色。颜色名称可任意重命名，不影响单元内部的缤纷度和祖先同色关系。

　　于是每份孩子信息对应一条先水平、后对角的最小需求折线。水平段是 X∈[,d+−1]、Z=；对角段是 Z∈[,B]、X=d+Z。水平段可能为空。因为 d+≥，两段不会交叉或遗漏。

　　例如两个单元均为 (2,1)，则 A=4、B=2、=2、=1，最小需求状态为 (X,Z)=(2,1)、(3,1)、(4,2)。这并不是全部具体染色的共有颜色状态，而是每个 X 唯一的最小需求。

　　5. 三组二维 DP 与正确性

　　不必把四个统计量一起放进高维状态。分别计算三组按同一批孩子信息求和的分布：P0[A][B] 统计两个和；P1[d][] 统计“差的和与需求最大值”；P2[][] 统计两个最大值。每合并一个孩子，按对应的加法或 max 运算做背包，权重乘以孩子的 dp。

　　用差分把这些分布还原成折线贡献。P0[A][B] 从 (A,B) 沿左下对角线累加；P1[d][m] 在 (d+m−1,m−1) 减去同样的权重，使对角段恰好停在 (d+m,m)。P2[p][m] 从 (p,m) 向右累加；P1[d][m] 在 (d+m,m) 减去，令水平段的右端恰好为 d+m−1。

　　这四种线性贡献相加，就得到合并分布 G[X][Z]。虽然三组 DP 分别保存的是边缘统计，每份孩子信息对折线的贡献本来就能拆成上述四项，逐项求和仍与逐份信息画折线完全等价，不需要假设统计量彼此独立。

　　最后处理 u。若 u∈S，它自己的颜色仍需由严格祖先提供，最小需求为 Z；若 u∉S，可让 u 提供一种原本需要祖先提供的颜色，最小需求变为 Z−1。初始化包含单元 (1,1)，故 Z≥1。这里仅描述最小需求的减少，不是强制 u 使用全新颜色。

　　上式适用于非根结点，两项分别对应 u∈S 与 u∉S。根只能取第二种选择，最终答案为 dp[0][X][0]。代码直接分两种选择转移，并对根排除第一种。

　　固定 S 和所有子树的缤纷度后，孩子信息及每个最小需求都唯一；X 的每个取值又确定父结点的缤纷度。因此折线上每个位置应加一次，而不能按颜色合并方式计数。水平段不包含拐点，保证它不会与对角段重复计数。

　　6. 复杂度与小例子

　　合并当前规模 a 与孩子规模 b 时，三组二维背包各至多 O(a²b²)。所有合并的 Σab=O(n²)，且 a²b²≤n²ab，所以总时间 O()；每次折线差分为子树大小的平方，总计不超过 O(n³)。保存全部结点的 dp 需要 O(n³) 空间，合并临时表为 O(n²)。

　　n=1 时答案为 1。三结点时，按 S=∅、{1}、{2}、{1,2} 的顺序，星形 0→1、0→2 的四个 为 3、2、2、1，总和是 8，与官方样例一致。链 0→1→2 的四个 为 4、2、3、1，总和是 10，不能把星形样例的 8 用到链上。

　　7. 参考代码

　　#include

　　#include "rainbow.h"

　　using namespace std;

　　const int MAXN = 205, MOD = 998244353;

　　int dp[MAXN][MAXN][MAXN], sz[MAXN];

　　int p[3][MAXN][MAXN], q[3][MAXN][MAXN];

　　int dg[MAXN][MAXN], hz[MAXN][MAXN];

　　vector

　　int add(int a, int b) {

　　 a += b;

　　 if (a >= MOD) a -= MOD;

　　 return a;

　　}

　　int sub(int a, int b) {

　　 a -= b;

　　 if (a < 0) a += MOD;

　　 return a;

　　}

　　bool cmp(int a, int b) { return sz[a] > sz[b]; }

　　int rainbow(int c, int n, vector

　　 for (int u = 0; u < n; u++) ch[u].clear();

　　 memset(dp, 0, sizeof(dp));

　　 for (int u = 1; u < n; u++) ch[f[u]].push_back(u);

　　 for (int u = n - 1; u >= 0; u--) {

　　 sz[u] = 1;

　　 for (int v : ch[u]) sz[u] += sz[v];

　　 }

　　 for (int u = n - 1; u >= 0; u--) {

　　 memset(p, 0, sizeof(p));

　　 p[0][1][1] = p[1][0][1] = p[2][1][1] = 1;

　　 int cur = 1;

　　 sort(ch[u].begin(), ch[u].end(), cmp);

　　 for (int v : ch[u]) {

　　 memset(q, 0, sizeof(q));

　　 for (int i = 0; i <= cur; i++)

　　 for (int j = 0; j <= cur; j++) {

　　 if (!p[0][i][j] && !p[1][i][j] && !p[2][i][j]) continue;

　　 for (int x = 1; x <= sz[v]; x++)

　　 for (int z = 0; z <= x; z++) {

　　 int w = dp[v][x][z];

　　 if (!w) continue;

　　 if (p[0][i][j]) {

　　 int t = 1LL * p[0][i][j] * w % MOD;

　　 q[0][i+x][j+z] = add(q[0][i+x][j+z], t);

　　 }

　　 if (p[1][i][j]) {

　　 int t = 1LL * p[1][i][j] * w % MOD;

　　 int a = i + x - z, b = max(j, z);

　　 q[1][a][b] = add(q[1][a][b], t);

　　 }

　　 if (p[2][i][j]) {

　　 int t = 1LL * p[2][i][j] * w % MOD;

　　 int a = max(i, x), b = max(j, z);

　　 q[2][a][b] = add(q[2][a][b], t);

　　 }

　　 }

　　 }

　　 cur += sz[v];

　　 memcpy(p, q, sizeof(p));

　　 }

　　 memset(dg, 0, sizeof(dg));

　　 memset(hz, 0, sizeof(hz));

　　 for (int i = 0; i <= cur; i++)

　　 for (int j = 0; j <= cur; j++) {

　　 dg[i][j] = add(dg[i][j], p[0][i][j]);

　　 hz[i][j] = add(hz[i][j], p[2][i][j]);

　　 if (j && i + j <= cur) {

　　 dg[i+j-1][j-1] = sub(dg[i+j-1][j-1], p[1][i][j]);

　　 hz[i+j][j] = sub(hz[i+j][j], p[1][i][j]);

　　 }

　　 }

　　 for (int x = cur; x >= 1; x--)

　　 for (int z = cur; z >= 1; z--)

　　 dg[x-1][z-1] = add(dg[x-1][z-1], dg[x][z]);

　　 for (int x = 1; x <= cur; x++)

　　 for (int z = 0; z <= cur; z++)

　　 hz[x][z] = add(hz[x][z], hz[x-1][z]);

　　 for (int x = 1; x <= cur; x++)

　　 for (int z = 1; z <= x; z++) {

　　 int w = add(dg[x][z], hz[x][z]);

　　 // u 不属于 S；根只能走这一种转移。

　　 dp[u][x][z-1] = add(dp[u][x][z-1], w);

　　 if (u) dp[u][x][z] = add(dp[u][x][z], w);

　　 }

　　 }

　　 int ans = 0;

　　 for (int x = 1; x <= n; x++) ans = add(ans, dp[0][x][0]);

　　 return ans;

　　}

　　代码核验：C++11 与官方评测程序链接成功，官方公开数据 25/25 个测试点答案一致；另对 n≤8 的 240 棵树枚举全部集合划分并逐个 S 去重，与 DP 一致，包含链和星形。代码使用三组二维合并表，解析与实现的 O() 复杂度一致。

　　8. 教练点评

　　本题最重要的状态不是“用了多少祖先颜色”，而是“至少需要祖先提供多少种颜色”。把可行性压缩为唯一的最小需求，才能在对缤纷度计数时去掉染色方案的重复；再将折线写成几项差分，才能让复杂度与 n=200 相匹配。

　　写在最后：从这届 NOI 看备赛方向

　　今年，优编程学员首次站上 NOI 赛场，获得 1 枚银牌、3 枚铜牌。其中两位长线学员自零基础入学、逐年进阶至今，说明信息学竞赛是一项可以长线规划、按部就班积累的事业。回到这六道题本身，命题人的意图也很清楚——不指望选手一眼看穿正解，而是把分数拆成一级一级台阶，优化一步、上一个台阶。segment 的覆盖深度、teleport 的不动点、median 的二分判定、kapok 的三维数点、rainbow 的折线压缩，都是这个思路。

　　五条备赛建议，按优先级：

　　• 一、把部分分爬坡练成习惯。 拿到题先看数据范围，先写能过最小子任务的暴力，再逐级优化。本届多道题设置了小规模或特殊性质测试点，一味死磕正解，反而可能拿不到前面台阶的分。

　　• 二、函数式和交互题专门练。 这届六道题都采用函数式提交，其中《布丁》是交互题。平时就要熟悉“实现函数、配 grader、本地对拍”这一套，不要到考场上第一次写。

　　• 三、把“特征→算法”练成稳定的条件反射。 区间图想弦图与 Helly，树上期望先写 Bellman 方程找常数项，区间中位数先二分答案再判定，Prüfer 过程先翻译成计数条件，小数据高维 DP 先把状态画成折线压维度。这张清单应内化为稳定的条件反射。

　　• 四、工程纪律与常数优化不丢。long long、边界、约分、对拍，是保障稳定得分的基本纪律。这届多道题算法思路不新，但常数压不进时限就拿不到满分——平时就要养成写干净、测极限数据的习惯。

　　• 五、建立大数据时限意识。n=5×10⁵、m=10⁶ 的数据越来越常见，O(n log²n) 都要算常数。练习时不仅应关注是否通过，更应评估最大数据规模下的实际运行时间。

　　竞赛是一件长期的事。不必和别人比进度，按自己的节奏把每一步走扎实——看清数据范围、写稳边界、遇到新题型愿意从部分分一步步往上爬，赛场自然会给答案。也希望大家各取所需：志在国决、强基保送的同学，把正解和常数研究透；打 NOIP、CSP-S 的同学，盯住命题方向；走综评、科技特长生渠道的同学，了解这条路长什么样就够了，不必都把 NOI 当成自己的目标。祝大家在接下来的 CSP-S、NOIP 中，走得稳、走得远。

　　资料来源与验证说明

　　本文六题的技术内容依据 CCF 官网《NOI 2026题目及数据》发布的第一试、第二试官方题面、六题头文件、正式评测程序及数据，并对照公开题解《NOI 2026 题解》。优编程学员获奖情况参考中国网教育 2026 年 8 月 5 日报道《优编程 4 名学员斩获 2026 NOI 竞赛 1 银 3 铜》。仅供教学参考；题目统计、子任务分值与选手成绩以 CCF 官方发布为准。

　　代码验证方式：六题均按官方头文件核对接口，并链接官网发布的正式评测程序。《布丁》按洛谷要求使用 C++17，其余五题使用 C++11，均启用 -O2。对非交互题逐点比较完整输出；对交互题检查识别正确性及实际资源消耗。官方比赛使用 C++14 和静态链接，本地编译及耗时不等同于比赛环境或线上评测。

　　官方公开数据核验：segment 25/25、teleport 20/20、median 20/20、kapok 25/25、rainbow 25/25，合计 115 个非交互测试点答案全部一致。本地单点最长耗时依次约为 0.91、2.79、0.38、0.95、0.40 秒；这些是本机观测值。

　　独立验证：线段使用子集枚举判树；传送使用 BFS 距离与精确分数，并额外核对 50 万结点长链上的 100 万次询问；中位数穷举长度不超过 15 的二值序列；木棉使用独立 Prüfer 解码器；彩虹树枚举小树的全部集合划分，另核对 200 结点链和星形的闭式答案。具体覆盖数量见各题代码说明。

　　pudding 的 3/3 个官方公开测试点全部识别正确，最大资源分别为 (Q,S)=(2,16)、(3,35)、(3,35)，按官方评分公式得到 100 分。独立模拟器穷举全部 4501500 组合法 (m,w)，最大 Q=3、S=35，满足题面的满分资源条件。正文代码可按洛谷 P17142 的要求，以 C++17 或更高版本直接提交，main 由交互库提供。

　　验证结果只覆盖上述公开数据、独立小规模比较与列出的边界构造；不将本地测试称为线上 AC。各题的状态定义、边界和复杂度均按正文代码说明，代码完整保留，小于号、大于号与逻辑运算符均为原字符。