CCPC2026网络热身-第二场 题解

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

题目索引

A. 潮汐灯带

标准评测 · ★ · 环形定长最大和

把长度为 n 的数组在末尾再接上前 k-1 个元素，得到长度 n+k-1 的线性数组，于是环上任意长度为 k 的连续段都变成普通窗口。先算前 k 个元素之和，再向右滑动窗口：每步加上进入的元素、减去离开的元素，同时记录当前窗口对应的起点编号。维护全局最大和，以及达到该和时最小的起点。n\le 2\times 10^5，滑动一遍即可。

时间复杂度 O(n)，额外空间 O(n)。

必须卡掉的错解：只在原数组上滑 n-k+1 个窗口，漏掉跨过编号 n 与 1 的段；或并列最大和时随便输出一个起点，而不是最小编号。

Tidal Light Strip

Standard · ★ · Fixed-length maximum sum on a circle

Append the first k-1 elements after the array so every circular window of length k becomes a linear window of length n+k-1. Compute the sum of the first window, then slide: add the entering value and subtract the leaving one, while tracking the corresponding start index. Keep the maximum sum and, on ties, the smallest start.

Time O(n), extra space O(n).

Wrong solutions that must fail: scanning only n-k+1 windows on the original array (missing wrap-around), or picking an arbitrary start when several windows share the same sum.

---

B. 暗水位

交互评测 · ★ · 有序试探

回答 1 表示试探值已经不低于水位，回答 0 表示还低。在 [0,10^9] 上维持可行区间，每次用区间中点缩小一半，第 32 次之内会剩下唯一整数。输出前刷新。

时间 O(1)，询问至多 32 次。

必须卡掉的错解：把回答 1 理解成严格大于，从而在水位恰好等于试探值时走到错误的一半；或不刷新，交互器读不到询问。

Hidden Waterline

Interactive · ★ · Ordered probing

Answer 1 means the probe is at least the waterline. Keep the feasible interval inside [0,10^9] and replace it by one half at the midpoint. At most 32 probes leave a single integer. Flush before reading the reply.

Time O(1), at most 32 queries.

Wrong solutions that must fail: treating 1 as a strict inequality, or forgetting to flush.

---

C. 浮桥配重

标准评测 · ★★ · 可撤销堆贪心

从左到右扫站点，余额先加 a_i，再把 b_i 丢进最大堆（表示“已到达、尚未启用”的装置）。若余额仍为负，就反复弹出堆顶最大的 b，加到余额上并计一次启用，直到余额非负或堆空。堆空仍为负则无解输出 -1。贪心正确性：亏空出现时，启用当前已有装置里增量最大的那件，能用尽量少的件数补回前缀亏空，且不会优于留着小件以后再用。

时间复杂度 O(n\log n)，空间 O(n)。

必须卡掉的错解：事先把所有 b_i 都算进可用总量，却未保证“只能在到达之后启用”，因而在前缀仍为负时提前使用了后面站点的装置。

Floating Bridge Ballast

Standard · ★★ · Greedy with a retractable max-heap

Scan stations left to right: add a_i to the balance, then push b_i into a max-heap of devices already reached. While the balance is negative, pop the largest available b, add it, and count one enable; if the heap is empty, output -1. When a deficit appears, taking the currently largest unused increment minimizes the number of enables needed for that prefix.

Time O(n\log n), space O(n).

Wrong solutions that must fail: assuming every b_i is available from the start, so later devices are used before their stations are reached.

---

D. 分尺传讯

题面

“凑够 k 段”指总段数不少于 k 即可，不要求恰好等于 k。

通信评测 · ★★ · 按成品段数取原料

第一轮只看得到原料和定尺，把 \lfloor a_i/L\rfloor 降序送出。第二轮才看到 k，按这个降序前缀累加，第一次达到 k 的根数就是答案。累加用比 64 位更宽的整数。

时间 O(n\log n)。

