CCPC2026网络热身-第一场 题解

赛后补题用的简要题解。中文在前，英文在后。

题目索引

A. 漂移刻度

标准评测 · ★★★ · 区间投影式 DP

最小代价只需从左到右维护一个当前可达闭区间 [L,R]：每读入位置 i 的 [l_i,r_i]，若 [L,R] 与之相交则取交；若完全在左侧则把区间缩成 \{l_i\} 并加上 l_i-R；若完全在右侧则缩成 \{r_i\} 并加上 L-r_i。全程累加的就是最优总漂移，因为最优解里相邻取值总可以压到区间投影所给的最近合法点。

方案则要字典序最小。先从右往左做同一套投影，得到每个位置 i 在「兼顾右侧全部约束」后的可达区间 SR_i。然后 x_1 取 [l_1,r_1] 与 SR_1 交集的最左端点；对 i\ge 2，在 [l_i,r_i] 上选最小的 y，使 |y-x_{i-1}| 加上 y 到 SR_i 的距离最小——具体是先把「相对 x_{i-1} 且能落到 SR_i」的最优开区间算出来，再与 [l_i,r_i] 求交取左端，交空则取离该开区间更近的那一侧端点。

时间与空间均为 O(n)，n\le 2\times 10^5。

必须卡掉的错解：每个位置都取区间中点或都取 l_i，代价不是最优；或算出最优代价后随意构造一组可行序列，忽略字典序，例如样例 2 输出 2\ 2\ 1 而不是 2\ 1\ 1。

Drift Scales

Standard · ★★★ · Interval-projection DP

The minimum cost is obtained by maintaining a reachable closed interval [L,R] while scanning left to right. At position i, intersect with [l_i,r_i] when possible; if the current interval lies entirely to the left, collapse to \{l_i\} and add l_i-R; if entirely to the right, collapse to \{r_i\} and add L-r_i. The accumulated shift is optimal because adjacent optima can always be realized by projecting onto the next box.

For the lexicographically smallest sequence, first project from right to left to get, for each i, the interval SR_i that remains after all right-hand constraints. Choose x_1 as the leftmost point of [l_1,r_1]\cap SR_1. For later positions, pick the smallest y\in[l_i,r_i] minimizing |y-x_{i-1}| plus the distance from y to SR_i: form the optimal open segment relative to x_{i-1} and SR_i, intersect with [l_i,r_i], and if empty take the nearer endpoint.

Time and space O(n) for n\le 2\times 10^5.

Wrong solutions that must fail: always taking midpoints or all left endpoints; or reconstructing any optimal-cost sequence without the lexicographic rule (e.g. printing 2\ 2\ 1 on Sample 2).

---

B. 仿射暗码

交互评测 · ★ · 模域仿射恢复

询问 ?\,0 得到 b=f(0)，再问 ?\,1 得到 f(1)=a+b，于是 a\equiv f(1)-f(0)\pmod p。目标是解 ai+b\equiv y\pmod p，即

i\equiv a^{-1}(y-b)\pmod p。

p 为质数且 a\not\equiv 0，模逆用快速幂 a^{p-2}；乘法用 __int128 做 64 位模乘，避免 p 接近 10^9+7 时溢出。两次询问后输出 !\,i 并 flush。

时间 O(\log p)，询问恰好 2 次。

必须卡掉的错解：用 32 位乘法算模乘导致溢出；或只问一次就猜 a，在一般仿射下无法唯一确定逆像。

Affine Cipher

Interactive · ★ · Affine recovery over a prime field

Query ?\,0 for b=f(0) and ?\,1 for f(1)=a+b, so a\equiv f(1)-f(0)\pmod p. Solve ai+b\equiv y\pmod p by i\equiv a^{-1}(y-b)\pmod p. Invert with a^{p-2} via fast exponentiation; multiply with __int128 so products stay correct for primes near 10^9+7. Print !\,i and flush.

Time O(\log p), exactly two queries.

Wrong solutions that must fail: 32-bit modular multiplies that overflow, or attempting recovery from a single query.

---

C. 旋页索引

题面

