一、泊位调度（berth）

1. 题意简述

有一个泊位和 $n$ 艘船。第 $i$ 艘船必须在 $[E_i,R_i]$ 内开始使用泊位，并连续占用 $L_i$ 个单位时间。任意时刻至多一艘船使用泊位，前一艘船结束时，后一艘船可以立即开始。

判断是否存在一种安排，使所有船均能合法使用泊位。

注意：$R_i$ 限制的是开始时刻，不是结束时刻；$L_i$ 可以为 $0$。原代码用结构体中的 T 存储题面中的 $L_i$。

2. 思路分析

枚举船的使用顺序

题目同时要求确定船的先后次序和每艘船的开始时刻。先考虑枚举使用顺序。

由于 $n\le10$，可以用 DFS 枚举所有排列。代码中的 a[x] 表示第 $x$ 个使用泊位的船的编号，st[i] 表示第 $i$ 艘船是否已经出现在当前排列中。

dfs(x) 从尚未选择的船中选一艘，放到排列的第 $x$ 个位置；当 $x>n$ 时，得到一个完整排列，再检查这个顺序是否可行。

固定顺序后，让每艘船尽早开始

设前一艘船结束使用泊位的时刻为 last，当前船的信息为 $E,R,L$。

当前船既不能在到达前开始，也不能与前一艘船冲突，因此最早开始时刻为

$$\max(last,E).$$

如果在固定顺序下故意推迟当前船，只会让它更晚结束，不会给后面的船带来任何好处。因此，应当让每艘船在满足要求的前提下尽早开始。

只要

$$\max(last,E)\le R,$$

就可以安排当前船，并更新

$$last\leftarrow\max(last,E)+L.$$

否则，这个排列不合法。

为什么代码只判断 last > R？

题目保证 $E\le R$，所以

$$\max(last,E)>R\iff last>R.$$

因此，代码中的

if (last > R) return;
last = max(last, E) + T;

正好对应上述判断和更新。这里不能把合法性条件改成 max(last, E) + T <= R，因为船允许在 $R$ 之后才结束使用泊位。

初始时 last = -1e9。由于所有到达时刻都非负，这使第一艘船直接从自己的到达时刻开始。

3. 算法流程

用 DFS 生成一个完整排列，随后依次模拟每艘船：若 last > R，立即否定当前排列；否则更新结束时刻。

若某个排列中的所有船都检查通过，则令 ans = true。后续进入 DFS 时会直接返回，不再继续深入搜索。若所有排列都不合法，则答案为 NO。

4. 正确性证明

引理：固定船的使用顺序后，尽早安排得到的每一艘船的结束时刻，都不晚于该顺序下任意合法安排中对应船的结束时刻。

用归纳法证明。

对于第一艘船，算法从其到达时刻开始，显然不会晚于任何合法安排。

假设算法安排前一艘船的结束时刻为 $f$，某个合法安排中对应的结束时刻为 $f'$，且 $f\le f'$。设当前船到达时刻为 $E$，占用时长为 $L$。

