补题链接

• T841030 信号展开（decode）
• T841031 通道选址（passage）
• T841032 栈道分段（bridge）
• T841033 漏水检修（repair）

信号展开（decode）

简要题意

给定 $L$ 条记录，每条包含一个重复次数 $n$ 和一个字符，其中 $1\le L\le1000$、$1\le n\le79$，字符为大小写英文字母、数字、+ 或 -。按原顺序将每条记录的字符连续输出 $n$ 次，每条记录占一行，保持字符的大小写。

一句话题解

外层循环依次读取记录，内层循环输出指定次数的字符，再换行。

完整题解

按记录逐行展开

题目中的字符只是要显示的符号。即使字符是数字，也应重复书写这个字符，例如 3 2 要输出 222，而不是计算 $3\times2$。

依次处理每条记录：读入次数 $n$ 与字符 $c$，执行 $n$ 次输出 $c$ 的操作，再输出换行。每一条记录都单独处理，即使前后记录的字符相同，也不能合并它们的输出。

正确性说明

处理某条记录时，内层循环从 $1$ 到 $n$，每次恰好输出一次原字符 $c$，所以本行输出的字符及数量都符合该记录。随后换行，使这条记录与下一条记录的输出分开。

外层循环按照输入顺序处理全部 $L$ 条记录，不遗漏记录，也不改变顺序。因此最终的 $L$ 行信号完全符合题目要求。

复杂度

设所有记录的重复次数之和为 $S$。时间复杂度为 $O(L+S)$，额外空间复杂度为 $O(1)$。由于 $S\le79000$，直接按字符输出即可。

常见失误

• 混淆记录条数 $L$ 与某条记录的重复次数 $n$。
• 使用 j < n 但从 $1$ 开始循环，少输出一个字符。
• 每条记录处理完后没有换行，或在连续字符之间添加空格。
• 把数字字符当成数值计算，或者擅自改变字母大小写。

满分参考实现