字符串保证全是小写字母。每一轮要读的行写明后就输出；输出之前再读，对端还在等，不会给出结束符。

通信评测 · ★ · 循环移位编码

第一轮构造 B+B，在长度 2n 的串里用字符串匹配找子串 A 的起始下标 s（0\le s<n）；周期串时任意合法 s 均可。只把这一个整数交给第二轮。

第二轮读入 s 与公共串 B，对每个查询下标 q_j 输出 B_{(q_j+s)\bmod n}，共 q 个字符、中间无空格。两轮内存隔离，靠协议传入的 s 还原 A 的字符。

第一轮匹配 O(n)，第二轮 O(q)，n\le 2\times 10^5。

必须卡掉的错解：第一轮输出 A 相对 B 的反向移位（把 s 理解成 B 相对 A），第二轮全部取错字符；或试图在两轮之间写文件传整串 A。

Rotation Index

Communication · ★ · Cyclic-shift encoding

In the first run, search for A inside B+B and emit any legal offset s with 0\le s<n (any match works when B is periodic). In the second run, read s and public B, and for each query index q_j print B_{(q_j+s)\bmod n} as a contiguous string of q characters. The two runs do not share memory; only the protocol value s carries state.

First run O(n), second run O(q), with n\le 2\times 10^5.

Wrong solutions that must fail: using the opposite shift direction so every reconstructed character is wrong, or writing A to disk between runs.

---

D. 两端见证

题面

子数组是下标连续的一段。

标准评测 · ★★★ · 分治单调极值

对区间 [l,r] 分治：答案等于左右两半内部答案，加上跨越中点的合法子数组个数。在中点左侧向左扫，记录前缀最小/最大；在中点右侧向右扫，记录前缀最小/最大。再对左侧位置建前缀计数：有多少个左端点恰好取到左半的最小值（或最大值）。

跨越中点时分两类。第一类要求右端点是右半最大值，左端点是左半最小值，且左半最大值不超过该右端点、左半最小值大于右半最小值——对右端 t 单调推进左端指针，用前缀计数一次加上合法左端个数。第二类对称：右端是右半最小值，左端是左半最大值。长度为 1 的子数组在叶子直接计 1。

时间 O(n\log n)，空间 O(n)，n\le 2\times 10^5。

必须卡掉的错解：枚举所有 O(n^2) 子数组再扫一遍求最值，超时；或只统计「左小右大」一种朝向，漏掉「左大右小」的一半。

Endpoint Witness

Standard · ★★★ · Divide-and-conquer with monotone extrema

Recurse on [l,r]: add answers inside each half, then count witnesses crossing the midpoint. Scan leftward from mid for left-prefix min/max and rightward for right-prefix min/max; maintain prefix counts of left positions that realize the left-side minimum (or maximum).

Crossing pairs split into two families. When the right endpoint is the right-side maximum, count left endpoints that are the left-side minimum with left max \le that right value and left min > the right-side minimum, advancing pointers monotonically and reading the prefix counts. The symmetric family has right endpoint as right-side minimum and left as left-side maximum. Length-1 subarrays contribute 1 at the leaves.

Time O(n\log n), space O(n), n\le 2\times 10^5.

Wrong solutions that must fail: O(n^2) enumeration with a scan for extrema, or counting only the “left=min, right=max” orientation.

---

E. 分片中位线

题面

四个进程跑同一份程序，角色编号是 argv[1]，从 0 到 3。

多进程评测 · ★★★ · 分布式值域二分

四个角色各持严格递增分片，全局 N 为奇数，目标是合并后第 (N+1)/2 小的元素。角色 0 在整个 int64 值域上二分（用 __int128 表示上下界）：对候选 x 输出 ? x，四个角色各自用 upper_bound 返回本地 \le x 的个数，调度器把四者和回传给角色 0。若总数 \ge(N+1)/2 则收紧右界，否则抬高左界。收敛后输出 ! m，四个角色再各打印一遍 m。

每轮通信常数次，二分约 64 轮；本地每次查询 O(\log n_i)。大规模测例 N 约 10^5。