必须卡掉的错解：第一轮把段数按输入顺序送出，通不过降序核对；或把长度加总后再除以 L，那是把原料焊在一起。

Piece Telegram

Communication · ★★ · Take rods by piece yield

Round 1 sees the rods and L only, and must send \lfloor a_i/L\rfloor in non-increasing order. Round 2 sees k and walks that prefix until the sum reaches k. The sum needs an integer wider than 64 bits.

Time O(n\log n).

Wrong solutions that must fail: sending yields in input order, or dividing the total length by L.

---

E. 双泊对照

题面

角色编号不从标准输入读，由命令行参数给出，为 0 或 1。

多进程评测 · ★★ · 多重集比较

角色 0 把自己的清单排成非降序送出。角色 1 把自己的清单也排序，与收到的序列逐项比较。相等就是同一个多重集。两边都要输出这个比特，并且在写出后继续把协议走完，不能提前退出。

时间 O(n\log n)。

必须卡掉的错解：只比较两个序列是否原序相同；或角色 1 写完判断就退出，调度进程还没把比特交给角色 0。

Twin Manifests

Multiprocess · ★★ · Multiset comparison

Role 0 sends its list sorted non-decreasing. Role 1 sorts its own list and compares item by item. Both roles print that bit, and neither exits before the exchange is finished.

Time O(n\log n).

Wrong solutions that must fail: comparing the manifests in their original order, or exiting before the bit has been echoed.

---

F. 第二阵风

标准评测 · ★★★ · 次大值距离贡献

对排列中每个值 v，统计它作为某个子数组次大值时的距离贡献之和。从大到小插入位置：用有序集合维护已插入（更大）位置，并设哨兵 0 与 n+1。设 i=\mathrm{pos}[v]，左侧最近更大位置为 L_1、次近为 L_2，右侧最近为 R_1、次近为 R_2。当最大值在 L_1 时，左端点可取 (L_2,L_1]、右端点可取 [i,R_1)，贡献 (L_1-L_2)(R_1-i)(i-L_1)；当最大值在 R_1 时，左端点 (L_1,i]、右端点 [R_1,R_2)，贡献 (i-L_1)(R_2-R_1)(R_1-i)。所有长度 \ge 2 的子数组恰好被其最大值与次大值这对覆盖一次。

时间复杂度 O(n\log n)，空间 O(n)。

必须卡掉的错解：O(n^2) 枚举每个子数组找最大与次大；或只累加“最大值到端点的距离”而漏掉次大值这一侧的约束区间。

Second Gust

Standard · ★★★ · Distance contribution of the second maximum

For each value v in the permutation, add its contribution as the second maximum of some subarrays. Insert positions from largest to smallest into an ordered set with sentinels 0 and n+1. At position i of v, let L_1,L_2 be the nearest and second-nearest larger positions on the left, and R_1,R_2 on the right. If the maximum is at L_1, left ends lie in (L_2,L_1] and right ends in [i,R_1), contributing (L_1-L_2)(R_1-i)(i-L_1). If the maximum is at R_1, the symmetric product (i-L_1)(R_2-R_1)(R_1-i) applies. Every subarray of length at least 2 is counted once through its max–second-max pair.

Time O(n\log n), space O(n).

Wrong solutions that must fail: O(n^2) enumeration of every subarray, or summing distances only from the maximum without restricting the interval by the second maximum.

---

G. 逐潮探点

题面

隐藏读数对每组数据是固定的，不随询问改变；最后要输出的就是这组隐藏读数。样例 1 的隐藏读数是 1,3，输出 ! 1 2 会判错。

交互评测 · ★★★ · 顺序统计恢复

已经确定有 have 个读数严格小于下一个未知值时，在 [0,10^{18}] 上找最小的 x，使小于等于 x 的个数超过 have。这个 x 就是下一个取值，它的重复次数是该询问的回答减去 have。n\le 200 时询问次数不超过 15000。

时间 O(n\log A)。