算法安排当前船的开始时刻为 $\max(f,E)$。合法安排中当前船的开始时刻必须不早于 $\max(f',E)$，而

$$\max(f,E)\le\max(f',E).$$

因此，算法安排当前船的开始和结束时刻均不晚于该合法安排，引理成立。

由引理可知，如果算法给出的最早开始时刻已经超过当前船的最晚开始时刻，那么在相同顺序下，不存在合法安排。反之，如果所有船的最早开始时刻均满足限制，算法本身就构造出了一个合法安排。

因此，算法可以正确判断任意一个排列是否可行。DFS 枚举了所有使用顺序，所以只要存在合法方案，就一定能找到；若找不到，则不存在合法方案。

5. 复杂度分析

对于一组数据，至多枚举 $n!$ 个排列，每个排列的检查耗时为 $O(n)$，因此时间复杂度上界为

$$O(n\cdot n!).$$

排列数组、访问标记和递归栈均占用 $O(n)$ 空间，空间复杂度为

$$O(n).$$

多组数据的总时间复杂度为 $O(\sum n\cdot n!)$；若用统一上界表示，则为 $O(Tn\cdot n!)$，其中 $T$ 是测试数据组数。

6. 参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
struct Ship {
	int E, R, T;
}e[N];
int n, a[N];
bool st[N], ans;
void dfs(int x) {
	if (ans) return;
	if (x > n) {
		int last = -1e9;
		for (int i = 1; i <= n; i ++) {
			int E = e[a[i]].E, R = e[a[i]].R, T = e[a[i]].T;
			if (last > R) return;
			last = max(last, E) + T;
		}
		ans = true;
		return;
	}
	for (int i = 1; i <= n; i ++)
		if (!st[i]) {
			a[x] = i;
			st[i] = true;
			dfs(x + 1);
			st[i] = false;
		}
}
int main() {
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++)
			cin >> e[i].E >> e[i].R >> e[i].T;
		ans = 0;
		dfs(1);
		if (ans) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

---

二、均衡分区（partition）

1. 题意简述

给定一个 $n\times m$ 的正整数矩阵。可以沿行或列之间的边界画贯穿整个矩阵的分区线，使矩阵被分成若干个非空矩形。

要求至少画一条线，并且划分后每个矩形的元素和相等。求不同划分方案的数量。

代码中的 $n,m$ 分别对应题面中的 $H,W$。

2. 核心观察：枚举左上角矩形

直接枚举每一条分区线是否选择，会产生大量组合。代码并不枚举分区线集合，而是枚举左上角第一个矩形的右下角 $(x,y)$。

一旦确定 $(x,y)$，左上角矩形就是第 $1\sim x$ 行、第 $1\sim y$ 列，其元素和也随之确定。记这个和为 sum，那么其他所有矩形的元素和都必须等于 sum。

本题的关键条件是：所有元素均为正数。 因此，在固定高度的横条内，从左向右扩大矩形时，元素和严格递增；在固定宽度的竖条内，从上向下扩大矩形时，元素和同样严格递增。

这意味着：确定左上角矩形后，其余分区线的位置至多只有一种可能。

3. 二维前缀和

令 s[i][j] 表示第 $1\sim i$ 行、第 $1\sim j$ 列的元素和，则

$$s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j].$$

对于第 $x_1+1\sim x_2$ 行、第 $y_1+1\sim y_2$ 列构成的矩形，其元素和为

$$s[x_2][y_2]-s[x_1][y_2]-s[x_2][y_1]+s[x_1][y_1].$$

因此可以在 $O(1)$ 时间内求出任意矩形的元素和。

4. 检查一个候选 $(x,y)$

check(x, y) 判断：是否存在一个均衡划分，使左上角矩形的右下角恰好为 $(x,y)$。

初始化边界

令

$$sum=s[x][y].$$

代码初始化

row = {0, x};
col = {0, y};

这里 row 记录每一横条的结束行，col 记录每一竖条的结束列，开头的 $0$ 用于表示上边界和左边界。最后还必须分别包含 $n$ 和 $m$，表示下边界和右边界。

这些数组同时包含矩阵的外边界坐标；外边界只是用于描述矩形，并不是额外画出的分区线。

在最上方的横条中确定所有竖线

只看第 $1\sim x$ 行。第一个矩形已经占据第 $1\sim y$ 列。

设上一个矩形结束于第 last 列，当前尝试让下一个矩形结束于第 $i$ 列，则其元素和为

$$s[x][i]-s[x][last].$$

由于所有元素为正，随着 $i$ 增大，这个和严格递增。

当它小于 sum 时，当前矩形还不完整，需要继续向右扩展。当它等于 sum 时，这一列就是下一个矩形唯一可能的右边界，记录该边界并令 last = i。当它大于 sum 时，更靠右的位置只会使元素和更大，因此当前候选不可能产生合法划分，立即返回 false。

扫描结束后，还必须满足

col.back() == m

否则说明最右侧剩下了一段不足 sum 的区域，没有恰好分完整。

由于竖线必须贯穿整个矩阵，最上方横条确定的所有竖线，也就是整幅矩阵中的所有竖线。

在最左侧的竖条中确定所有横线

同理，只看第 $1\sim y$ 列。

设上一个矩形结束于第 last 行，当前尝试让下一个矩形结束于第 $i$ 行，其元素和为

$$s[i][y]-s[last][y].$$

按相同规则扫描，记录所有结束行，并检查

row.back() == n

这样便确定了全部横线。

检查所有矩形

确定横线和竖线之后，不能直接判定成功。上述过程只保证了最上方一横条和最左侧一竖条中的矩形符合要求，内部矩形仍然可能不合法。

例如矩阵

$$\begin{pmatrix} 1 & 1\\ 1 & 2 \end{pmatrix}$$

取 $x=y=1$，则 sum = 1。通过第一行和第一列都能确定中间的分区线，但右下角矩形的和为 $2$，不符合要求。

因此，要枚举相邻两条横向边界和相邻两条纵向边界，用二维前缀和检查每一个矩形：

int x1 = row[i - 1], y1 = col[j - 1];
int x2 = row[i], y2 = col[j];
if (s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1] != sum)
    return false;