必须卡掉的错解：某个非 0 角色擅自二分或只统计本地中位数；或值域二分用普通 long long 算中点导致 LLONG_MIN/LLONG_MAX 溢出。

Sharded Median Line

Multi-process · ★★★ · Distributed binary search on the value domain

Four roles hold strictly increasing shards; global N is odd and the answer is the ((N+1)/2)-th element of the merged order. Role 0 binary-searches the full int64 range (bounds in __int128): it emits ? x, every role answers how many local values are \le x via upper_bound, and the manager returns the sum. If the sum is at least (N+1)/2, shrink the right bound; otherwise raise the left. After convergence, print ! m, and every role echoes m.

About 64 rounds of communication; each local count is O(\log n_i). Large tests have N around 10^5.

Wrong solutions that must fail: a non-coordinator computing a local median alone, or midpoint arithmetic that overflows at LLONG_MIN/LLONG_MAX.

---

F. 两夜树谱

通信评测 · ★★★ · 带权 Prüfer 码

第一轮按经典 Prüfer 消叶：用小根堆反复删当前编号最小的叶子，记录它唯一邻居，共 n-2 个父节点；同一删除顺序再记被删边的边权 n-2 个；最后补上剩余那条边的边权。一行输出这 2n-3 个整数。

第二轮按编码还原：由父节点序列恢复各点度数，同样用小根堆按叶删顺序连边并挂上对应边权，最后连接两个未删点。建树后对每个询问从 x 做一次 BFS（边权累加）得到到 y 的距离。n\le 2000，询问数 \le n，总时间约 O(qn)。

必须卡掉的错解：第一轮只传普通 Prüfer 父节点、丢掉边权，第二轮无法还原距离；或第二轮把编码当成邻接表直接读，长度对不上。

Two-Night Tree Spectrum

Communication · ★★★ · Weighted Prüfer code

In the first run, repeatedly delete the smallest-labeled leaf with a min-heap, recording its unique neighbor (n-2 parents) and the deleted edge weight (n-2 weights), then append the weight of the last remaining edge — 2n-3 integers in one line.

In the second run, rebuild degrees from the parent list, delete leaves in the same order while attaching the stored weights, and connect the last two vertices. Answer each query by a weighted BFS from x. With n\le 2000 and at most n queries, the cost is about O(qn).

Wrong solutions that must fail: shipping an unweighted Prüfer sequence without edge weights, or treating the code as an adjacency list of the wrong length.

---

G. 半度定向

特判评测 · ★★★★ · 指定出度定向

建分层网络：源连每条边容量 1；每条边再分别连向它的两个端点容量 1；每个点 v 连向汇、容量恰为给定出度 b_v。Dinic 求最大流，满流 m 时每条边恰好流向一个端点，该端点即为有向边的起点（出边）。按输入边序读残差：边节点到点 u 的容量变为 0 则定向为 u\to v，否则 v\to u。

n\le 400，m\le 4000，网络点数 O(n+m)，边数 O(m)，Dinic 足够。题面保证存在合法定向。

必须卡掉的错解：任意欧拉定向或随机定向，不满足每个点恰好 b_v 条出边；或把容量设成 \lfloor d_v/2\rfloor 而忽略题目给定的具体 b 向量。

Half-Degree Orientation

Special judge · ★★★★ · Orientation with prescribed out-degrees

Build a flow network: source to each edge with capacity 1; each edge to both endpoints with capacity 1; each vertex v to the sink with capacity b_v. A maximum flow of m (Dinic) orients every edge toward exactly one endpoint — the residual zero-capacity arc from the edge node marks the tail. Emit directed pairs in input order.

With n\le 400 and m\le 4000 the network is small enough. Feasibility is guaranteed.

Wrong solutions that must fail: any Eulerian or random orientation that ignores the exact vector b, or always using \lfloor d_v/2\rfloor instead of the given targets.

---

H. 三枝测绘

题面

树无根，叶子是度为 1 的点。要输出的边集唯一，顺序可以任意。样例 2 只是一次合法对话。

交互评测 · ★★★ · 三叶树距离恢复

