补题链接

• T1 能量吸收（absorb）
• T2 铜牌名次（bronze）
• T3 分组核验（group）
• T4 候晴行程（travel）
• T5 巡检路线（patrol）
• T6 环线分区（district）

讲题录屏

录制: CSP-J&S模拟赛第2场

日期: 2026-10-02 19:01:44

录制文件：https://meeting.tencent.com/crm/29r6EyLP96

密码：HGNO

T1 能量吸收（absorb）

简要题意

每组给定初始能量 $d$ 和按顺序排列的 $n$ 个正整数能量块。只有 $a_i$ 严格小于当前能量时才能吸收，并将当前能量增加 $a_i$；否则立即停止，不再处理后面的能量块。求最终能量。

数据范围：$1\le n\le10^5$，$1\le d,a_i\le10^9$。每个文件至多 $10$ 组数据，所有组的 $n$ 之和不超过 $2\times10^5$。

一句话题解

先把数组完整读入，再按顺序模拟；能够吸收就累加，第一次不能吸收时直接退出模拟循环。

完整题解

从题意到程序

题目已经给出了唯一的接触顺序，不能重新排序，也不能跳过当前能量块去吸收后面的能量块。因此不需要设计选择策略，直接执行题目描述的过程即可。

用变量 $d$ 保存当前能量。从前往后枚举 $a_i$：

• 若 $a_i<d$，执行 $d\leftarrow d+a_i$，继续处理下一个能量块。
• 否则立即退出循环，此时的 $d$ 就是答案。

如果整个数组都能吸收，循环自然结束，最后的 $d$ 同样是答案。

例如，初始能量为 $5$，能量块依次为 $3,2,9,20,22,14$。吸收前三块后，能量依次变为 $8,10,19$；遇到 $20$ 时不能吸收，所以答案为 $19$，后面的能量块不再处理。

复杂度与数值范围

每组读入和模拟各进行至多 $n$ 次操作，时间复杂度为 $O(n)$。标程保存了整个数组，按有效数据规模计，空间复杂度为 $O(n)$。

每个 $a_i$ 不超过 $10^9$，可以用 int 保存；但累加后的能量可能超过 32 位有符号整数范围，因此当前能量 $d$ 使用 long long。

满分标程（absorb.cpp）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N];
int main() {
	int T;
	cin >> T;
	while (T --) {
		LL d;
		int n;
		cin >> n >> d;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		for (int i = 1; i <= n; i ++)
			if (a[i] < d) {
				d += a[i];
			} else {
				break;
			}
		cout << d << "\n";
	}
	return 0;
}

常见错误

把严格小于写成小于等于。 当 $d=5,a_1=5$ 时不能吸收，答案仍为 $5$。

始终与初始能量比较。 当 $d=5$、能量块为 $3,6$ 时，可以先变成 $8$，再吸收 $6$，答案为 $14$。判断使用的必须是不断变化的当前能量。

跳过失败位置或重新排序。 当 $d=5$、能量块为 $8,1$ 时，必须在第一块处停止，答案为 $5$，不能先吸收后面的 $1$。

把 break 放进尚未完成读入的循环。 本题有多组数据，应像标程一样先完整读入本组数组，再进行模拟。

T2 铜牌名次（bronze）

简要题意

给定 $n$ 名选手的成绩，找出第三大的不同成绩，并输出这一成绩及其出现次数。同分选手属于同一档，保证至少出现三种不同的成绩。

数据范围：$3\le n\le250000$，$0\le a_i\le75$。每个文件至多 $10$ 组数据，所有组的 $n$ 之和不超过 $5\times10^5$。

一句话题解

解法一：复制数组，排序去重后找到第三大的不同成绩，再回到原数组统计人数。

解法二：利用成绩值域很小的特点进行桶计数，从高到低找到第三个非空桶。

完整题解

先分清“第三个人”和“第三档成绩”

例如，成绩为 $10,10,8,6,6$。不同成绩从高到低是 $10,8,6$，因此铜牌成绩为 $6$，铜牌人数为 $2$。

若直接把全部成绩降序排序并取第三项，得到的却是 $8$，这是错误的。重复出现的成绩不应占用新的名次。

本题有两个需要分别完成的任务：先找出第三大的不同成绩，再统计这个成绩在原数据中出现了多少次。

解法一：排序去重，再统计人数

1. 保留原数组，复制一份用于去重

标程用 a 保存原始成绩，并在读入时将每个成绩复制到 b：

cin >> a[i], b[i] = a[i];

随后对 b[1..n] 进行从小到大的排序。此时相同成绩一定相邻，才能继续使用 unique 去重。

2. 理解 unique 返回的是什么

unique(b + 1, b + n + 1) 将相邻的重复值合并，把不同的成绩依次放在数组前面，返回去重后有效区间的尾后位置。

由于有效数据从 b + 1 开始，不同成绩的个数为

int m = unique(b + 1, b + n + 1) - b - 1;

去重之后，只有 b[1..m] 是接下来需要使用的有效部分，并且满足

$$b_1<b_2<\cdots<b_m.$$

所以最大的不同成绩是 $b_m$，第二大是 $b_{m-1}$，第三大就是 $b_{m-2}$。题目保证至少有三种不同成绩，因此 $m\ge3$，这个下标一定合法。

例如，$10,10,8,6,6$ 排序后为 $6,6,8,10,10$，去重后的有效部分为 $6,8,10$。此时 $m=3$，铜牌成绩就是 $b_1=6$。

3. 回到原数组统计次数

去重只保留了不同成绩，不能再用去重后的有效区间计算原来的出现次数。因此再次扫描完整的 a[1..n]，每遇到一个等于 b[m - 2] 的元素，就将人数加一。

这也是标程需要保留原数组 a 的原因：b 用来确定名次，a 用来保留所有选手的信息。

正确性证明

排序后，相等的成绩连续出现；去重后的 b[1..m] 恰好包含每种出现过的成绩一次，并且严格递增。因此 b[m - 2] 恰好是第三大的不同成绩。

原数组 a 没有被修改，每名选手对应其中一个元素。程序检查全部 $n$ 个元素，并且仅在成绩等于铜牌成绩时计数，所以统计结果恰好是铜牌选手人数。两个输出均正确。

复杂度

复制、去重和计数均为 $O(n)$，排序为 $O(n\log n)$，所以总时间复杂度为 $O(n\log n)$。保存两份成绩数组，空间复杂度为 $O(n)$。

满分标程（bronze.cpp）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int a[N], b[N];
int main() {
	int T;
	cin >> T;
	while (T --) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> a[i], b[i] = a[i];
		sort(b + 1, b + n + 1);
		int m = unique(b + 1, b + n + 1) - b - 1;
		int ans = 0;
		for (int i = 1; i <= n; i ++)
			if (a[i] == b[m - 2]) ans ++;
		cout << b[m - 2] << ' ' << ans << "\n";
	}
	return 0;
}