只有全部检查通过，check(x, y) 才返回 true。

5. 为什么不会重复或漏算？

对于任意一个均衡划分，其左上角矩形的右下角 $(x,y)$ 唯一确定，枚举时一定会访问到它。

固定 $(x,y)$ 后，每个矩形的目标元素和已经确定。由于元素均为正，在最上方横条内，从一个已知左边界出发，元素和恰好等于 sum 的右边界至多有一个；在最左侧竖条内也同理。因此，一组 $(x,y)$ 至多对应一种划分。

也就是说，每个合法划分都会被枚举到，且只会被计数一次。

6. 为什么最后输出 ans - 1？

当 $x=n,y=m$ 时，左上角矩形就是整个矩阵，不画任何内部线也能通过 check。

但是题目要求至少画一条分区线。这个“完全不划分”的方案恰好只有一个，所以最终答案为

$$ans-1.$$

7. 正确性证明

首先，固定左上角矩形后，正数条件保证从任意已确定的边界出发，目标和对应的下一个边界位置至多有一个。因此，只要该候选存在合法划分，扫描第一横条与第一竖条时就一定能恢复出这个划分的全部边界，不会漏掉它。

其次，若 check 返回 true，说明边界覆盖整个矩阵，且所有矩形的元素和都等于 sum，因此得到的划分确实均衡。

最后，所有候选 $(x,y)$ 被完整枚举，而每个均衡划分又恰好对应一个候选。因此，累计得到的 ans 恰好是包含“不划分”在内的均衡方案数；减去这唯一的不合法方案后，即得到题目要求的答案。

8. 复杂度分析

二维前缀和的预处理耗时为 $O(nm)$。

共有 $nm$ 个候选 $(x,y)$。对于一个候选，扫描行列边界耗时 $O(n+m)$，检查所有小矩形至多耗时 $O(nm)$。

因此，总时间复杂度上界为

$$O\bigl(nm(n+m+nm)\bigr)=O(n^2m^2).$$

矩阵和二维前缀和占用 $O(nm)$ 空间，边界数组占用 $O(n+m)$ 空间，因此总空间复杂度为

$$O(nm).$$

9. 参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 55;
int a[N][N], s[N][N], n, m;
bool check(int x, int y) {
	vector<int> row, col;
	row.push_back(0);
	col.push_back(0);
	row.push_back(x);
	col.push_back(y);
	int sum = s[x][y];
	for (int i = y + 1, last = y; i <= m; i ++) {
		if (s[x][i] - s[x][last] > sum) return false;
		if (s[x][i] - s[x][last] == sum) {
			col.push_back(i);
			last = i;
		}
	}
	if (col.back() != m) return false;
	for (int i = x + 1, last = x; i <= n; i ++) {
		if (s[i][y] - s[last][y] > sum) return false;
		if (s[i][y] - s[last][y] == sum) {
			row.push_back(i);
			last = i;
		}
	}
	if (row.back() != n) return false;
	for (int i = 1; i < row.size(); i ++)
		for (int j = 1; j < col.size(); j ++) {
			int x1 = row[i - 1], y1 = col[j - 1];
			int x2 = row[i], y2 = col[j];
			if (s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1] != sum) return false;
		}
	return true;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++) {
			cin >> a[i][j];
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
		}
	int ans = 0;
	for (int x = 1; x <= n; x ++)
		for (int y = 1; y <= m; y ++)
			if (check(x, y)) ans ++;
	cout << ans - 1;
	return 0;
}