必须卡掉的错解：把下界开成 1，从而丢失读数 0；或在 10^{18} 上用有符号加法把中点算溢出。

Tide Samples

Interactive · ★★★ · Order-statistic recovery

Once have values are known to be strictly smaller than the next unknown value, binary-search the least x in [0,10^{18}] whose count exceeds have. That x is the next value, and its multiplicity is the count minus have. With n\le 200 the query budget holds.

Time O(n\log A).

Wrong solutions that must fail: starting the range at 1 and dropping zeros, or overflowing the midpoint near 10^{18}.

---

H. 树潮报文

题面

第一轮把 n、父节点行、潮位行原样写回，轮次行不写回。

通信评测 · ★★★ · 树上路径最小值及其次数

第一轮把父节点和点权原样交回，第二轮才能看到询问。把路径两端爬到它们的交点，沿途统计最小值和次数。交点只计一次。n 和 q 都不超过 1500，沿父节点上爬即可。

时间 O(nq)，空间 O(n)。

必须卡掉的错解：第一轮改写了父节点；或把交点的潮位加了两次，询问一个点时次数变成 2。

Tree Tide Message

Communication · ★★★ · Path minimum and its multiplicity

Round 1 must echo the tree. Round 2 climbs both ends to their meeting vertex and counts the minimum, charging that vertex once. With n,q\le 1500, walking parent pointers is enough.

Time O(nq), space O(n).

Wrong solutions that must fail: altering a parent in the echo, or counting the meeting vertex twice.

---

I. 四段并港

题面

角色 0 也要先把自己的 m_r 和这 m_r 条边原样写回（不含 n），见样例 1 进程 0。

多进程评测 · ★★★ · 分边并查集

每个角色先把本段边原样交回，避免调度进程还在读时另一边已经退出。角色 0 收齐四段边后做并查集。两端相同的记录跳过。孤立港口各算一块。另外三个角色只复述角色 0 给出的个数，但必须等到这个整数送到再输出。

时间 O(n+m)，空间 O(n)。

必须卡掉的错解：把自环当成一条连接；或角色 1 到 3 在交回边表之后立刻结束，角色 0 的答案还没有被复述。

Four-Port Union

Multiprocess · ★★★ · Union-find on split edges

Every role echoes its own edges before waiting for the next message. Role 0 unions all four bundles and skips records whose ends are equal. Each isolated port is a component. The other roles print the count only after it arrives.

Time O(n+m), space O(n).

Wrong solutions that must fail: treating a loop as a join, or exiting before the count is echoed.

---

J. 封闭车站

标准评测 · ★★★★ · 点双树路径

删点使 s,t 不连通的点，恰是 s–t 简单路径上、且属于点双连通分量边界的割点（不含 s,t 自身）。用 Tarjan 求点双与割点，建割点–点双圆方树：割点节点权为 1，点双节点权为 0。每个原图点映射到对应树节点。查询时在树上对 bel[s] 与 bel[t] 求 LCA，用深度前缀和取路径上权值和，再若 s 或 t 本身是割点则各减 1。s=t 答案为 0。n,q\le 10^5，预处理倍增 LCA。

时间复杂度 O((n+m)\log n+q\log n)，空间 O(n\log n)。

必须卡掉的错解：统计 s–t 路径上全部中间点（非割点删了仍连通）；或只判断单个割点是否在路径上却漏掉路径上多个割点。

Closed Stations

Standard · ★★★★ · Paths on the block-cut tree

A vertex disconnects s from t iff it is a cut vertex on every s–t path, equivalently a cut vertex on the block-cut tree path between s and t, excluding the endpoints. Tarjan finds BCCs and cut vertices; build the block-cut tree with weight 1 on cut nodes and 0 on BCC nodes. Map each vertex to its tree node. For a query, sum weights on the tree path via LCA prefix sums, then subtract one for each endpoint that is itself a cut. Answer 0 when s=t.