解法二：桶排序思想——按成绩计数

1. 用桶保存每种成绩的人数

因为成绩只能取 $0\sim75$，不需要对所有选手逐一排序，可以直接设置

$$\mathrm{cnt}[x]=\text{成绩为 }x\text{ 的选手人数}.$$

读入一个成绩 $x$，就执行 cnt[x] ++。全部读入后，每个桶的下标表示成绩，桶内的数表示该成绩的人数。

这里使用的是桶排序的计数思想，不必把排序后的完整成绩序列重新输出或存回数组。

2. 从高到低寻找第三个非空桶

从 $75$ 枚举到 $0$，只在 cnt[i] > 0 时增加名次计数。遇到的第一个非空桶是金牌档，第二个是银牌档，第三个是铜牌档。

因此找到第三个非空桶时，直接输出其下标 $i$ 和桶内人数 cnt[i] 即可。

注意：名次计数每次增加的是 $1$，不是 cnt[i]。同一成绩不论有多少人，都只占用一档。

正确性证明

读入结束后，cnt[x] 等于成绩 $x$ 的出现次数，所以非空桶与所有出现过的不同成绩一一对应。

按下标从大到小扫描时，非空桶的出现顺序恰好是不同成绩从高到低的顺序。因此第三个非空桶对应铜牌成绩，该桶的计数就是铜牌人数。题目保证至少有三种不同成绩，所以一定能够找到答案。

复杂度

设成绩值域大小为 $V=76$。读入并计数需要 $O(n)$，初始化与扫描桶需要 $O(V)$，总时间复杂度为 $O(n+V)$，空间复杂度为 $O(V)$。

在本题的固定值域下，也可以分别写成 $O(n)$ 和 $O(1)$。人数不超过 $250000$，所有计数使用 int 即可。

桶计数参考实现

#include<bits/stdc++.h>
using namespace std;
const int N = 80;
int cnt[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		int n;
		cin >> n;
		memset(cnt, 0, sizeof cnt);
		for (int i = 1; i <= n; i ++) {
			int a;
			cin >> a;
			cnt[a] ++;
		}
		int k = 0;
		for (int i = 75; i >= 0; i --) {
			if (!cnt[i]) continue;
			k ++;
			if (k == 3) {
				cout << i << ' ' << cnt[i] << "\n";
				break;
			}
		}
	}
	return 0;
}

两种解法的区别

排序去重法不依赖成绩值域很小这一条件：即使成绩范围扩大，只要可以排序，思路仍然成立。桶计数法利用了本题只有 $76$ 种可能成绩的特点，直接获得每种成绩的出现次数，不需要另存原数组。

两种做法都能解决本题的完整数据范围。

常见错误

直接取排序后的第三项。 应当先排除重复成绩对名次的影响，不能把“第三名选手”当成“第三档成绩”。

没有排序就调用 unique。 unique 只合并相邻的相同值，不能直接对任意顺序的数组完成全局去重。

去重后仍然用原来的 $n$ 计算下标。 不同成绩个数已经变成 $m$，第三大应取 b[m - 2]，不是 b[n - 2]。

去重后只在有效前缀中统计人数。 每种成绩只剩一个，原有的重复次数已经无法从这个前缀恢复，应扫描保留的原数组。

桶扫描遗漏 $0$，或多组数据没有清空桶。 $0$ 分也是合法成绩；不同活动的计数必须互不影响。

T3 分组核验（group）

简要题意

先给出 $X$ 条“必须同组”的要求和 $Y$ 条“不能同组”的要求，再给出 $G$ 个三人小组。分组已经确定，不需要调整，只需统计被违反的要求条数。

每名同学有唯一的姓名，恰好属于一个小组；同一无序姓名对最多出现一条要求，要求中出现的同学都在给定的分组中。

数据范围：$0\le X,Y\le10^5$，$1\le G\le10^5$，姓名由 $1\sim10$ 个大写字母组成。每个文件至多 $10$ 组数据，所有组的 $X$ 之和、$Y$ 之和、$G$ 之和分别不超过 $2\times10^5$。

一句话题解

用 map<string, int> 记录每名同学的小组编号，再分别检查两类要求中的两个人是否同组。

完整题解

先确定真正需要查询的信息

对于一条要求，只需要知道它涉及的两名同学是否在同一个小组，不需要知道小组内其他人的姓名，也不需要推导新的关系。

设 p[s] 表示姓名为 s 的同学所在的小组编号，那么判断两名同学是否同组，就转化成了比较两个整数是否相等。

这里建立的是“姓名到组号”的映射，不是按照要求重新分组。题目让我们核验已有方案，不允许合并或调整小组。

按输入顺序组织数据

要求先出现，分组后出现。在读要求时，还不知道每个人的组号，所以要先把要求保存下来。

标程用四个字符串数组保存两类要求：xa[i]、xb[i] 是第 $i$ 条必须同组要求中的两个人；ya[i]、yb[i] 是第 $i$ 条不能同组要求中的两个人。

读到第 $i$ 个小组的三名同学 a、b、c 时，执行

p[a] = p[b] = p[c] = i;

这样，全部小组读入后，每个人所在的小组编号就都已经记录好了。

两类要求分别判断

对于“必须同组”的要求，只有两人的组号不相等时才违反要求：

if (p[xa[i]] != p[xb[i]]) ans ++;

对于“不能同组”的要求，只有两人的组号相等时才违反要求：

if (p[ya[i]] == p[yb[i]]) ans ++;

每条输入要求独立检查一次，满足就不计数，不满足就给答案加一。

例如，小组为 A B C 和 D E F，有三条必须同组的要求 A D、B E、C F。这三条要求全部不满足，答案是 $3$，不能因为它们涉及的是同一对小组就合并计算。

正确性证明

每名同学恰好属于一个小组。读入第 $i$ 个小组时，程序将其中三个人的组号都设为 $i$，因此映射 p 正确记录了每个人所在的小组。

对于任意一条必须同组的要求，两人的组号不相等当且仅当要求被违反；程序使用的正是这个判断条件。对于任意一条不能同组的要求，两人的组号相等当且仅当要求被违反；程序也恰好在这种情况下计数。

程序对每条输入要求检查一次，不遗漏、不重复，也不计算未在输入中出现的要求。因此最终的 ans 就是被违反的要求总数。

复杂度与实现细节

设姓名最大长度为 $L$，其中 $L\le10$。映射中至多有 $3G$ 个姓名，map 的一次访问需要 $O(\log(3G+1))$ 次字符串比较，每次比较的最坏时间为 $O(L)$。

因此，按有效输入规模计，时间复杂度为

$$O\bigl((G+X+Y)L\log(3G+1)\bigr),$$