叶子至多 3，树至多一条离开直径的支链。先从点 1 问遍所有点，取最远点 a；再从 a 问遍所有点，取最远点 b，则 a–b 是一条直径。再从 b 补全到其余点的距离（a 到 b 已有）。对每个点 i 令

\mathrm{hang}_i=\frac{d(a,i)+d(b,i)-d(a,b)}{2},\qquad \mathrm{pos}_i=d(a,i)-\mathrm{hang}_i。

\mathrm{hang}=0 的点按 \mathrm{pos} 排序连成直径路径；其余点挂在同一附着位置，按 \mathrm{hang} 升序串成唯一支链。询问次数约 3n，限制为 3n。

n\le 500。

必须卡掉的错解：按一般树用 n-1 次询问做启发式重建却暴力超限；或把所有 \mathrm{hang}>0 的点直接连到直径上同一点而不按挂接深度排序，支链边集会错。

Three-Branch Survey

Interactive · ★★★ · Distance recovery on a tree with \le 3 leaves

At most three leaves means at most one branch off a diameter. Query distances from 1 to find a farthest vertex a, then from a to find b (a diameter endpoint), then fill distances from b. For each i set \mathrm{hang}_i=(d(a,i)+d(b,i)-d(a,b))/2 and \mathrm{pos}_i=d(a,i)-\mathrm{hang}_i. Sort diameter vertices (\mathrm{hang}=0) by position and link them; sort off-diameter vertices by hang height and chain them from the unique attach point. About 3n queries, within the 3n limit.

n\le 500.

Wrong solutions that must fail: generic tree reconstruction that exceeds the query bound, or attaching every hanging vertex directly to the diameter without ordering by hang depth.

---

I. 潮门余时

题面

每个 S_i 始终非空，操作 1 改完之后也非空。

标准评测 · ★★★★ · 小状态 min-plus 矩阵

k\le 6，把每扇门建成 k\times k 的 min-plus 矩阵：入口余数 a 到出口余数 b 的最短耗时。对允许进入余数 u，等待 (u-a)\bmod k，穿越耗时 c，离开余数 (u+c)\bmod k，取所有 u 的最小值。连续多扇门对应矩阵复合（min-plus 乘法）。

用线段树维护区间矩阵积：单点修改更新一扇门的矩阵，询问 [l,r] 取出复合矩阵，在起点余数 s 对应的那一行取最小可达出口。矩阵乘法 O(k^3)，线段树每次 O(k^3\log n)。n,q\le 2\times 10^4。

必须卡掉的错解：询问时对区间逐门模拟最短路，单次 O((r-l)k^2)，在 q 次大区间询问下超时；或把等待写成 |u-a| 而不是环上最短非负等待 (u-a)\bmod k。

Tide Gate Residues

Standard · ★★★★ · Min-plus matrices of small state

With k\le 6, represent each gate by a k\times k min-plus matrix: for arrival residue a and allowed entry u, wait (u-a)\bmod k, pay crossing time c, and leave at (u+c)\bmod k. A sequence of gates composes by min-plus matrix multiplication.

A segment tree stores interval products: point updates rebuild one gate matrix; a range query returns the composed matrix, and the answer is the minimum entry in the row of the starting residue s. Multiplication costs O(k^3); each update/query is O(k^3\log n). Constraints: n,q\le 2\times 10^4.

Wrong solutions that must fail: simulating each query gate-by-gate in O((r-l)k^2) over many large ranges, or using |u-a| instead of the cyclic wait (u-a)\bmod k.

---

J. 群岛外缘

题面

凸包退化为线段时，周长平方和含闭合边。没有点的角色只输出一行 0。

多进程评测 · ★★★ · 局部凸包合并

角色 1,2,3 对本地点集做 Andrew 单调链凸包（叉积用 __int128，共线点用叉积 \le 0 弹出，只留端点），把至多 30 个顶点发给调度器。角色 0 把自己的局部凸包与收到的三个凸包顶点并成一点集，再算一次全局凸包。输出顶点数、有向面积两倍的绝对值、以及闭合多边形上每条边 (\Delta x)^2+(\Delta y)^2 之和。