#include<bits/stdc++.h>
using namespace std;
int l, n;
char c;
int main() {
	freopen("decode.in", "r", stdin);
	freopen("decode.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> l;
	for (int i = 1; i <= l; i ++) {
		cin >> n >> c;
		for (int j = 1; j <= n; j ++) cout << c;
		cout << "\n";
	}
	return 0;
}

---

通道选址（passage）题解

简要题意

给定长度为 $n$ 的正整数序列 $a$ 和整数 $k$，在保持原顺序的前提下，选择恰好连续的 $k$ 个元素，使它们的和最小，并输出最左的最优区间左端点。每组 $1\le k\le n\le5\times10^5$、$1\le a_i\le100$；每个文件至多 $10$ 组，所有组的 $n$ 之和不超过 $10^6$。

一句话题解

枚举每个长度为 $k$ 的区间，用前缀和在常数时间内求区间总和，从左到右扫描并仅在总和严格变小时更新答案。

完整题解

1. 先确定枚举什么

每段通道必须包含恰好 $k$ 块连续木板。如果左端点为 $l$，右端点就唯一确定为 $l+k-1$。

因此，所有合法选择恰好对应

$$1\le l\le n-k+1.$$

依次检查这些左端点，计算对应木板段的总费用，就不会漏掉任何方案。题目要求输出的是左端点编号，而不是最小费用。

2. 60 分：双循环直接求和

对于 $n\le2000$ 的测试点，可以用外层循环枚举左端点 $l$，再用内层循环把 $a_l,a_{l+1},\ldots,a_{l+k-1}$ 相加。

维护当前最小费用 best 和对应左端点 ans。从小到大枚举 $l$，只有新费用严格小于 best 时才更新。这样遇到相同费用时会保留较小的左端点。

一组数据需要做 $n-k+1$ 次求和，每次访问 $k$ 个数，时间复杂度为

$$O((n-k+1)k),$$

最坏为 $O(n^2)$，保存数组需要 $O(n)$ 空间。这种做法只需要循环、累加和比较，可以获得前 $12$ 个测试点的 $60$ 分。

由于所有费用都是正数，也可以在某次求和已经不小于当前最优值时提前结束。但在各段费用接近或相等的情况下，仍可能扫描几乎整个区间，最坏复杂度没有改变。

3. 满分：前缀和避免重复计算

相邻的区间包含大量相同元素，逐项重新相加做了许多重复工作。

定义前缀和

$$s_0=0,\qquad s_i=a_1+a_2+\cdots+a_i.$$

它可以在读入时按

$$s_i=s_{i-1}+a_i$$

依次计算。对于任意合法左端点 $l$，长度为 $k$ 的区间总费用为

$$s_{l+k-1}-s_{l-1}.$$

前一个前缀包含从 $1$ 到 $l+k-1$ 的全部元素，减去从 $1$ 到 $l-1$ 的元素，就只剩下所需区间。因此，每次求和只需常数时间。

先把第一个区间的费用 $s_k$ 作为 best，令 ans=1。随后从 $l=2$ 枚举到 $n-k+1$，仍只在费用严格减小时更新。

4. 正确性说明

每个合法方案都由一个左端点 $l\in[1,n-k+1]$ 唯一确定，算法恰好枚举这些左端点，既没有漏选，也没有把首尾相接的区间算进去。

前缀和之差准确等于该区间内各块木板的费用之和。扫描过程中，best 始终是已经检查过的区间的最小费用；只有严格更优时才更新，所以 ans 始终是达到这个费用的最左端点。

全部区间检查完后，这两个结论对所有合法方案成立，因此输出的 ans 就是题目要求的答案。

5. 另一种满分做法：滚动维护区间和

先求出编号 $1\sim k$ 的费用之和。将区间向右移动一格时，删除原左端点的费用，加入新右端点的费用即可。例如从 $[l,l+k-1]$ 移到 $[l+1,l+k]$，区间和更新为

$$\text{sum}\gets\text{sum}-a_l+a_{l+k}.$$

每次移动也只做常数次运算，同样能在 $O(n)$ 时间内求解，属于满分算法。并列时仍需保留较小的左端点。

6. 复杂度与边界

前缀和做法每组的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$；整个文件的时间复杂度为 $O(\sum n)$。

• $k=1$ 时，就是找最靠左的最小元素。
• $k=n$ 时，只有一个合法区间，答案为 $1$。
• 最后一个合法左端点是 $n-k+1$，不能漏掉。
• 每组都重新设置 s[0]、best 和 ans。已有的 s[1..n] 会被本组输入覆盖，不需要清空整张数组。
• 最大前缀和为 $5\times10^5\times100=5\times10^7$，本题使用 int 可以安全保存前缀和与费用。

7. 满分参考实现

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, k, s[N];
int main() {
	freopen("passage.in", "r", stdin);
	freopen("passage.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		s[0] = 0;
		for (int i = 1, x; i <= n; i ++) {
			cin >> x;
			s[i] = s[i - 1] + x;
		}
		int ans = 1, best = s[k];
		for (int i = 2; i + k - 1 <= n; i ++) {
			int sum = s[i + k - 1] - s[i - 1];
			if (sum < best) best = sum, ans = i;
		}
		cout << ans << "\n";
	}
	return 0;
}

---

栈道分段（bridge）题解

简要题意

给定按顺序排成一条链的 $n$ 个平台，以及 $m$ 对平台 $(a_j,b_j)$，其中 $a_j<b_j$。平台 $i$ 与 $i+1$ 之间各有一段双向栈道；求最少关闭多少段栈道，才能让每一对指定平台互不连通。每组 $n,m\le10^5$，要求不重复；每个文件至多 $10$ 组，$n$、$m$ 的总和分别不超过 $2\times10^5$。

一句话题解

把要求 $(a,b)$ 转成必须在 $[a,b-1]$ 中关闭至少一段栈道，按 $b$ 从小到大处理，遇到尚未满足的要求就关闭编号为 $b-1$ 的栈道。

完整题解

1. 从平台要求转成栈道区间

将平台 $i$ 与平台 $i+1$ 之间的栈道编号为 $i$。从平台 $a$ 到平台 $b$ 的唯一路径经过栈道 $a,a+1,\ldots,b-1$。

因此，让这两个平台不连通，等价于在区间 $[a,b-1]$ 中至少选择一个栈道编号并关闭它。原问题就变成：给定若干整数区间，用尽量少的整数位置，使每个区间都包含至少一个被选位置。

右端点是 $b-1$，不是 $b$。例如要求 $(1,2)$ 只能通过关闭平台 $1$ 与平台 $2$ 之间的栈道来满足；关闭平台 $2$ 右边的栈道没有作用。

2. 30 分：枚举所有关闭方案

当 $n\le16$ 时，只有至多 $15$ 段栈道。枚举每段栈道是关闭还是开放，总共 $2^{n-1}$ 种方案。

对一种方案，检查每个要求对应的栈道区间中是否至少有一段已经关闭。可以对关闭标记求前缀和，把每条要求的检查缩短为一次区间和查询；记录所有合法方案中关闭数量的最小值。

单组时间复杂度为 $O(2^{n-1}(n+m))$，空间复杂度为 $O(n+m)$。这些限制对应测试点 $1\sim6$，共 $30$ 分。

3. 贪心策略：优先处理最早结束的要求

在所有尚未满足的区间中，选出右端点最小的区间 $[L,R]$。我们一定要在这个区间里关闭至少一段栈道，而最好的选择是直接关闭最右边的 $R$ 号栈道。

直观上，当前区间必须被满足；把关闭位置尽量向右放，能给后面的区间留下更多被同一位置满足的机会。

这不是按左端点排序。比如三条要求为 $(1,4),(2,3),(3,4)$：前一条覆盖范围虽然很大，后两条却分别要求关闭 $2$ 号和 $3$ 号栈道，答案是 $2$。不能因为它们与同一个大区间相交，就认为关闭一次足够。

4. 为什么可以选择最右位置

只考虑尚未满足的区间，设其中右端点最小的区间为 $[L,R]$。

任意合法方案都必须在 $[L,R]$ 中选择某个位置 $p$。把这个位置改为 $R$，其他选择保持不变：

• $[L,R]$ 仍然被满足。
• 对于任何原来包含 $p$ 的其他剩余区间 $[l,r]$，有 $l\le p\le R$；由于 $R$ 是最小右端点，还存在 $R\le r$。因此这个区间同样包含 $R$。

修改不会让任何已由 $p$ 满足的剩余要求失效，也不会增加关闭数量。所以一定存在一个最优方案选择 $R$。

固定这一选择，去掉所有包含 $R$ 的区间，再对剩下的区间重复同样的操作，就得到了最优方案。

5. 60 分：每次重新扫描

直接实现上面的过程：每轮扫描尚未满足的全部要求，找出最小的 $b$，关闭 $b-1$ 号栈道；再扫描一遍，去掉已被满足的要求。

最多进行 $m$ 轮，每轮扫描至多 $m$ 条要求，单组时间复杂度为 $O(m^2)$，空间复杂度为 $O(m)$。把尚未满足的要求紧凑地放到数组前部可以减少常数，但最坏情况下仍为平方复杂度。

当 $m\le2000$ 时，这一做法可以通过；加上前一档，共可获得 $60$ 分。一般范围中有大量要求必须分别关闭不同栈道，扫描的轮数无法通过“已经满足就提前停止”降到很少。

6. 满分：排序后一次扫描

将全部要求按 $b$ 升序排序。维护 last，表示最近一次关闭的栈道编号，初始为 $0$。

处理要求 $(a,b)$ 时：

• 若 $last\ge a$，该要求已经满足。由于按右端点排序，已有 $last\le b-1$，因此 last 确实位于这条要求对应的区间中。
• 若 $last<a$，此前关闭的位置全都在 $a$ 左侧，该要求尚未满足。关闭 $b-1$ 号栈道，将 last 更新为 $b-1$，答案加一。

每次新选择的栈道编号都严格大于上一次；因此只记最后一次关闭的位置就足够，不需要记录全部方案。

排序耗时 $O(m\log m)$，扫描耗时 $O(m)$，空间复杂度为 $O(m)$。多组数据的总时间为 $O(\sum m_i\log m_i)$。答案不超过 $n-1$，普通 int 足够。

还可以按右端平台编号建桶：对于每个 $b$，只保留该右端点对应的最大左端点，再按 $b=2,3,\ldots,n$ 扫描。这是 $O(n+m)$ 的另一种完整做法，具有相同的贪心依据。

7. 实现中容易出现的问题

• 混淆平台编号和栈道编号，误把关闭位置写成 $b$。
• 仅判断区间之间有没有交集，或者把一串两两相交的区间合成一个要求。它们可能不存在共同的关闭位置。
• 按输入顺序、左端点顺序处理，然后只维护最后一次关闭位置。此前选择的位置可能落在后续区间的右侧，无法满足它。
• 每次选择覆盖要求最多的位置。局部覆盖数量最大不代表最终关闭次数最少；处理最早结束的要求才有上述交换证明。
• 多组数据之间没有重置答案、最近关闭的位置或用于标记的数组。

8. 满分参考实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Node {
	int l, r;
} a[N];
int n, m;
bool cmp(Node x, Node y) {
	if (x.r != y.r) return x.r < y.r;
	return x.l < y.l;
}
int main() {
	freopen("bridge.in", "r", stdin);
	freopen("bridge.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= m; i ++) cin >> a[i].l >> a[i].r;
		sort(a + 1, a + m + 1, cmp);
		int ans = 0, last = 0;
		for (int i = 1; i <= m; i ++) {
			if (last >= a[i].l) continue;
			last = a[i].r - 1;
			ans ++;
		}
		cout << ans << "\n";
	}
	return 0;
}

---

漏水检修（repair）题解

简要题意

给定一条数轴上 $n$ 个互异、非零的漏水点坐标 $x_i$，检修员从 $0$ 以单位速度移动，到达漏点可以瞬间修好；每处漏点在被修好之前每单位时间漏出 $1$ 单位水。求修好全部漏点时的最小总漏水量，也就是各漏点被修好时刻之和。每组 $n\le1000$、$|x_i|\le5\times10^5$；每个文件至多 $10$ 组，所有组的 $n$ 之和不超过 $2000$。

一句话题解

排序并加入起点 $0$，用区间 DP 维护已修好的连续区间和当前所在端点，每次向左或向右扩展一个点，增加“移动距离乘尚未修好的点数”。

完整题解

1. 先把总漏水量算清楚

如果第 $i$ 处漏点在时刻 $t_i$ 被修好，它恰好漏出了 $t_i$ 单位水，因此答案是所有 $t_i$ 的和。

这与“修完所有点的最短总路程”不同。即使最后走过的路程相同，先修好更多漏点，也可能减少总漏水量。每次选择最近的漏点也不一定最优，因为转向时仍在漏水的点数会影响代价。

直接按每处漏点累加修好时刻，会让人想记录已经用了多少时间。另一种等价算法更方便：如果某一段移动耗时 $d$，途中没有新修好漏点，而当时还有 $c$ 处漏点未修好，那么这段移动增加的总漏水量恰好为

$$c\times d.$$

按每段移动累加这个量，就等于按每处漏点累加漏水时间。这样，后续新增代价只取决于未修点数和当前所在位置，不需要额外记录当前时刻。

2. 为什么只考虑向区间两端扩展

修理不花时间，修好一个点不会妨碍后续行动。因此，检修员第一次经过某处漏点时，立即修好它一定不劣。

将所有坐标排序，并把起点 $0$ 加入序列。此后可以认为：每次修好新点时，所有已经经过的位置构成一个包含 $0$ 的连续区间，这个区间内的漏点都已经修好。

下一个新修好的漏点只能是区间左边紧邻的点，或者右边紧邻的点。不可能在不经过中间点的情况下先到达更远的点。若中途绕行却没有修好任何新点，删去绕行不会增加费用。

于是，处理完一个区间后，只需记录检修员是在区间左端，还是右端。

3. 状态和初始条件

加入 $0$ 后共有 $m=n+1$ 个位置，排序后记为 $a_1<a_2<\cdots<a_m$，其中 $a_p=0$。

定义：

• $f_{l,r,0}$：区间 $[l,r]$ 内的漏点已全部修好，检修员位于 $a_l$ 时，至此产生的最少总漏水量；
• $f_{l,r,1}$：同样处理好区间 $[l,r]$，但检修员位于 $a_r$ 时的最少总漏水量。

这里的“总漏水量”包括仍未修好漏点在此前已经漏出的水，不只是已修好漏点的贡献。这正是后续转移无需保存当前时刻的原因。

起点不是漏点，初始只有区间 $[p,p]$ 被处理，因此

$$f_{p,p,0}=f_{p,p,1}=0.$$

其他状态初始化为无穷大。只需处理满足 $l\le p\le r$ 的区间。

4. 转移

当前区间包含 $r-l+1$ 个位置，其中包括起点 $0$。尚未修好的漏点数为

$$c=m-(r-l+1).$$

若 $l>1$，下一处修理左边的 $a_{l-1}$：

$$f_{l-1,r,0}\gets\min\left\{ f_{l-1,r,0},\quad f_{l,r,0}+c(a_l-a_{l-1}),\quad f_{l,r,1}+c(a_r-a_{l-1}) \right\}.$$

若 $r<m$，下一处修理右边的 $a_{r+1}$：

$$f_{l,r+1,1}\gets\min\left\{ f_{l,r+1,1},\quad f_{l,r,0}+c(a_{r+1}-a_l),\quad f_{l,r,1}+c(a_{r+1}-a_r) \right\}.$$

按区间长度从小到大计算。所有漏点都修好后的答案为

$$\min(f_{1,m,0},f_{1,m,1}).$$

5. 正确性说明

先由“第一次经过就修好”的性质，将任意最优路线改成逐次扩展已修区间的形式而不增加漏水量。

对每一个这样的状态，下一个新修点恰好是左邻点或右邻点；从当前端点直达该点时，所增加的漏水量恰好为未修点数乘移动距离。转移枚举了当前所在两种端点和下一步两个方向，既没有漏掉合法的最优选择，也没有加入无法执行的操作。

由区间长度归纳，所有状态都记录了其定义下的最小总漏水量。最终区间覆盖所有点，取两种结束位置中的较小值即为全局最优答案。

6. 部分分做法

20 分：枚举访问顺序。 当 $n\le9$ 时，枚举漏点的所有排列，按相邻两次访问的距离累加当前时刻，再把每个到达时刻加到总量中，取最小值。即使某排列经过了尚未安排修理的点，它也只代表一种延迟修理的合法路线；最优排列一定包含第一次经过就修好的路线，因此枚举的最小值仍正确。时间复杂度 $O(n\cdot n!)$，空间复杂度 $O(n)$。

另外 20 分：所有漏点在同一侧。 沿着这一侧不断向外走、遇到就修即可，第 $i$ 个漏点的最早到达时刻就是 $|x_i|$，答案为 $\sum |x_i|$。这一做法为 $O(n)$。与小规模排列枚举结合，可得到 $40$ 分。

累计 60 分：只搜索下一个区间端点。 发现连续区间性质以后，每次只搜索左侧或右侧最近的未修点，按“距离乘未修点数”更新费用，不做记忆化。最坏时间复杂度为 $O(2^n)$，能处理 $n\le20$；当所有点同侧时，每一步只有一个方向，搜索本身也能在线性时间内完成，因此这条路线自然覆盖前三档。

100 分：区间 DP。 不同搜索路径可能到达同样的区间和端点；只保留最小代价，便得到上述 DP。

7. 复杂度与实现细节

每组时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。多组数据的总时间复杂度为 $O(\sum n_i^2)$；由单组 $n_i\le1000$ 和总量不超过 $2000$ 可控制总工作量。

实现时注意：加入的 $0$ 不是漏点；乘数是移动开始时尚未修好的点数；左右坐标都可能为负；每组必须重新初始化 DP。使用 long long 保存代价和乘法结果。

8. 满分参考实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010;
int n, a[N];
LL f[N][N][2];
int main() {
	freopen("repair.in", "r", stdin);
	freopen("repair.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		a[++ n] = 0;
		sort(a + 1, a + n + 1);
		int pos = lower_bound(a + 1, a + n + 1, 0) - a;
		memset(f, 0x3f, sizeof f);
		f[pos][pos][0] = f[pos][pos][1] = 0;
		for (int len = 1; len < n; len ++) {
			int cnt = n - len;
			for (int l = max(1, pos - len + 1); l <= pos && l + len - 1 <= n; l ++) {
				int r = l + len - 1;
				if (l > 1) {
					LL v = min(f[l][r][0] + 1LL * (a[l] - a[l - 1]) * cnt,
						f[l][r][1] + 1LL * (a[r] - a[l - 1]) * cnt);
					f[l - 1][r][0] = min(f[l - 1][r][0], v);
				}
				if (r < n) {
					LL v = min(f[l][r][0] + 1LL * (a[r + 1] - a[l]) * cnt,
						f[l][r][1] + 1LL * (a[r + 1] - a[r]) * cnt);
					f[l][r + 1][1] = min(f[l][r + 1][1], v);
				}
			}
		}
		cout << min(f[1][n][0], f[1][n][1]) << "\n";
	}
	return 0;
}