---

三、区域重染（recolor）

1. 题意简述

给定一个 $n\times m$ 的颜色矩阵。上下左右相邻且颜色相同的格子属于同一个区域。

恰好执行一次操作：选中一个区域，将其中所有格子同时改成某种颜色。操作后，它可能与周围同色区域合并。

求操作后包含所选区域的连通块的最大大小。允许染成原来的颜色，所以地图可以保持不变。

2. 核心观察：把区域缩成点

操作改变的是一个完整区域，而不是单个格子。因此，不必区分同一区域内部的不同格子，可以把每个原有区域看成一个点。

用 DFS 遍历所有同色连通块，记录

• id[x][y]：格子 $(x,y)$ 所属区域的编号；
• sz[u]：区域 $u$ 包含的格子数；
• color[u]：区域 $u$ 的原颜色。

tot 是区域总数。每次发现一个未编号格子，就建立一个新区域，从该格子出发，只沿着同色且尚未编号的相邻格子继续 DFS。

完成之后，每个格子恰好属于一个区域，区域大小和颜色也都已经确定。

3. 建立区域之间的相邻关系

遍历每个格子及其四个方向。如果两个相邻格子属于不同区域，就在这两个区域之间连边。

代码使用

set<int> e[N * N];

存储邻接关系，其中 e[u] 是与区域 $u$ 相邻的区域编号集合。

为什么必须去重？

两个区域可能通过多条格子边相邻。例如，一个区域可能沿着很长的一段边界接触另一个区域。

无论接触多少次，重染后都只能把这个相邻区域计入一次。因此，需要按区域编号去重。set 正是为了确保每个相邻区域在 e[u] 中只出现一次。

注意，不是按颜色去重：多个互不相同的区域可能颜色相同，它们都应当分别贡献各自的大小。

4. 枚举被重染的区域，按颜色汇总邻居

假设把区域 $u$ 改成颜色 $C$，则它会与所有满足下列条件的原有区域合并：与 $u$ 相邻，并且颜色为 $C$。

所以新区域的大小为

$$sz[u]+\sum_{\substack{v\in e[u]\\color[v]=C}}sz[v].$$

对于同一个被重染区域 $u$，只需要找出邻居中哪一种颜色对应的总大小最大。

代码使用 map<int, int> mp，其中

$$mp[C]=\sum_{\substack{v\in e[u]\\color[v]=C}}sz[v].$$

遍历每个相邻区域 j 时执行

mp[color[j]] += sz[j];
t = max(t, mp[color[j]]);

扫描完成后，t 就是能够合并进来的最大格子数，因此用

ans = max(ans, sz[i] + t);

更新答案。

例如，一个大小为 $4$ 的区域，周围有两个颜色为 $3$、大小分别为 $2$ 和 $3$ 的区域，以及一个颜色为 $5$、大小为 $4$ 的区域。染成 $3$ 可以得到

$$4+2+3=9,$$

而染成 $5$ 只能得到 $4+4=8$。因此，应该比较的是同一种颜色的相邻区域大小之和，而不是单个相邻区域的最大大小。

5. 为什么只需要考虑直接相邻的区域？

可能会担心：重染之后先合并某个相邻区域，是否还能经由它继续合并更远的同色区域？

如果两个原有区域颜色相同且相邻，它们在操作前就已经属于同一个连通块，不会被编号为两个不同区域。

操作只改变区域 $u$ 的颜色，其余格子保持不变。对于目标颜色 $C$，任何与 $u$ 相邻的原有颜色 $C$ 区域都会整体并入；而一个不与 $u$ 相邻的原有颜色 $C$ 区域，不可能通过其他原有颜色 $C$ 区域额外连入，否则它们原本就是同一个区域。

因此，合并范围恰好是“区域 $u$ 本身，加上所有与它直接相邻的目标颜色区域”，不需要在区域图上进行多轮扩展。

6. 为什么不用枚举所有颜色？