空间复杂度为 $O((G+X+Y)L)$。将短字符串长度看成常数时，也可以简写为 $O((G+X+Y)\log(3G+1))$ 时间、$O(G+X+Y)$ 空间。

每组开始时调用 p.clear() 清除上一组的映射，并重新将答案设为 $0$。当 $X=0$ 或 $Y=0$ 时，对应循环不执行即可，不需要特判。

满分标程（group.cpp）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
string xa[N], xb[N], ya[N], yb[N];
map<string, int> p;
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		p.clear();
		int x, y, g;
		cin >> x;
		for (int i = 1; i <= x; i ++) cin >> xa[i] >> xb[i];
		cin >> y;
		for (int i = 1; i <= y; i ++) cin >> ya[i] >> yb[i];
		cin >> g;
		for (int i = 1; i <= g; i ++) {
			string a, b, c;
			cin >> a >> b >> c;
			p[a] = p[b] = p[c] = i;
		}
		int ans = 0;
		for (int i = 1; i <= x; i ++)
			if (p[xa[i]] != p[xb[i]]) ans ++;
		for (int i = 1; i <= y; i ++)
			if (p[ya[i]] == p[yb[i]]) ans ++;
		cout << ans << "\n";
	}
	return 0;
}

常见错误

按违规小组数或违规人数计数。 本题的统计对象是“要求条数”，同一人、同一组或同一对小组涉及的多条要求仍应分别计算。

把要求当成分组指令。 输入中的小组已经确定，不能按照“必须同组”的要求再去合并，否则改变了需要核验的对象。

两类要求使用了同一个判断条件。 必须同组时，组号不同才违规；不能同组时，组号相同才违规。

忽略输入顺序或多组数据的初始化。 要先保存要求，等读完分组后再核验。每组清空映射，可以避免无关姓名不断累积。姓名也必须完整保存，不能只比较开头的几个字符。

T4 候晴行程（travel）

简要题意

每组给出 $N$ 段必须依次经过的道路和 $M$ 天的天气，$1\le N\le M\le1000$。第 $i$ 段长度为 $D_i$，第 $j$ 天天气系数为 $C_j$，两者均在 $1\sim1000$。每天可以等待，或花一天经过下一段道路，产生 $D_iC_j$ 的费用，求在 $M$ 天内完成行程的最小总费用。每文件至多 $10$ 组，所有组的 $NM$ 之和不超过 $2\times10^6$。

一句话题解

令 $f[i][j]$ 为第 $j$ 天结束时位于城镇 $i$ 的最低费用，由第 $j$ 天等待或行走两种选择转移。

完整题解

20 分：没有等待的余地

测试点 $7\sim10$ 保证 $N=M$。必须在恰好 $N$ 天走完 $N$ 段道路，而一天至多走一段，因此每天都必须行走。唯一方案的费用为

$$\sum_{i=1}^{N}D_iC_i.$$

这个性质给出直接求和的 $20$ 分，不需要动态规划。

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		int n, m, ans = 0;
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		for (int i = 1; i <= m; i ++) {
			int c;
			cin >> c;
			if (i <= n) ans += a[i] * c;
		}
		cout << ans << "\n";
	}
	return 0;
}

30 分：枚举行走的日期

测试点 $1\sim6$ 保证 $M\le18$。从 $M$ 天中选出 $N$ 个行走日期，将它们从小到大依次对应第 $1\sim N$ 段道路，就得到一个合法方案。

可以 DFS 枚举第 $u$ 段道路在哪天行走。如果上一段走完后可用的第一天为 day，这次选择的日期 $j$ 必须满足

$$\mathrm{day}\le j\le M-(N-u).$$

右侧限制给后面 $N-u$ 段道路留出足够的天数。枚举完后更新最低费用。

这相当于穷举全部 $\binom{M}{N}$ 个日期组合，保守时间上界为 $O(N2^M)$，递归空间为 $O(N)$。当 $M\le18$ 时可以完成。

合并两档，自然取得 50 分

同一个 DFS 在 $N=M$ 时，每层只有唯一合法日期，因此只遍历一条深度为 $N$ 的路径，不会指数爆炸。下面的枚举程序既能完成前 $30$ 分，也能自然完成 $N=M$ 的 $20$ 分，合计 $50$ 分。

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, a[N], b[N], ans;
void dfs(int u, int day, int cost) {
	if (u > n) {
		ans = min(ans, cost);
		return;
	}
	for (int i = day; i <= m - (n - u); i ++)
		dfs(u + 1, i + 1, cost + a[u] * b[i]);
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		for (int i = 1; i <= m; i ++) cin >> b[i];
		ans = 0x3f3f3f3f;
		dfs(1, 1, 0);
		cout << ans << "\n";
	}
	return 0;
}

为什么不能直接挑好天气

道路顺序不能改变，而且不同道路长度不同。同样一天较小的天气系数，安排给哪一段道路，影响可能完全不同。

例如道路长度为 $(100,1)$，天气为 $(2,1,3)$。挑天气系数最小的两天是第 $1,2$ 天，费用为 $201$；实际应在第 $2,3$ 天行走，费用为 $103$。

反过来，若道路长度为 $(1,100)$、天气仍为 $(2,1,3)$，给第一段选择当前能用的最好天气，会选第 $2$ 天，费用变成 $301$；在第 $1,2$ 天行走只需 $102$。

所以必须同时考虑当前进度和剩余日期。

满分动态规划

状态定义

定义 $f[i][j]$ 为第 $j$ 天结束时，恰好走完前 $i$ 段道路、位于城镇 $i$ 的最小总费用。没有可行方案时记为正无穷。

标程中的 d[i] 对应第 $i$ 段道路长度 $D_i$，c[j] 对应第 $j$ 天天气系数 $C_j$。

代码注释中的“在第 $j$ 天抵达 $i$”，应按上述状态理解为“第 $j$ 天结束时已经到达并位于 $i$”，不要求首次抵达恰好发生在第 $j$ 天。因为第 $j$ 天也可能是在城镇 $i$ 等待。

按最后一天的行动分类

考察第 $j$ 天的行动，只有两种可能。

第一种：等待。 第 $j-1$ 天结束时已经位于城镇 $i$，第 $j$ 天不移动，也不产生费用。因此可以由 $f[i][j-1]$ 转移。

第二种：行走。 第 $j-1$ 天结束时位于城镇 $i-1$，第 $j$ 天走第 $i$ 段道路，新增费用 $d_i c_j$。因此可以由 $f[i-1][j-1]+d_i c_j$ 转移。只有 $i>0$ 时才存在这一种选择。

对 $i>0$，转移方程为

$$f[i][j]=\min\bigl(f[i][j-1],\ f[i-1][j-1]+d_i c_j\bigr).$$

对 $i=0$，只能等待，所以

$$f[0][j]=f[0][j-1].$$