各角色局部 O(n_i\log n_i)；合并时顶点数常数级，全局再 O(1) 量级排序建包。

必须卡掉的错解：非协调角色发送全部原始点而不是局部凸包，通信量与终裁约定不符；或叉积用 64 位乘法在坐标 \pm 10^6 时溢出。

Archipelago Rim

Multi-process · ★★★ · Merging local convex hulls

Roles 1,2,3 compute Andrew monotone-chain hulls of their points (cross products in __int128, popping on \le 0 so collinear interior vertices disappear) and send at most 30 vertices each. Role 0 unions its own hull vertices with the three received hulls and recomputes the global hull, then prints the vertex count, the absolute doubled directed area, and the sum of squared edge lengths over the closed polygon.

Local work is O(n_i\log n_i); the merged instance has a constant-size vertex set.

Wrong solutions that must fail: shipping every raw point instead of the local hull, or 64-bit cross products that overflow at coordinate magnitude 10^6.

---

K. 树冠折光

题面

以节点 1 为根。

标准评测 · ★★ · 沿祖先链枚举

以 1 为根 DFS 记录父指针与到根带权深度。对每次询问 (v,q)，从 v 沿父链走到根，对每个祖先 u 检查 \mathrm{dist}(v,u)=\mathrm{dep}[v]-\mathrm{dep}[u]\le R_u，若合法则用代价 \alpha_u\cdot q+\beta_u+\mathrm{dist}(v,u) 更新答案。自身距离为 0，故至少有一个合法选择。

n,Q\le 800，枚举祖先总复杂度 O(nQ)，空间 O(n)。数据规模下无需再上李超结构。

必须卡掉的错解：只在 v 的儿子或整棵子树里选反射器，而不是祖先链；或比较深度差时忘记边权、按边数当距离。

Canopy Refraction

Standard · ★★ · Walking the ancestor chain

Root the tree at 1 and store parents with weighted depths. For each query (v,q), walk from v to the root; for every ancestor u with \mathrm{dist}(v,u)=\mathrm{dep}[v]-\mathrm{dep}[u]\le R_u, update the answer by \alpha_u\cdot q+\beta_u+\mathrm{dist}(v,u). Distance 0 to v itself always yields a feasible choice.

With n,Q\le 800, enumerating ancestors costs O(nQ) and needs only O(n) memory; no Li Chao structure is required at this scale.

Wrong solutions that must fail: searching among children or the whole subtree instead of ancestors, or treating unweighted hop counts as distances.

---

L. 换色巡航

题面

d_{\mathrm{red}}(v)、d_{\mathrm{blue}}(v) 分别是点 v 的红边条数、蓝边条数。

特判评测 · ★★★★ · 欧拉转移配对

上界 U=\sum_v\min(d_{\mathrm{red}}(v),d_{\mathrm{blue}}(v)) 已由题面给出。实现上用带颜色偏好的 Hierholzer：在每个点把红边与蓝边交错排进邻接表，遍历时优先走与上一色不同的未用边，得到一条欧拉回路。再对起点、初始偏好色、红蓝谁先交错做若干确定性枚举；若异色次数仍低于 U，则对邻接表随机打乱并重复数百到数千次试验，保留异色次数最大且确实走完 m 条边的闭回路。

n\le 300，m\le 2000。输出边的输入编号（1-based）顺序即可。

必须卡掉的错解：普通 Hierholzer 不交错颜色，在红蓝混杂图上异色次数远低于 U；或输出开路径 / 漏边，不构成欧拉回路。

Recolor Cruise

Special judge · ★★★★ · Euler tour with color-alternating transfers

The optimum equals U=\sum_v\min(d_{\mathrm{red}}(v),d_{\mathrm{blue}}(v)). Run Hierholzer with a color preference: interleave red and blue edges in each adjacency list and, while traversing, prefer an unused edge whose color differs from the previous one. Enumerate starts, initial preferred colors, and which color leads the interleaving; if the number of color changes is still below U, shuffle adjacency lists for a few hundred to a few thousand random trials and keep the best closed tour that uses every edge once.