颜色范围可达 $10^9$，但固定区域 $u$ 后，只有出现在其邻居中的颜色才可能增加得分。选择其他颜色，只能保留原区域大小 sz[u]。

由于题目允许染成原色，即使无法合并任何邻居，得到 sz[u] 也始终是合法选择。代码把 t 初始化为 $0$，已经包含了这种情况。

因此，只需通过 map 统计邻居中实际出现的颜色，不必遍历整个颜色范围。

7. 正确性证明

首先，DFS 只访问同色且相邻的格子，并将所有可达格子编号为同一区域，因此得到的恰好是原矩阵中的所有同色连通块。

其次，遍历格子边建立邻接关系，能够找出所有相邻区域；set 去重保证每个相邻区域只被记录一次，不会重复贡献大小。

固定被重染区域 $u$ 和目标颜色 $C$。根据前面的分析，重染后的连通块恰好由 $u$ 和所有相邻的原有颜色 $C$ 区域组成。代码中的 mp[C] 正确累加了这些区域的大小，因此 sz[u] + mp[C] 就是该操作的得分。

对邻居颜色取最大值，并保留不增加大小的基准情况，就能得到固定 $u$ 时的最优得分。最后枚举所有区域 $u$，便覆盖了所有可能的重染操作，得到全局最高分。

8. 复杂度分析

令 $V=nm$，即格子总数。

DFS 处理所有格子和相邻关系，耗时为 $O(V)$。

原网格中格子间的相邻边总数为 $O(V)$，所以缩点后的不同区域之间的边数也为 $O(V)$，所有邻接集合的大小之和为 $O(V)$。

建图时，总共进行 $O(V)$ 次 set 插入尝试，单次操作的时间复杂度上界为 $O(\log V)$。随后按颜色汇总时，每个区域的邻接集合被扫描一次，总共进行 $O(V)$ 次 map 更新，单次更新同样至多耗时 $O(\log V)$。

因此，原代码的总时间复杂度上界为

$$O(V\log V)=O\bigl(nm\log(nm)\bigr).$$

颜色矩阵、区域编号、区域信息、邻接集合、临时映射以及 DFS 递归栈合计占用 $O(V)$ 空间，所以空间复杂度为

$$O(nm).$$

这里不能忽略 set 和 map 的开销，将原实现直接写成线性时间复杂度。

9. 与原代码有关的实现说明

建图部分没有显式判断邻居是否在地图内，而是通过 id[a][b] 是否为 $0$ 过滤。当前实现中，id 是全局数组，未赋值的位置初始为 $0$；数组边长为 $510$，实际行列数至多为 $500$，四方向访问产生的外围坐标仍然在数组范围内。因此，这里的边界处理成立。