初值与标程中的枚举顺序

开始时还没有经过任何一天，运输队位于城镇 $0$，因此

$$f[0][0]=0.$$

其余状态先初始化为正无穷。特别地，$f[i][0]=+\infty$（$i>0$），表示不可能在零天内走完正数段道路。

标程外层枚举 $i=0\sim n$，内层枚举 $j=1\sim m$。每个状态先执行等待转移：

f[i][j] = f[i][j - 1];

当 $i>0$ 时，再尝试行走转移：

if (i) f[i][j] = min(f[i][j], f[i - 1][j - 1] + d[i] * c[j]);

当外层枚举到 $i=0$ 时，等待转移会把 $f[0][0]=0$ 一直传递下去，自然得到所有 $f[0][j]=0$，不需要单独写一段初始化循环。

按这个顺序计算时，同一行的 $f[i][j-1]$ 已经计算，上一行的 $f[i-1][j-1]$ 也已经计算，两个前驱都可以直接使用。

答案为什么是 f[n][m]

最终要求在 $m$ 天以内到达城镇 $n$，答案为 $f[n][m]$。

虽然允许提前到达，但到达后可以一直等待到第 $m$ 天，费用不会变化。等待转移已经包含了这些方案，所以不需要再单独枚举到达终点的日期。

正确性证明

对于任意一个第 $j$ 天结束时位于城镇 $i$ 的合法方案，第 $j$ 天只可能等待或行走。

若等待，删去这一天后得到第 $j-1$ 天结束时位于城镇 $i$ 的合法方案，对应第一项转移。若行走，由于道路必须按顺序经过且一天最多走一段，这一天必然走第 $i$ 段；删去这一天后得到第 $j-1$ 天结束时位于城镇 $i-1$ 的合法方案，对应第二项转移。

反过来，任意一个合法前驱方案追加相应行动，也都会得到满足当前状态要求的方案。因此两种转移覆盖所有可能，且不引入非法方案。

初值准确描述出发时的情况，由计算顺序归纳可知每个状态都取得正确的最小费用。提前完成的方案又能通过等待延伸到第 $m$ 天，所以 $f[n][m]$ 正是题目所求。

复杂度与实现

共有 $O(NM)$ 个状态，每个状态只做常数次转移。按有效状态数计，时间复杂度为 $O(NM)$，空间复杂度为 $O(NM)$。题目保证同一输入文件中所有组的 $NM$ 之和不超过 $2\times10^6$；标程另外会在每组开始时清空整个固定大小的 f 数组。

总费用至多为

$$N\times1000\times1000\le10^9,$$

因此可以用 int 保存。标程的无穷大为 0x3f3f3f3f，大于所有合法答案，并且加上一次道路费用后仍不会超过 int 上限。

满分标程（travel.cpp）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010;
int d[N], c[N];
int f[N][N];    // f[i][j]表示在第j天抵达i的最小代价
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		int n, m;
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) cin >> d[i];
		for (int i = 1; i <= m; i ++) cin >> c[i];
		memset(f, 0x3f, sizeof f);
		f[0][0] = 0;
		for (int i = 0; i <= n; i ++) {
			for (int j = 1; j <= m; j ++) {
				f[i][j] = f[i][j - 1];
				if (i) f[i][j] = min(f[i][j], f[i - 1][j - 1] + d[i] * c[j]);
			}
		}
		cout << f[n][m] << "\n";
	}
	return 0;
}

常见错误与自然修补

• 天气排序后直接匹配。 排序破坏了日期顺序，无法保证道路仍按顺序经过。即使先选出最好的 $N$ 天、再把日期排回原顺序，上面的反例仍然存在。
• 每段都挑后续可用日期中最好的天气。 这可能把更适合长道路的日期提前用掉。枚举第一段日期、后续仍贪心，也没有解决后面各段之间的冲突。
• 转移写成 $f[i-1][j]$。 会允许同一天连续走多段道路，违反一天至多走一段的规定。
• 不可达状态初始化为零。 会把没有足够天数的状态也当成合法低费用方案。
• 只检查一个日期窗口。 允许在任意城镇等待，行走日期不必连续。

对于“枚举第一段日期”的加强贪心，取道路长度 $(20,4,18)$，天气系数 $(4,9,8,15)$。最优方案在前三天行走，费用为 $20\times4+4\times9+18\times8=260$。该贪心即使选对第一天，也会给第二段挑第 $3$ 天，迫使第三段走第 $4$ 天，得到 $382$；枚举另一个合法首日也不能修复这个错误。

赛时推进

先观察 $N=M$，再用组合枚举完成小范围，可以较稳妥地得到 $50$ 分。搜索时存在大量“走到同一段道路、来到同一天”的重复状态，将最优费用按这两个量保存下来，就得到满分动态规划。

T5 巡检路线（patrol）

简要题意

每组给出一个 $4\le N,M\le100$ 的车间网格，外圈全是墙，内部有唯一的起点、至少一块空地，以及墙、摄像头和四向传送带。主动移动到相邻格子计 $1$ 步，传送带强制沿箭头移动且不计步数。摄像头的四向视线只被墙阻挡；空地和起点受到监控，传送带本身不受监控且不挡视线。按行优先顺序输出到每块空地的最少主动步数，不可达输出 $-1$。输入至多 $10$ 组，同文件总格数不超过 $10^5$，各组独立。

一句话题解

先标记摄像头视线，再把主动移动建成 $1$ 权边、传送建成 $0$ 权边；使用数组模拟双端队列，运行 0-1 BFS。

完整题解

30 分：没有摄像头和传送带

此时只有墙、起点和空地。每次移动的代价都为 $1$，从起点进行普通 BFS，即可得到所有空地的最短距离。