Time O((n+m)\log n+q\log n), space O(n\log n).

Wrong solutions that must fail: counting every intermediate vertex on an s–t path, or checking only whether a single cut lies on the path while missing multiple cuts.

---

K. 根旁花簇

题面

“连通子树”指任意非空的连通顶点集合（连通诱导子图），不是“某点及其全部后代”。

标准评测 · ★★★★ · 换根生成函数

对每个根 r，统计含 r、恰含 K 个标记点的连通子图个数（模 998244353）。令 f_{u\to v}(x) 表示在 u 一侧、必须包含邻居 v 所在方向上的连通子图，对标记数的生成函数。向下 DFS：对儿子 v， f_{u\to v}=x^{m_v}\prod_{t\neq u}(1+f_{v\to t})。 向上换根时，用邻居方向上 (1+f) 的前缀积与后缀积，在 O(\deg) 内算出父方向的生成函数并下传。答案为 \bigl[x^K\bigr]\Bigl(x^{m_r}\prod_{v\sim r}(1+f_{r\to v})\Bigr)。 n\le 2000，K\le 20，多项式乘法截断到次数 K。

时间复杂度 O(n\cdot\deg\cdot K^2) 量级约 O(n K^2)，空间 O(nK)。

必须卡掉的错解：对每个根重新 DFS 一遍却不做换根，在 n=2000 上多出一个 n 因子超时；或把“诱导连通”理解成任意子集，丢掉树上连通约束。

Rootside Clusters

Standard · ★★★★ · Rerooting generating functions

For each root r, count connected subgraphs containing r with exactly K marked vertices, modulo 998244353. Let f_{u\to v}(x) be the generating function for connected subgraphs on u’s side that must include neighbor v. Downward DP: f_{u\to v}=x^{m_v}\prod_{t\neq u}(1+f_{v\to t}). Reroot with prefix/suffix products of (1+f) over neighbors to fill the parent direction. The answer is the coefficient of x^K in x^{m_r}\prod_{v\sim r}(1+f_{r\to v}). Polynomials truncate at degree K\le 20.

Time about O(n K^2), space O(nK).

Wrong solutions that must fail: restarting a full DFS from every root (O(n^2 K^2) at n=2000), or counting arbitrary subsets instead of connected induced subtrees.

---

L. 层叠花窗

题面

每一块占用的数值是固定的（第 1 块占最小的 s_1 个整数，以此类推），块内只能写成严格降序，不能自由填。

特判评测 · ★★★★ · 三角数分块构造

块内严格降序、块间数值递增时，逆序数恰好等于 \sum_i\binom{s_i}{2}。问题化为：把 n 拆成恰好 b 个正整数，使三角数和等于 K。用 DP：dp[p][s] 为用 p 段、总和为 s 时可达的三角数集合（bitset），转移枚举下一段长度 sz，并记录 prev_sz 以便回溯。若不可达输出 IMPOSSIBLE；否则还原 s_1,\ldots,s_b，再按块依次取下一段整数写成降序得到排列。n\le 40，状态可承受。

时间复杂度约 O(b\cdot n^2\cdot n^2/w)（bitset 加速），空间 O(b\cdot n\cdot n^2)。

必须卡掉的错解：输出任意逆序数为 K 的排列却不是“块内降序、块间递增”的结构；或 b=n 时仍对 K>0 给出方案（此时只能全为 1，逆序必为 0）。

Layered Rose Windows

Special judge · ★★★★ · Partition into triangular contributions

With strictly decreasing values inside each pane and increasing ranges across panes, the inversion count equals \sum\binom{s_i}{2}. Find positive integers s_1+\cdots+s_b=n with that triangular sum equal to K via DP on (parts used, sum used) with a bitset of achievable triangular totals, storing predecessors for reconstruction. If unreachable, print IMPOSSIBLE; otherwise emit the sizes and the concatenated descending blocks. n\le 40 keeps the DP feasible.