10. 参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m, c[N][N];
int id[N][N], tot, sz[N * N], color[N * N];
set<int> e[N * N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
void dfs(int x, int y) {
	id[x][y] = tot;
	sz[tot] ++;
	for (int i = 0; i < 4; i ++) {
		int a = x + dx[i], b = y + dy[i];
		if (a >= 1 && a <= n && b >= 1 && b <= m
			&& c[a][b] == c[x][y] && !id[a][b]) dfs(a, b);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			cin >> c[i][j];
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if (!id[i][j]) {
				tot ++;
				color[tot] = c[i][j];
				dfs(i, j);
			}
	for (int x = 1; x <= n; x ++)
		for (int y = 1; y <= m; y ++) {
			int u = id[x][y];
			for (int i = 0; i < 4; i ++) {
				int a = x + dx[i], b = y + dy[i];
				if (id[a][b] && id[a][b] != id[x][y]) {
					int v = id[a][b];
					e[u].insert(v);
					e[v].insert(u);
				}
			}
		}
	int ans = 0;
	for (int i = 1; i <= tot; i ++) {
		int t = 0;
		map<int, int> mp;
		for (int j : e[i]) {
			mp[color[j]] += sz[j];
			t = max(t, mp[color[j]]);
		}
		ans = max(ans, sz[i] + t);
	}
	cout << ans;
	return 0;
}

---

四、校准配对（calibrate）

1. 题意简述

给定偶数个校准片，第 $i$ 个校准片上的数值为 $A_i$。需要将所有校准片两两配对，使每一对的数值 $u,v$ 至少满足以下一个条件：

$$|u-v|=d\quad\text{或}\quad u+v=s.$$

判断是否存在合法的完整配对方案。

代码中的 n,d,s 分别对应题面中的 $N,D,S$。其中 $d\ge0$，相同数值的校准片仍然是不同物品，配对时需要分别使用。

2. 核心观察：从最小值和最大值入手

代码用 multiset<int> S 保存尚未配对的校准片数值。每一轮取出当前最小值和最大值：

int x = *S.begin(), y = *S.rbegin();

由于 $x$ 是最小值，如果它通过“差为 $d$”的条件配对，搭档只能是 $x+d$；如果它通过“和为 $s$”的条件配对，搭档只能是 $s-x$。

同理，最大值 $y$ 的搭档只能是 $y-d$ 或 $s-y$。

这里也包含 $d=0$ 的情况：通过差值条件配对时，需要另一张数值相同的校准片。

因此，比较 $x+y$ 与 $s$，就能判断某一端是否无法通过和的条件配对，从而确定这一轮应该删除哪两个数。

3. 三种情况分别处理

当 $x+y<s$ 时，最小值只能与 $x+d$ 配对

所有剩余数值都不超过 $y$，所以对任何可能的搭档 $v$，都有

$$x+v\le x+y<s.$$

因此，最小值 $x$ 不可能通过“和为 $s$”的条件配对，只能使用差值条件。

由于没有比 $x$ 更小的数，它的搭档只能是 $x+d$。

于是，如果能够取出数值分别为 $x$ 和 $x+d$ 的两张校准片，就删除它们；否则，不存在完整配对方案，直接返回 false。

这里不是从多个搭档中随意选择，而是最小值的搭档数值已经被迫确定。 相同数值的校准片在配对条件上没有区别，取出其中任意一张即可。

当 $x+y>s$ 时，最大值只能与 $y-d$ 配对

所有剩余数值都不小于 $x$，所以对任何可能的搭档 $v$，都有

$$y+v\ge y+x>s.$$

因此，最大值 $y$ 不可能通过“和为 $s$”的条件配对，只能使用差值条件。

由于没有比 $y$ 更大的数，它的搭档只能是 $y-d$。

于是，如果能够取出数值分别为 $y$ 和 $y-d$ 的两张校准片，就删除它们；否则直接返回 false。

这与上一种情况完全对称，同样属于搭档被迫确定的情况。

当 $x+y=s$ 时，直接将最小值和最大值配对

这时 $(x,y)$ 本身就是合法的一对，代码直接删除它们。

但是，仅仅说明这一对合法，还不能证明贪心正确：会不会先用掉这两个数，导致剩下的校准片无法配对？这里需要使用交换论证。

假设当前存在一个完整配对方案。选定一张数值为 $x$ 的校准片和另一张数值为 $y$ 的校准片。如果它们已经互相配对，则不需要调整。

否则，设它们原来的搭档数值分别为 $p,q$，原方案中包含

$$(x,p),\qquad(y,q).$$

这四张校准片互不相同，但它们的数值可以相同。接下来证明，$(p,q)$ 一定也是合法的一对。

如果 $p=y$，那么 $(p,q)$ 与原来的 $(y,q)$ 具有相同的数值，因此合法。

如果 $q=x$，那么 $(p,q)$ 与原来的 $(p,x)$ 具有相同的数值，因此也合法。

否则，$p\ne y$ 且 $q\ne x$。因为 $s-x=y$、$s-y=x$，原来的两对都不能通过和的条件成立，只能通过差值条件成立。结合 $x$ 是最小值、$y$ 是最大值，得到

$$p=x+d,\qquad q=y-d.$$

于是

$$p+q=(x+d)+(y-d)=x+y=s,$$

所以 $(p,q)$ 仍然合法。

无论哪种情况，都可以将原来的两对替换成

$$(x,y),\qquad(p,q),$$

而不影响其他配对。

因此，只要当前存在完整配对方案，就一定存在一个让所选最小值与最大值互相配对的完整方案。 直接删除它们，不会把有解的情况变成无解。

4. multiset 的实现细节

相同数值需要分别保存、分别删除

题目允许多个校准片具有相同数值，因此使用能够保存重复元素的 multiset，而不是 set。

每次只应删除一张校准片，所以代码使用

S.erase(S.find(x));

先找到一个对应元素，再通过迭代器删除它。不能直接写成 S.erase(x)，因为按数值删除会把所有等于 $x$ 的元素一并删除。

为什么先删除搭档，再检查当前值是否还存在？

以 $x+y<s$ 的分支为例，代码先找到并删除一个 $x+d$，随后再次查找 $x$，存在时才删除。

这是为了正确处理 $d=0$。

当 $d=0$ 时，$x+d=x$。即使集合中能够找到 $x$，也不代表有两张数值为 $x$ 的校准片。先删除一张，再检查是否还有另一张，才能保证配对使用的是两个不同物品。

如果原来只有一张，第二次查找失败，返回 false；如果至少有两张，就能正确删掉两张。处理 $y-d$ 的分支同理。

当 $x+y=s$ 且 $x=y$ 时，也需要删除两个相同数值。由于最小值等于最大值，集合内的所有数值都相同；又因为初始校准片数量为偶数，每轮成功操作都删除两张，所以非空集合至少还有两张，两次删除都是合法的。

只需要判断是否存在

代码使用 find 判断所需数值是否存在，不需要统计该数值的全部出现次数。

每一轮只进行常数次查找和删除。这也是复杂度分析中能够将每轮操作控制在 $O(\log n)$ 的依据。

5. 正确性证明

证明每轮操作都保持“当前集合是否存在完整配对方案”不变。

当 $x+y<s$ 时，最小值 $x$ 必须与 $x+d$ 配对；当 $x+y>s$ 时，最大值 $y$ 必须与 $y-d$ 配对。如果没有足够的校准片完成这一对，当前一定无解；否则删除这一对后，剩余集合有解当且仅当原集合有解。

当 $x+y=s$ 时，根据交换论证，只要原集合有解，就可以调整出一个包含 $(x,y)$ 的完整方案，因此删除所选的这两张校准片后，剩余集合仍然有解。反过来，如果剩余集合有解，把合法的一对 $(x,y)$ 加回去，就能得到原集合的完整配对方案。

所以，每次成功删除一对都不会改变有解性；每次返回 false 都说明当前不存在完整方案，从而原问题也无解。

每轮成功操作都会删除两张校准片，因此过程一定结束。如果最终集合为空，说明所有校准片都已经被组成合法的配对，返回 true。

综上，算法输出 YES 当且仅当存在合法的完整配对方案。

6. 复杂度分析

对于一组数据，逐个向 multiset 插入 $n$ 个数，需要 $O(n\log n)$ 时间。

随后至多成功删除 $n/2$ 对校准片。每一轮进行常数次查找和删除，耗时上界为 $O(\log n)$，因此总时间复杂度为

$$O(n\log n).$$

集合中至多保存 $n$ 个数，因此空间复杂度为

$$O(n).$$

多组数据的总时间复杂度为 $O(\sum n\log n)$。题目保证所有测试组的 $n$ 之和不超过 $2\times10^5$。

7. 参考代码

#include<bits/stdc++.h>
using namespace std;
bool solve() {
	multiset<int> S;
	int n, d, s;
	cin >> n >> d >> s;
	while (n --) {
		int x;
		cin >> x;
		S.insert(x);
	}
	while (S.size()) {
		int x = *S.begin(), y = *S.rbegin();
		if (x + y == s) {
			S.erase(S.find(x));
			S.erase(S.find(y));
		} else if (x + y < s) {
			if (S.find(x + d) != S.end()) {
				S.erase(S.find(x + d));
				if (S.find(x) != S.end()) {
					S.erase(S.find(x));
				} else {
					return false;
				}
			} else {
				return false;
			}
		} else {
			if (S.find(y - d) != S.end()) {
				S.erase(S.find(y - d));
				if (S.find(y) != S.end()) {
					S.erase(S.find(y));
				} else {
					return false;
				}
			} else {
				return false;
			}
		}
	}
	return true;
}
int main() {
	int T;
	cin >> T;
	while (T --) {
		if (solve()) cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}