一个格子第一次被 BFS 访问时，得到的就是最少步数；因为队列按距离非递减顺序扩展。没有被访问的空地输出 $-1$。时间、空间复杂度均为 $O(NM)$。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 105;
int n, m, d[N][N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
char a[N][N];
void solve() {
	cin >> n >> m;
	memset(d, -1, sizeof d);
	queue<PII> q;
	for (int i = 1; i <= n; i ++) {
		cin >> (a[i] + 1);
		for (int j = 1; j <= m; j ++)
			if (a[i][j] == 'S') d[i][j] = 0, q.push({i, j});
	}
	while (!q.empty()) {
		int x = q.front().first, y = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k ++) {
			int nx = x + dx[k], ny = y + dy[k];
			if (a[nx][ny] == 'W' || a[nx][ny] == 'C' || d[nx][ny] != -1) continue;
			d[nx][ny] = d[x][y] + 1;
			q.push({nx, ny});
		}
	}
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if (a[i][j] == '.') cout << d[i][j] << "\n";
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

60 分：允许摄像头，但没有传送带

先从每个摄像头沿四个方向扫描，遇到墙停止，标记射线上的空地和起点。被标记的格子不能进入，摄像头所在格子也不能进入。

之后仍然是普通 BFS。若起点被标记，则所有空地不可达。每台摄像头至多扫描 $O(N+M)$ 个格子，预处理时间为 $O(NM(N+M))$，BFS 为 $O(NM)$；空间为 $O(NM)$。在本题每组最多 $100\times100$ 的范围下足够。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 105;
int n, m, sx, sy, d[N][N];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
char a[N][N];
bool ban[N][N];
void solve() {
	cin >> n >> m;
	memset(d, -1, sizeof d);
	memset(ban, 0, sizeof ban);
	for (int i = 1; i <= n; i ++) {
		cin >> (a[i] + 1);
		for (int j = 1; j <= m; j ++)
			if (a[i][j] == 'S') sx = i, sy = j;
	}
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if (a[i][j] == 'C')
				for (int k = 0; k < 4; k ++) {
					int x = i + dx[k], y = j + dy[k];
					while (a[x][y] != 'W') {
						ban[x][y] = true;
						x += dx[k], y += dy[k];
					}
				}
	queue<PII> q;
	if (!ban[sx][sy]) d[sx][sy] = 0, q.push({sx, sy});
	while (!q.empty()) {
		int x = q.front().first, y = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k ++) {
			int nx = x + dx[k], ny = y + dy[k];
			if (a[nx][ny] != '.' && a[nx][ny] != 'S') continue;
			if (ban[nx][ny] || d[nx][ny] != -1) continue;
			d[nx][ny] = d[x][y] + 1;
			q.push({nx, ny});
		}
	}
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if (a[i][j] == '.') cout << d[i][j] << "\n";
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

满分：预处理监控，再运行 0-1 BFS

1. mon 记录视线经过的位置，不等于所有格子都禁止进入

摄像头的位置不会改变，监控情况与机器人选择的路线无关，因此可以一次性预处理。

从每个摄像头沿上、下、左、右四个方向扫描，遇到墙才停止。传送带和其他摄像头都不阻挡视线，不能在经过它们时停止扫描。

标程将射线经过的非墙格子标记为 mon[x][y] = true，其中也可能包含传送带。这里的标记表示“视线经过”，不是“机器人一定不能进入”。

检查目标格子时，要结合格子类型判断：墙和摄像头始终不能进入；空地 . 只有未被监控时才能进入；传送带不受监控影响，可以进入。

代码在排除墙和摄像头后，使用

s[a][b] == '.' && !mon[a][b] || s[a][b] != '.'

判断是否允许进入。因为 && 的优先级高于 ||，它等价于

(s[a][b] == '.' && !mon[a][b]) || (s[a][b] != '.')

即“未被监控的空地，或者不是空地的其他可进入格子”。传送带即使被 mon 标记，也不会因此被拦住。

起点 S 在开始搜索之前单独检查：只有 !mon[sx][sy] 时才将起点入队。若起点被监控，队列为空，所有空地保持不可达；若起点未被监控，由于监控状态不会改变，之后回到 S 也始终安全。因此后续移动时不必再单独拦截被监控的 S。

2. 把移动规则转化成有向边

将每个可进入的格子看成一个顶点。

如果当前格子是空地或起点，可以主动走到四个方向中合法的相邻格子，每次消耗 $1$ 步，对应一条权值为 $1$ 的有向边。

如果当前格子是传送带，只能沿箭头指向移动到相邻格子，不消耗主动步数，对应一条权值为 $0$ 的有向边。如果箭头指向的格子不能进入，就没有合法出边，不能从其他方向离开。

边权由出发格子上的动作决定。 从空地主动走上传送带仍然消耗 $1$ 步；从传送带被运送到下一格才消耗 $0$ 步。不能只根据终点是否为传送带判断边权。

标程中 dir = "UDLR" 与 dx、dy 的四个方向一一对应。先检查当前格子是不是某个方向的传送带；若是，只尝试该方向，并通过 flag 跳过后面的四向主动移动。

不需要实际建立邻接表，取出当前格子时按上述规则枚举后继即可。

3. 为什么普通 BFS 的“第一次访问就确定答案”不成立

普通 BFS 适用于所有边权都为 $1$ 的情况。本题同时存在 $0$ 权边和 $1$ 权边，一条经过更多格子的传送路线，反而可能需要更少的主动步数。

例如下面的地图：

WWWWW
W...W
WS.UW
WWWWW

从起点到第 $2$ 行第 $4$ 列，沿上方空地走需要 $3$ 步；向右走两步进入 U，再免费向上传送，只需要 $2$ 步。

按照标程的方向枚举顺序，目标空地可能先以距离 $3$ 入队，之后才通过传送带把距离更新为 $2$。因此，一个格子第一次入队时，距离不一定已经最优。

4. 用松弛代替单纯的访问判断

令 d[x][y] 表示当前找到的最少主动步数，初始为 $-1$，表示尚未到达。

若当前准备从 $(x,y)$ 经过边权为 $w$ 的边到达 $(a,b)$，只有当

$$d[a][b]=-1\quad\text{或}\quad d[x][y]+w<d[a][b]$$

时，才更新 d[a][b] 并将目标格子入队。这一步叫作松弛：找到更短的路线后，用新答案替换旧答案。

标程分别写出了两种情况。传送时 $w=0$，判断 d[x][y] < d[a][b]；主动移动时 $w=1$，判断 d[x][y] + 1 < d[a][b]。

所以，一个格子可以在距离被改善后再次入队。不能只用 d[a][b] == -1 判断能否进入，也不能在第一次入队后就禁止更新。

只有严格变短时才再次入队，同样重要。遇到传送带形成的零权环时，沿环走一圈只会得到相等的距离，不会无限重复入队。

5. 数组如何模拟双端队列

0-1 BFS 使用双端队列：成功经过 $0$ 权边时放到队首，成功经过 $1$ 权边时放到队尾。

标程使用数组 q 和两个指针 hh、tt 模拟，当前队列是 q[hh..tt]。初始时让 hh 位于数组中间，tt = hh - 1，表示空队列。

三种操作分别是：

PII u = q[hh ++];  // 取出队首
q[ -- hh] = {a, b}; // 加入队首，对应 0 权边
q[ ++ tt] = {a, b}; // 加入队尾，对应 1 权边

零代价转移应当优先处理，因此放到队首；增加一步的转移放到队尾。这是双端队列在本题中的关键作用，不是把普通队列换一种写法而已。

本实现没有“已经确定”的 st 数组，也没有在出队时跳过重复队列项，而是始终使用当前的 d 尝试严格松弛。重复取出一个格子不会把较优距离改差；真正使算法正确的是 0/1 边权对应的队列顺序和允许距离改善的更新条件。

正确性证明

首先，摄像头预处理从每个摄像头沿四个方向扫描，并且只在遇到墙时停止，因此准确记录了视线能够经过的位置。搜索时禁止进入墙、摄像头和被监控的空地，同时允许经过传送带，并在起点被监控时不启动搜索，恰好满足题目的安全规则。

其次，图中的每条边都对应一种合法移动：空地和起点的出边是代价为 $1$ 的主动移动，传送带的唯一可能出边是代价为 $0$ 的强制传送。因此，到达任一空地的合法路线与图中到达该空地的路径相对应，路径权值之和就是主动移动次数。传送环没有额外出口，也不会被当成可以自由行走的区域。

最后，0-1 BFS 将零代价转移放到队首，将增加一步的转移放到队尾，使尚未过期的队列项按距离从小到大得到处理。对于当前最小距离的格子，不可能通过尚未处理的更大距离再得到一条更短的路径，因为所有边权均非负。结合严格松弛，所有可达格子最终都得到最短距离。

同一格子留下的重复队列项只会按当前距离重新尝试松弛，不会覆盖更小的距离，也不会漏掉应当进行的更新。因此标程求得的空地距离正确；没有被到达的空地保持 $-1$。

复杂度与实现细节

最多有 $NM$ 个顶点，每个顶点至多有四条出边，因此 0-1 BFS 的时间复杂度为 $O(NM)$，空间复杂度为 $O(NM)$。这一复杂度不是建立在“每个格子只能入队一次”的假设上。

从每个摄像头沿射线扫描，一台摄像头至多扫描 $O(N+M)$ 个位置。摄像头数量至多为 $NM$，所以监控预处理的时间复杂度上界为 $O(NM(N+M))$。本题 $N,M\le100$，可以使用这一实现。

因此总体时间复杂度为 $O(NM(N+M))$，空间复杂度为 $O(NM)$，按每组的有效网格规模计算。每组重新清空 mon，搜索时重新初始化 d 和队列指针；不需要清空整个 q，因为只有当前的队列区间会被读取。

外圈全部是墙，搜索不会进入墙，摄像头射线也会在墙处停止。最终按行优先顺序只输出 . 格子的 d，不输出起点、传送带等其他格子，也不在两组之间额外输出空行。

满分标程（patrol.cpp）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110;
char s[N][N];
int d[N][N], n, m;
bool mon[N][N];
struct PII {
	int x, y;
}q[N * N * 2];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
string dir = "UDLR";
void bfs(int x, int y) {
	memset(d, -1, sizeof d);
	d[x][y] = 0;
	int hh = N * N, tt = hh - 1;
	if (!mon[x][y]) q[ ++ tt] = {x, y};
	while (hh <= tt) {
		PII u = q[hh ++];
		int x = u.x, y = u.y;
		bool flag = false;  // 是否是传送带
		for (int i = 0; i < 4; i ++)
			if (s[x][y] == dir[i]) {
				int a = x + dx[i], b = y + dy[i];
				if (s[a][b] != 'W' && s[a][b] != 'C' && (d[a][b] == -1 || d[x][y] < d[a][b])) {
					if (s[a][b] == '.' && !mon[a][b] || s[a][b] != '.') {
						d[a][b] = d[x][y];
						q[ -- hh] = {a, b};
					}
				}
				flag = true;
			}
		if (flag) continue;
		for (int i = 0; i < 4; i ++) {
			int a = x + dx[i], b = y + dy[i];
			if (s[a][b] != 'W' && s[a][b] != 'C' && (d[a][b] == -1 || d[x][y] + 1 < d[a][b])) {
				if (s[a][b] == '.' && !mon[a][b] || s[a][b] != '.') { // 未被监视的空地或传送带
					d[a][b] = d[x][y] + 1;
					q[ ++ tt] = {a, b};
				}
			}
		}
	}
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if (s[i][j] == '.') cout << d[i][j] << "\n";
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= m; j ++)
				cin >> s[i][j];
		memset(mon, 0, sizeof mon);
		int sx, sy;
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= m; j ++) {
				if (s[i][j] == 'S') sx = i, sy = j;
				else if (s[i][j] == 'C') {
					for (int k = 0; k < 4; k ++) {
						int x = i, y = j;
						while (s[x][y] != 'W') {
							x += dx[k], y += dy[k];
							if (s[x][y] != 'W') mon[x][y] = true;
						}
					}
				}
			}
		bfs(sx, sy);
	}
	return 0;
}