Time roughly O(b n^2\cdot n^2/w) with bitsets.

Wrong outputs that must fail: any permutation with K inversions that is not this blocked descending form, or a positive-K answer when b=n forces all sizes to be 1.

---

M. 开关仓库

题面

赛后题面把“向量”的说法统一成“整数”“元素”，题意和数据都没变。

标准评测 · ★★★★★ · 可回滚线性基区间计数

把每个整数的存活区间 [birth,death) 挂到时间线段树上，对时间轴 DFS：进入节点时把该节点上的整数插入可回滚线性基，离开时回滚。在叶子（单个操作时刻）若是查询 K，则在当前基上统计异或 <K 的子集数。计数时先把基化成行最简形，令 ways=2^{cnt-rk} 为核的倍数；再从高位到低位按 K 的二进制贪心：有主元的位按是否小于 K 的当前位累加 2^{rem}，无主元的位若已大于 K 则提前结束。答案乘 ways 后对 998244353 取模。B=20，Q\le 5000。

时间复杂度 O(Q\log Q\cdot B^2)，空间 O(Q\log Q+B\cdot Q)。

必须卡掉的错解：每次查询暴力枚举 2^{cnt} 个子集；或维护线性基时不可回滚删除，只能重建导致超时。

Switch Warehouse

Standard · ★★★★★ · Rollbackable basis with range counting

Place each integer on a time segment tree over its lifetime [birth,death). DFS the tree: insert those integers on enter, roll the basis back on leave. At a query leaf, count subsets with XOR <K on the current basis: reduce to RREF, multiply by 2^{cnt-rk}, then walk bits of K from high to low, adding 2^{rem} when a free choice stays below K. Modulo 998244353. Width B=20, Q\le 5000.

Time O(Q\log Q\cdot B^2).

Wrong solutions that must fail: enumerating 2^{cnt} subsets per query, or rebuilding the basis from scratch after every deletion instead of rolling back.

---

N. 二元镜室

题面

运算都在二元域 \mathbb F_2 上进行。样例说明里的“双曲块”只是对样例 1 矩阵的称呼，不是额外条件。

特判评测 · ★★★★★ · 二元域合同分解

在 \mathbb F_2 上对对称阵 B 做合同变换，化成对角块的直和：对角 1（秩一型）或 2\times 2 双曲块 \begin{pmatrix}0&1\\1&0\end{pmatrix}。操作是“同时交换两行两列”与“把第 i 行加到第 j 行并同步加列”，全部记录下来。对角 1 用一列标准基向量实现；每个双曲块用三列 \begin{pmatrix}1&1&0\\1&0&1\end{pmatrix} 实现。得到中间矩阵 Y 后，按记录的逆序把行变换作用回去，得到 X 满足 XX^{\mathsf T}=B。若分解所需列数少于给定 d，右侧补零列。保证有解且 d\le n+4。

时间复杂度 O(n^3)，空间 O(n^2)。

必须卡掉的错解：只对 B 做普通高斯消元求平方根却破坏对称合同结构；或输出行数、列数不对的矩阵导致 XX^{\mathsf T} 维数对不上。

Binary Mirror Room

Special judge · ★★★★★ · Congruence factorization over \mathbb F\_2

Reduce the symmetric matrix B by congruence operations (swap two rows and columns together; add row i into row j and the same for columns) to a direct sum of diagonal 1 blocks and hyperbolic 2\times 2 blocks \bigl(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\bigr). Realize each 1 by a single standard basis column and each hyperbolic block by three columns \bigl(\begin{smallmatrix}1&1&0\\1&0&1\end{smallmatrix}\bigr). Apply the inverse row operations to obtain X with XX^{\mathsf T}=B, padding zero columns up to the given d.

Time O(n^3), space O(n^2).

Wrong solutions that must fail: ordinary Gaussian elimination that breaks the congruence form, or emitting a matrix whose dimensions cannot satisfy XX^{\mathsf T}=B.