n\le 300, m\le 2000. Print the 1-based input edge indices along the circuit.

Wrong solutions that must fail: plain Hierholzer without color interleaving (far below U on mixed graphs), or emitting a trail that is not a closed Eulerian circuit.

---

M. 时裂约束

题面

总收益的最大值不取模，只对达到该最大值的方案数取模。

标准评测 · ★★★★★ · 时间线段树上的可回滚异或并查集

把时间轴 [1,q] 建成线段树。每条约束从加入时刻活到删除前一刻（或一直活到 q），挂到 O(\log q) 个线段树节点；每个变量的收益同理，按「上次修改到本次修改前」切成时间段挂上。DFS 线段树时，进入节点就把其上的约束 / 收益用可回滚结构加上，离开时弹栈撤销。

并查集维护相对异或：按秩合并，连边时记录子根相对父根的异或；同根若推出矛盾则 bad_cnt++。每个连通块维护把根取 0 / 取 1 时的收益和 g_0,g_1。询问时若 bad_cnt>0 输出 0，否则对每个根取 \max(g_0,g_1) 累加，两边相等则方案数乘 2，对 998244353 取模。收益和用 __int128：单次收益已是 |p|\le 10^{18}，n 个加起来会超过 long long。

n\le 2000，q\le 4000，总复杂度约 O((n+q)\log q\cdot\alpha(n))。

必须卡掉的错解：每次询问从空并查集重建当前所有约束，在 q 次询问下超时；或合并连通块时忘记按异或翻转交换 g_0 与 g_1，导致最大收益算错。

Temporal Constraints

Standard · ★★★★★ · Rollback XOR DSU on a segment tree of time

Build a segment tree over times [1,q]. Each constraint lives from its insertion until just before deletion (or through q) and is stored on O(\log q) nodes; profit updates are likewise cut into time intervals. DFS the tree: apply the node’s constraints and profits with a rollback stack on entry, then undo on exit.

The DSU stores relative XOR with union by size; same-component contradictions increment bad_cnt. Each component tracks profit sums g_0,g_1 for the root being 0 or 1. A query prints 0 if bad_cnt>0; otherwise sums \max(g_0,g_1) over roots and multiplies ways by 2 on ties, modulo 998244353. Profit sums use __int128: one profit is already up to 10^{18}, and n of them overflow long long.

n\le 2000, q\le 4000, total about O((n+q)\log q\cdot\alpha(n)).

Wrong solutions that must fail: rebuilding the DSU from scratch on every query, or merging components without swapping g_0 and g_1 when the linking XOR is 1.

---

N. 异或续航林

题面

n 的上界 1500 是对的，数据里有 n=1500。

标准评测 · ★★★ · 从每个点检查路径

对每个起点 s=1\ldots n，从 s 做 DFS：携带当前距离与路径节点异或（含端点标签）。每当走到编号大于 s 的点 u，若 \mathrm{dist}\le k_s、\mathrm{dist}\le k_u 且异或为 0，答案加一。这样每个无序对 \{s,u\}（s<u）恰好检查一次。

n\le 1500，总复杂度 O(n^2)，空间 O(n)。规模下直接枚举即可，不必上点分治与二维偏序结构。

必须卡掉的错解：路径异或只异或边权或漏掉端点标签；或只检查 \mathrm{dist}\le\min(k_u,k_v) 之外又漏掉「两侧续航都要满足」写成只约束一侧。

XOR Endurance Forest

Standard · ★★★ · Checking paths from every vertex

For every source s=1\ldots n, DFS from s while tracking distance and the XOR of node labels on the path (including endpoints). Whenever a vertex u>s is reached with \mathrm{dist}\le k_s, \mathrm{dist}\le k_u, and XOR 0, increment the answer. Each unordered pair is examined once.

With n\le 1500 this is O(n^2) time and O(n) memory — enough without centroid decomposition or a 2D data structure.

Wrong solutions that must fail: XORing edge weights only or omitting an endpoint label, or enforcing the endurance bound on only one of the two endpoints.