常见错误与赛时检查

• 忽略起点被监控。 例如 WWWWW / WSC.W / W...W / WWWWW，起点已被发现，所有空地都不可达。
• 认为传送带阻挡视线，或认为带上的机器人也会被拍到。 两者都与题目规则相反；传送带只让机器人避开拍摄，并不遮挡后面的空地。
• 以为传送带可以随时离开。 例如 WWWWW / WSR.W / W...W / WWWWW，机器人进入 R 后只能继续向右，不能直接向下。
• 把首次入队当成最优。 将队列换成双端队列后，如果仍然只允许每个格子入队一次，也不一定正确；必须允许成功松弛。
• 把传送环当作可自由行走的区域。 圈内机器人不能选择方向，不能从旁边跳出去。

赛时可以先完成普通 BFS 获得前 $30$ 分，再加入监控获得前 $60$ 分。最后只需改变传送带出边与队列松弛方式，不需要学习新的高级图结构。

T6 环线分区（district）

简要题意

每组给出按环排列的 $N$ 段道路及正整数长度 $A_i$，在道路之间选三个不同分界，将全部道路划成三个非空连续区域，求三个区域长度最小值的最大可能值。每文件至多 $10$ 组，$3\le N\le10^5$、$1\le A_i\le10^9$，所有组的 $N$ 之和不超过 $2\times10^5$，每组输出一个整数。

一句话题解

复制环形数组，二分最短区域长度；用双指针求每个起点最早达标的右端点，再连续取三段，检查是否能放在同一圈之内。

完整题解

先把三个分界理解清楚

可以把分界放在任意一段道路之前，而不必选第 $1$ 段之前。三个不同分界恰好产生三个非空区域。固定三个分界后，分数就是三个区间和的最小值。

总长度最多为 $10^{14}$，答案、前缀和和二分边界均应使用 long long。复制数组后前缀和最多为 $2\times10^{14}$，仍可安全表示。

20 分：前缀和加速求值

建立前缀和 $s_i=\sum_{j=1}^{i}A_j$。上述三个区域的长度依次为

$$s_{j-1}-s_{i-1},\qquad s_{k-1}-s_{j-1},\qquad s_N-s_{k-1}+s_{i-1}.$$

每种方案只需常数时间求值，复杂度降为 $O(N^3)$，空间 $O(N)$，可累计获得测试点 $1\sim4$ 的 $20$ 分。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
LL a[N], sum[N];
int main() {
	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], sum[i] = sum[i - 1] + a[i];
		LL ans = 0;
		for (int i = 1; i <= n; i ++)
			for (int j = i + 1; j <= n; j ++)
				for (int k = j + 1; k <= n; k ++) {
					LL x = sum[j - 1] - sum[i - 1];
					LL y = sum[k - 1] - sum[j - 1];
					LL z = sum[n] - x - y;
					ans = max(ans, min(x, min(y, z)));
				}
		cout << ans << "\n";
	}
	return 0;
}

50 分：固定一个分界，优化另外两个分界

复制数组，令 $A_{N+i}=A_i$，建立长度 $2N$ 的前缀和。枚举一个区域的起点 $l\in[1,N]$，则这一圈为 $[l,l+N-1]$。再枚举第一个区域的终点 $j\in[l,l+N-3]$。

第一个区域长度已经确定，余下两段的总长度也固定。要使三者最小值最大，只需让剩余两段中较短者尽可能长。枚举第二段的终点 $k$ 时，第二段长度随 $k$ 递增，第三段长度递减，因此最优位置只可能是两者第一次满足“第二段不短于第三段”的位置及其前一个位置。

对于固定 $l$，$j$ 递增时，平衡位置对应的条件为

$$2s_k\ge s_j+s_{l+N-1}.$$

右侧不减，故 $k$ 不需要向左退。为所有 $j$ 找平衡位置总计只需 $O(N)$。枚举 $l$ 后总复杂度为 $O(N^2)$，空间 $O(N)$。测试点 $5\sim10$ 中，每组 $N\le5000$，同一输入文件内 $\sum N\le20000$，因此总工作量按 $\sum N^2$ 计算，可累计获得 $50$ 分。

这里枚举了每一种第一段，而剩余两段检查了其最优分界，所以没有遗漏最优解。它不是把第一段也盲目设成总长度的三分之一。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n;
LL a[N], sum[N];
int main() {
	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[i + n] = a[i];
		for (int i = 1; i <= 2 * n; i ++) sum[i] = sum[i - 1] + a[i];
		LL ans = 0;
		for (int l = 1; l <= n; l ++) {
			int k = l + 1;
			for (int j = l; j <= l + n - 3; j ++) {
				k = max(k, j + 1);
				while (k < l + n - 2 && sum[k] - sum[j] < sum[l + n - 1] - sum[k]) k ++;
				LL x = sum[j] - sum[l - 1];
				ans = max(ans, min(x, min(sum[k] - sum[j], sum[l + n - 1] - sum[k])));
				if (k > j + 1) ans = max(ans, min(x, min(sum[k - 1] - sum[j], sum[l + n - 1] - sum[k - 1])));
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

满分：二分答案、贪心截段与双指针

1. 把“最小值最大”转化为判定

考虑能否将环线分成三个非空连续区域，使每个区域的总长度都至少为 $x$。

如果 $x$ 可行，那么更小的正整数一定也可行；如果 $x$ 不可行，那么更大的整数也一定不可行。因此可行性具有单调性，可以二分答案。

三个区域的长度和等于整条环线总长度 $S$，所以答案不会超过 $\lfloor S/3\rfloor$。标程没有使用这个更紧的上界，而是直接在 $[1,10^{14}]$ 上二分，也能包含所有可能答案。

下界 $1$ 一定可行，因为 $n\ge3$，并且每段道路长度都是正整数，任意三个非空区域的长度都至少为 $1$。

2. 复制一遍数组，将环形区间转化为普通区间

令

$$a_{n+i}=a_i\qquad(1\le i\le n),$$

并建立长度 $2n$ 的前缀和

$$\mathrm{sum}[i]=\sum_{j=1}^{i}a_j.$$

任意从第 $i$ 段道路开始的一整圈，都对应复制数组上的区间

$$[i,\ i+n-1],\qquad1\le i\le n.$$

只要枚举这 $n$ 个起点，就能覆盖所有环形划分，不必强行把原来的第 $1$ 段道路之前作为分界。

3. R[i] 保存“最早达标的右端点”

固定当前二分值 mid。定义 R[i] 为：从第 $i$ 段道路开始，连续取一段，使总长度至少为 mid 时，能够选择的最小右端点。

也就是寻找最小的 $j\ge i$，满足

$$\mathrm{sum}[j]-\mathrm{sum}[i-1]\ge\mathrm{mid}.$$

如果存在，则 R[i] = j；如果一直取到复制数组末尾也无法达到要求，就令 R[i] = 2 * n + 1，表示不存在。

注意，R[i] 记录的是当前段最后一个元素的位置，不是下一段的起点。因此下一段应从 R[i] + 1 开始。

4. 连续取三段，检查能否放进一圈

固定一圈的起点 $i$，贪心让每一段在第一次达到 mid 时就结束。三段的右端点依次为

int R1 = R[i];
int R2 = R[R1 + 1];
int R3 = R[R2 + 1];

相应的三个区间为

$$[i,R_1],\qquad[R_1+1,R_2],\qquad[R_2+1,R_3].$$

只要三个右端点都不超过这一圈的末尾 $i+n-1$，这三个达标区间就能放进同一圈之内。

这里检查的是

$$R_1\le i+n-1,\quad R_2\le i+n-1,\quad R_3\le i+n-1,$$

而不是要求 $R_3=i+n-1$。

如果贪心的第三段提前结束，剩余道路怎么办？ 将 $[R_3+1,i+n-1]$ 全部并入第三个区域即可。道路长度为正数，延长第三段只会增加它的长度，不会使其低于 mid。这样仍然恰好分成三个非空区域，并覆盖这一圈的全部道路。

只要存在一个起点通过检查，check(mid) 就返回 true；全部起点都失败时才返回 false。

5. 为什么每段尽早截断不会漏掉可行解

固定起点 $i$，假设存在一个可行划分，其三个区域的右端点为 $p_1,p_2,p_3$，其中 $p_3=i+n-1$。

因为第一段 $[i,p_1]$ 的长度至少为 mid，而 $R_1$ 是第一次达到要求的位置，所以

$$R_1\le p_1.$$

从 $R_1+1$ 开始取到 $p_2$，得到的区间包含原方案的整个第二段 $[p_1+1,p_2]$。多出来的道路长度均为正数，所以这个区间的长度也至少为 mid，于是

$$R_2\le p_2.$$

同理，$[R_2+1,p_3]$ 包含原方案的整个第三段，长度也至少为 mid，所以

$$R_3\le p_3=i+n-1.$$

因此，只要固定起点存在合法划分，贪心连续取三段一定能在这一圈结束前完成，不会漏解。

反过来，如果贪心检查通过，前两段直接保留，将第三段延长到圈尾，就得到三个长度都至少为 mid 的非空区域。这说明判定通过也一定对应一个合法划分。

6. 用双指针线性求出所有 R[i]

直接为每个起点重新扫描右端点，会重复访问大量位置。可以利用道路长度均为正数这一条件优化。

当左端点从 $i$ 移到 $i+1$ 时，原来的区间少了一段正数长度的道路。对于相同的右端点，区间和只会减小，所以最早达标的右端点不可能向左移动。

因此可以让左端点 i 依次从 $1$ 枚举到 $2n$，共用一个只向右移动的指针 j：

while (j <= 2 * n && sum[j] - sum[i - 1] < mid) j ++;
if (j <= 2 * n) R[i] = j;

当区间和不足时移动 j；第一次满足要求的位置就是 R[i]。由于 j 从不回退，整个过程中的右移次数至多为 $2n$，所以求出全部有效 R[i] 只需要 $O(n)$ 时间。

标程没有单独执行 j = max(j, i)。这是因为二分始终满足 mid >= 1：如果上一轮的右端点恰好为当前的 i - 1，此时前缀和之差为 $0$，while 会自动将 j 向右推进。合法的达标区间不会为空。

7. 哨兵位置与二分边界

每次判定开始时，标程将整个 R 数组初始化为 2 * n + 1。这样，所有无法达标的位置都保留同一个哨兵值。

如果 R1 不存在，那么 R1 = 2 * n + 1，接下来会访问 R[2 * n + 2]。这个位置也已初始化为哨兵，因此后续仍然得到“不存在”，最终无法通过圈内检查。

数组容量为 $2\times10^5+10$，而 $n\le10^5$，所以 2 * n + 2 仍然在数组范围内。保留这些额外位置并进行初始化，是这份连续跳转写法成立的实现细节。

二分使用向上取整的中点：

LL mid = l + r + 1 >> 1;

加法的优先级高于右移，因此这句等价于

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

若 check(mid) 成立，就令 l = mid，继续尝试更大的答案；否则令 r = mid - 1。向上取整可避免只剩两个候选值时循环停滞。结束时 l == r，标程输出 r。

正确性证明

对于任意固定的 mid，双指针准确求出每个起点第一次达到目标长度的右端点。上面的贪心论证说明：固定起点存在可行划分，当且仅当连续取出的三个达标区间能放在这一圈之内。

枚举全部 $1\sim n$ 的起点，覆盖所有可能的环形划分，所以 check(mid) 能正确判断是否存在三个区域长度都至少为 mid 的方案。

可行性关于 mid 单调，而二分初始范围包含真实答案。每次更新都保留最大的可行值，最终输出的就是三个区域长度最小值的最大可能值。

复杂度与数值范围

每次判定中，双指针求右端点需要 $O(n)$，枚举所有起点并连续跳三次也需要 $O(n)$。二分上界为 $U=10^{14}$，需要约 $47$ 轮判定。因此算法主体的时间复杂度为 $O(n\log U)$，按有效数据规模计的空间复杂度为 $O(n)$。

这份标程还会在每一轮判定中初始化整个固定容量的 R 数组。若令数组容量 $B=2\times10^5+10$，则精确计入这部分开销，代码每轮为 $O(B+n)$，总时间为 $O((B+n)\log U)$，静态数组空间为 $O(B)$。

每段道路长度不超过 $10^9$，可以用 int 保存；总长度可达 $10^{14}$，复制后的前缀和可达 $2\times10^{14}$，所以 sum、二分边界和 mid 均使用 long long。R 保存的是下标，使用 int 即可。

满分标程（district.cpp）

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N], n, R[N];
LL sum[N];
bool check(LL mid) {
	for (int i = 0; i < N; i ++) R[i] = 2 * n + 1;
	for (int i = 1, j = 1; i <= 2 * n; i ++) {
		while (j <= 2 * n && sum[j] - sum[i - 1] < mid) j ++;
		if (j <= 2 * n) R[i] = j;
	}
	for (int i = 1; i <= n; i ++) {
		int R1 = R[i];
		int R2 = R[R1 + 1];
		int R3 = R[R2 + 1];
		if (R1 <= i + n - 1 && R2 <= i + n - 1 && R3 <= i + n - 1) return true;
	}
	return false;
}
int main() {
	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 + i] = a[i];
		for (int i = 1; i <= 2 * n; i ++) sum[i] = sum[i - 1] + a[i];
		LL l = 1, r = 1e14;
		while (l < r) {
			LL mid = l + r + 1 >> 1;
			if (check(mid)) l = mid;
			else r = mid - 1;
		}
		cout << r << "\n";
	}
	return 0;
}

常见错误与反例

• 强制第 1 段之前是分界。 例如环上长度为 $[1,2,2,1]$ 时，环形最优值为 $2$：把首尾相邻的两个 $1$ 合并，其余两个 $2$ 各成一区。若强制第 $1$ 段之前设置分界，首尾两个 $1$ 无法处于同一区域，只能得到 $1$。
• 把总长度除以 3 当答案。 例如 $[1,1,10]$ 必须每段道路单独成区，答案为 $1$，不是 $4$。道路不可拆分，均分只给出上界。
• 按道路段数平分。 段数接近不代表总长度接近；长度差异很大时，最优三个区域可能含有很不均衡的道路段数。
• 只枚举几个看起来重要的起点。 初始位置、最短道路和最长道路的两侧都不能代表全部可能分界；固定起点法的局部修补仍缺乏覆盖所有方案的证明。
• 把右端点和下一段起点混淆。 R[i] 是段尾，下一段从 R[i] + 1 开始；漏写 +1 会让相邻两段重复使用一段道路。
• 要求第三段恰好结束在圈尾。 正确条件是 R3 <= i + n - 1，剩余道路可以并入第三段。
• 遗漏第三段、允许空区域或忽略哨兵下标。 三段都必须达标且位于同一圈内；连续跳转时要保证哨兵及其后一位仍在已初始化的数组范围内。
• 累计长度使用 int，或多测继承上一组答案。 每组重新建立前缀和及二分边界，输出本组结果。

平方算法还可以加正确的剪枝：当前答案为 $b$，第一段长度为 $x$ 时，若 $x\le b$ 或剩余总长度不超过 $2b$，该选择不可能改进答案；可以二分跳过一部分无望终点。这些剪枝能显著加速一般随机数据，但不保证满分复杂度。例如在环上相隔半圈放两个很大的道路段，其余段很短时，大量第一段都只含一个大值，仍需检查平方级数量的候选。因此，带这些剪枝的枚举仍属于 $50$ 分路线，不能把随机数据运行很快当成复杂度证明。

赛时路线

先用三刀枚举和前缀和拿到 $20$ 分；进一步发现“固定一段后，另外两段应尽量均衡”，即可写出 $50$ 分平方解。若熟悉最大最小值的判定转化，再证明尽早截断不劣并利用正数的双指针单调性，便可实现满分。