补题链接

• T1 展品归位（shelf）
• T2 避险路线（shelter）
• T3 菜单排期（menu）
• T4 星图定位（stars）
• T5 琴弦调音（harp）
• T6 辣度清单（chili）

讲题录屏

录制：CSP-J&S模拟赛第3场

日期：2026-10-04 19:04:12

录制文件：https://meeting.tencent.com/crm/2MYo4mxM2b

访问密码：5XMN

T1 辣度清单（chili）

简要题意

依次加入 $N$ 个辣椒，每个辣椒有一个名称和与之对应的固定辣度。同一种辣椒可以出现多次，每次都要计入总和。给出所有名称，求最终辣度，其中 $1\le N\le1000$。

思路：名称查表，逐次累加

题目只给出了六种辣椒，可以用两个数组一一对应地存储名称和辣度：name[i] 表示第 $i$ 种辣椒的名称，val[i] 表示它的辣度。

名称	辣度
Poblano	$1500$
Mirasol	$6000$
Serrano	$15500$
Cayenne	$40000$
Thai	$75000$
Habanero	$125000$

每次读入字符串 s，从前往后枚举这六种名称。找到 s == name[i] 时，将 val[i] 加入答案 sum，然后退出内层循环，继续处理下一个辣椒。

例如样例中的四个名称对应辣度为 $1500,40000,75000,1500$，答案为

$$1500+40000+75000+1500=118000.$$

两次出现 Poblano 就累加两次，不能按名称去重。

正确性

初始时没有加入辣椒，sum = 0 正确。每处理一个名称，程序都从对应表中找到该辣椒的辣度，并且恰好累加一次。因此处理前 $i$ 个名称后，sum 就是这 $i$ 个辣椒的辣度之和；处理完所有名称后即得到答案。

复杂度与实现要点

每个名称最多比较六次，名称长度也是常数，因此时间复杂度为 $O(N)$，额外空间复杂度为 $O(1)$。

最大答案为 $1000\times125000=125000000$，int 足够。找到匹配项后的 break 只退出查表的 for 循环，不会提前结束外层读入。

参考代码

#include<bits/stdc++.h>
using namespace std;
string name[] = {"Poblano", "Mirasol", "Serrano", "Cayenne", "Thai", "Habanero"};
int val[] = {1500, 6000, 15500, 40000, 75000, 125000};
int main() {
	int n;
	cin >> n;
	int sum = 0;
	while (n --) {
		string s;
		cin >> s;
		for (int i = 0; i < 6; i ++)
			if (s == name[i]) {
				sum += val[i];
				break;
			}
	}
	cout << sum;
	return 0;
}

T2 琴弦调音（harp）

简要题意

若干条调音指令首尾相接，每条指令由“非空字母串、一个 + 或 -、一个正整数”组成。字母在 A 到 T 之间，+ 表示 tighten，- 表示 loosen。按原顺序把每条指令拆成一行，三个字段之间用空格分隔；字符串总长度 $L\le160$，圈数可能有多位。

思路：按三种字符依次扫描

用指针 i 从左向右扫描字符串。每次外层循环处理一条完整指令：

1. 连续读到字母时，直接输出这些字母，保持顺序不变。
2. 接下来必然是 + 或 -，分别输出带有前后空格的 tighten 或 loosen，再跳过该符号。
3. 连续读到数字时，直接输出这些数字。直到下一个字母或字符串结尾，输出换行，开始处理下一条指令。

这里不需要计算圈数，也就不必将数字串转换成整数。STD采用的是“原样输出整个数字段”，所以一位数和多位数的处理方法相同。

例如 AFB+8HC-4 的扫描过程是：

• 输出 AFB，把 + 翻译成 tighten，输出 8，换行。
• 输出 HC，把 - 翻译成 loosen，输出 4，换行。

正确性

合法指令中的字母、符号、数字依次出现，三种字符类别不会混淆。字母段在符号处结束，数字段在下一条指令的字母处或整串结尾结束，因此扫描能唯一确定每条指令的边界。

每次循环完整输出一条指令，并把指针移动到下一条指令开头；所有字符都按原顺序处理，既不会遗漏指令，也不会重复输出。

复杂度与实现要点

指针只向右移动，每个字符处理常数次，时间复杂度为 $O(L)$。存储输入字符串需要 $O(L)$ 空间，除此以外只使用 $O(1)$ 额外空间。

• 数字段必须用循环输出，不能只处理第一个数字。
• 外层 for 的第三部分为空，因为三段扫描各自推进 i；不能再无条件多移动一次。
• 原代码的字母判断范围写为 'A' 到 'z'。在本题只含 A～T、正负号和数字的合法输入上，它能够正确区分字母；若把代码推广到任意字符串，则应按实际字符范围调整判断。
• 参考代码最后一个数字段可能读到 s[s.size()]。C++14 中对该位置只读会得到字符串末尾的空字符，因此数字循环结束；它不会继续访问更后面的位置。一般自行实现时，也可以显式添加 i < s.size() 的判断。

参考代码

#include<bits/stdc++.h>
using namespace std;
int main() {
	string s;
	cin >> s;
	for (int i = 0; i < s.size();) {
		while (s[i] >= 'A' && s[i] <= 'z') cout << s[i], i ++;
		if (s[i] == '+') cout << " tighten ";
		else cout << " loosen ";
		i ++;
		while (s[i] >= '0' && s[i] <= '9') cout << s[i], i ++;
		cout << "\n";
	}
	return 0;
}

---

T3 星图定位（stars）

简要题意

给出包含 $M$ 个点的星图和包含 $N$ 个点的照片。只能将星图整体平移，不能旋转、翻转或缩放；照片中可以有多余的点。求唯一的平移量 $(\Delta x,\Delta y)$，使星图平移后的每个点都出现在照片中。

每组数据满足 $1\le M\le200$、$M\le N\le1000$，坐标在 $0$ 至 $10^6$ 之间，同一输入文件中所有组的 $N$ 之和不超过 $2000$。

部分分：$N=M$，40 分

测试点 $1\sim8$ 保证 $N=M$，共 40 分。此时照片中的点没有剩余，平移后的星图与照片恰好是同一个点集。

设星图中最小的横坐标、纵坐标分别为 $x_A,y_A$，照片中对应的最小值分别为 $x_B,y_B$。所有点都加上同一个平移量，因此最小值也增加相同的量：

$$\Delta x=x_B-x_A,\qquad \Delta y=y_B-y_A.$$

扫描两个点集即可，时间复杂度为 $O(M+N)$。这里的最小横坐标和最小纵坐标可以来自不同的点，因为我们分别利用两个坐标轴上的最小值变化规律。

当 $N>M$ 时，多余星点可能改变照片的坐标最小值，上述做法便不再有正确性保证。

正解推导：固定一个点，枚举它的对应点

一次平移由横、纵两个改变量唯一确定。只要知道星图中某个点平移后落到照片中的哪个点，就能算出这两个改变量。

固定星图中的第一个点 $a_1=(x_1,y_1)$。它在正确平移后一定与照片中的某个点重合，因此枚举照片中的每个点 $b_i=(u_i,v_i)$，尝试让 $a_1$ 与 $b_i$ 对齐。此时唯一可能的平移量为

$$\Delta x=u_i-x_1,\qquad \Delta y=v_i-y_1.$$

接下来逐个检查星图中的点 $a_j=(x_j,y_j)$：平移后的点

$$(x_j+\Delta x,\ y_j+\Delta y)$$

是否出现在照片中。只要有一个点不存在，就立即放弃本次候选；如果所有点都存在，当前平移量就是答案。

STD 用 set<PII> S 保存照片中的全部坐标，调用 S.count(p) 判断一个完整的坐标对是否存在，单次查询的时间复杂度为 $O(\log N)$。必须把横、纵坐标作为同一个点查询，不能分别判断两个坐标是否出现过。

题目允许照片存在额外星点，所以只需要检查星图中的全部 $M$ 个点，不要求照片中的每个点都被使用。星图中的点互不相同，整体平移后仍互不相同，也不需要额外标记照片中的点是否已匹配。

正确性证明

首先证明正确答案一定被枚举到。设真正的平移量为 $(\Delta x^*,\Delta y^*)$，星图中的 $a_1$ 平移后必然是照片中的某个点 $b_k$。当程序枚举到 $b_k$ 时，计算出的平移量恰为 $(\Delta x^*,\Delta y^*)$，并且星图中的每个点都能通过检查。

再证明程序输出的答案一定合法。程序只会在全部 $M$ 个平移后的点都属于照片点集时输出；所有点使用的平移量相同，因此输出结果满足题目要求。

所以程序不会遗漏合法平移，也不会输出非法平移。结合题目保证答案存在且唯一，第一次通过完整检查的平移量就是所求答案。

复杂度

每组数据建立集合需要 $O(N\log N)$ 时间。至多枚举 $N$ 个候选平移，每个候选至多查询 $M$ 个点，因此总时间复杂度为

$$O(N\log N+MN\log N)=O(MN\log N),$$

空间复杂度为 $O(M+N)$，用于保存两个点集和照片集合。

代码关键变量

• m、n：分别对应题面中的星图点数 $M$、照片点数 $N$。
• a[j]、b[i]：星图中的第 $j$ 个点、照片中的第 $i$ 个点；代码中的 .x、.y 分别是 pair 的第一、第二个分量。
• S：保存照片中全部坐标对的有序集合，每组数据重新建立。
• dx、dy：令 a[1] 与当前 b[i] 对齐得到的候选平移量。
• p：当前星图点按照候选平移量移动后的坐标。
• flag：当前候选是否仍可能合法；遇到一个不存在的点便设为 false 并结束检查。

原坐标非负，但 dx、dy 可能为负。按照坐标范围，候选平移后的坐标在 $[-10^6,2\times10^6]$ 内，人工代码使用 int 足够。

参考代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
PII a[N], b[N];
int main() {
	int T;
	cin >> T;
	while (T --) {
		int m, n;
		cin >> m;
		for (int i = 1; i <= m; i ++) cin >> a[i].x >> a[i].y;
		cin >> n;
		set<PII> S;
		for (int i = 1; i <= n; i ++) {
			cin >> b[i].x >> b[i].y;
			S.insert(b[i]);
		}
		for (int i = 1; i <= n; i ++) {
			// 尝试用a[1]和b[i]对齐
			int dx = b[i].x - a[1].x, dy = b[i].y - a[1].y;
			bool flag = true;
			for (int j = 1; j <= m; j ++) {
				PII p = {a[j].x + dx, a[j].y + dy};
				if (!S.count(p)) {
					flag = false;
					break;
				}
			}
			if (flag) {
				cout << dx << ' ' << dy << "\n";
				break;
			}
		}
	}
	return 0;
}

T4 菜单排期（menu）

简要题意

安排 $N$ 天的菜单，每天从 $1,2,3$ 三种主菜中选择一种，其中 $K$ 天的主菜已固定。要求任意连续三天不能供应同一种主菜，连续两天相同则允许。求合法安排数对 $10000$ 取模的结果。

每组数据满足 $3\le N\le100$、$1\le K\le N$；固定安排的日期互不相同，输入时不一定按日期排序，并保证至少存在一种合法安排。

部分分：$N\le12$，30 分

测试点 $1\sim6$ 保证 $N\le12$，共 30 分。可以按日期从前向后搜索：已经固定的日期只尝试指定的主菜，其余日期分别尝试三种主菜。

安排第 $i$ 天时，如果 $i\ge3$，就检查当天与前两天是否全都相同。若相同，当前分支立即结束；否则继续安排下一天。成功安排完全部 $N$ 天时，方案数加一。

搜索树每层至多有三个分支，每次扩展只需常数时间检查，时间复杂度为 $O(3^N)$，递归及保存菜单的空间复杂度为 $O(N)$。当 $N\le12$ 时，未剪枝的完整菜单也只有至多 $3^{12}=531441$ 种；但 $N$ 增大到 $100$ 时，指数级枚举无法继续使用。

正解推导：只记录最后两天

从搜索过程可以发现：假设前 $i-1$ 天的安排已经合法，决定第 $i$ 天能不能选某种主菜时，只需要知道第 $i-1$ 天和第 $i-2$ 天的主菜。

更早的日期不会和第 $i$ 天组成连续三天，而它们内部的合法性已经检查过。因此，如果若干种前缀安排的最后两天相同，那么它们能够接上的下一种主菜也相同，可以把这些安排合并计数。

定义

$$f[i][a][b]$$

表示前 $i$ 天已经安排完毕且合法，第 $i$ 天主菜为 $a$、第 $i-1$ 天主菜为 $b$ 的方案数，对 $10000$ 取模。注意状态中先记录当天，再记录前一天。

用 p[i] 保存第 $i$ 天的固定安排：p[i] = 0 表示未固定，否则只能选 p[i] 对应的主菜。

空状态与前两天的处理

为了统一处理前两天，人工代码用 $0$ 表示“这一天尚不存在”，它不是一种真正的主菜。先将所有状态清零，再设置

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

含义是：尚未安排任何日期时，空安排有且只有一种。

第 $1$ 天只能从这个空状态转移，产生 $f[1][a][0]$；第 $2$ 天再由这些状态产生 $f[2][a][b]$。由于新选的主菜始终在 $1,2,3$ 中，前两天涉及的占位值 $0$ 不可能和它组成三个相同的数，不会错误地触发限制。

从第 $2$ 天结束开始，能够有贡献的状态中，最后两天的主菜都已经是 $1,2,3$。所以从第 $3$ 天开始，程序就会正常检查连续三天是否相同。

状态转移与答案

枚举当天的主菜 $a\in\{1,2,3\}$。如果当天已有固定安排且 p[i] != a，就跳过这个选择。

随后枚举前一天的主菜 $b$、前两天的主菜 $c$。对应的旧状态为 $f[i-1][b][c]$。在这个前缀后面添加 $a$ 时，唯一新出现的连续三天是第 $i-2,i-1,i$ 天，所以只有 $a=b=c$ 时不能转移。其余情况下执行

$$f[i][a][b] \leftarrow \bigl(f[i][a][b]+f[i-1][b][c]\bigr)\bmod10000.$$

为了兼容初始空状态，代码枚举 $b,c\in\{0,1,2,3\}$。其中不符合实际日期含义的状态一直为 $0$，不会额外贡献方案。

最终，所有合法菜单都按最后两天的主菜分类。题目保证 $N\ge3$，因此最后两天确实存在，答案为

$$\left(\sum_{a=1}^{3}\sum_{b=1}^{3}f[N][a][b]\right)\bmod10000.$$

例如样例中第 $1,3$ 天都固定为主菜 $1$，转移到第 $3$ 天时，前三天全为 $1$ 的状态会被排除，因此第 $2$ 天只能选 $2$ 或 $3$。第 $4$ 天固定为 $2$，第 $5$ 天三种主菜都能选择，共得到 $2\times3=6$ 种安排。

正确性证明

对已安排的天数 $i$ 归纳。

当 $i=0$ 时，只有一个空安排，故 $f[0][0][0]=1$，其余状态为 $0$，初始化正确。

假设第 $i-1$ 层已经正确统计所有合法前缀。向其中一个前缀添加当天主菜 $a$ 时，程序先检查当天是否满足固定安排，再排除 $a=b=c$。旧前缀本身已经合法，而新出现的连续三天只有末尾这一组，因此通过检查后得到的前 $i$ 天安排一定合法。

反过来，任意一个合法的前 $i$ 天安排，删去最后一天后，都得到一个已被正确统计的合法前缀。它当天的主菜满足固定要求，末尾也没有连续三天相同，因此一定能通过相应转移重新得到这个安排。其前缀和最后一天都是唯一确定的，所以不会重复计数。

由归纳可知，全部状态计数正确。最后对最后两天的所有实际主菜组合求和，就得到全部合法菜单的方案数；在每次加法后取模不会改变最终对 $10000$ 取模的结果。

复杂度

每天枚举 $3$ 种当天主菜、$4$ 种前一天状态和 $4$ 种前两天状态，共 $3\times4\times4$ 次常数操作。每组数据的时间复杂度为 $O(N)$。

人工代码保留全部日期的 DP 状态，空间复杂度为 $O(N)$。

代码关键变量

• n：总天数 $N$；读入时的 m：已经固定的天数 $K$。
• p[i]：第 $i$ 天固定的主菜，值为 0 时当天可以自由选择。按日期下标存储，因此固定安排的输入顺序不影响计算。
• f[i][a][b]：前 $i$ 天合法、当天为 $a$、前一天为 $b$ 的方案数。
• 转移中的 a、b、c：依次表示第 $i$ 天、第 $i-1$ 天、第 $i-2$ 天的主菜，不能把 f[i][a][b] 的后两维顺序颠倒。
• mod：模数 $10000$；ans：最后一层所有实际主菜组合的方案数之和。

每组数据开始时，人工代码重新清空 p[1..n] 和整个 f 数组，再设置空状态，避免多组数据之间相互影响。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110, mod = 10000;
int p[N];
int f[N][4][4]; // f[i][a][b]表示考虑前i天的菜单, 第i天主菜为a, 第i-1天主菜为b的方案数
int main() {
	int T;
	cin >> T;
	while (T --) {
		int n, m;
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) p[i] = 0;
		while (m --) {
			int a, b;
			cin >> a >> b;
			p[a] = b;
		}
		memset(f, 0, sizeof f);
		f[0][0][0] = 1;
		for (int i = 1; i <= n; i ++) {
			for (int a = 1; a <= 3; a ++) {
				if (p[i] && p[i] != a) continue;
				for (int b = 0; b <= 3; b ++)
					for (int c = 0; c <= 3; c ++) {
						if (a == b && a == c) continue;
						f[i][a][b] = (f[i][a][b] + f[i - 1][b][c]) % mod;
					}
			}
		}
		int ans = 0;
		for (int a = 1; a <= 3; a ++)
			for (int b = 1; b <= 3; b ++)
				ans = (ans + f[n][a][b]) % mod;
		cout << ans << "\n";
	}
	return 0;
}

---

T5 避险路线（shelter）

简要题意

给定一张有 $n$ 座城市、$m$ 条双向道路的无向图，其中 $k$ 座城市被封锁，不能进入。在原图上，到任意封锁城市的最少道路条数不超过 $s$ 的未封锁城市是危险城市，其余是普通城市。经过普通中间城市需要支付 $P$，经过危险中间城市需要支付 $Q$，且 $P<Q$。城市 $1$ 和城市 $n$ 不收费，求从 $1$ 到 $n$ 的最小总费用。

题目保证起终点没有被封锁，而且存在一条不经过封锁城市的路线。每组 $n\le10^5$、$m\le2\times10^5$；每个输入文件至多 $10$ 组，$\sum n\le2\times10^5$、$\sum m\le4\times10^5$。

部分分路线

本题有 $20$ 个独立测试点，每点 $5$ 分。下表中的累计分数指按公开限制能够覆盖的完整测试点组。

测试点	附加限制	对应做法	本组分值
$1\sim6$	$k=0$	普通 BFS 求最少边数	$30$ 分
$7\sim12$	$n\le160$	求出危险区域后，使用朴素 Dijkstra
$13\sim20$	无	多源 BFS 加堆优化 Dijkstra	$40$ 分

当 $k=0$ 时，没有危险城市，每个中间城市都收取 $P$。如果最少经过 $L$ 条道路，那么其中有 $L-1$ 座中间城市，答案为 $(L-1)P$。用 BFS 求 $L$，时间复杂度为 $O(n+m)$，可解决前 $30$ 分。

对于 $n\le160$ 的小图，危险区域确定后，直接使用朴素 Dijkstra：每轮扫描全部城市，选出距离最小且尚未确定的城市，再沿它的道路松弛。时间复杂度为 $O(n^2+m)$。将这一路线与 $k=0$ 的 BFS 分支结合，即可覆盖前 $12$ 个测试点，累计 $60$ 分。小图也可以使用 Floyd，但需要分别处理原图道路距离和禁止经过封锁城市的费用距离。

正解推导

1. 用多源 BFS 确定危险城市

这里有两个不同的问题：判断危险程度时，比较的是原图上的道路条数；寻找实际路线时，比较的是住宿费用，而且不能进入封锁城市。先解决前者，再解决后者。

把所有封锁城市同时放入 BFS 队列，令它们的距离为 $0$，其他城市距离为 $-1$。从全部源点一起向外扩展，得到每座城市到最近封锁城市的最少道路条数。

STD 用 g 保存城市类别：0 表示普通，1 表示危险，2 表示封锁。读入封锁城市时先将它们标为 2。BFS 首次访问一个城市 j 后，若 d[j] <= s，就把它标为危险。所有封锁城市的距离起初已经是 $0$，不会再次作为未访问点入队，因此不会被覆盖成危险城市。

这份实现会在原图上完成整次 BFS，不在距离达到 $s$ 时截断。只有距离不超过 $s$ 的未封锁城市被标记为危险，距离更远的城市保持普通。BFS 没有访问到的城市也保持普通；这包括 $k=0$ 时的所有城市，以及完全不含封锁城市的连通块。

2. 把住宿费放在进入城市的转移上

对于一条从 $u$ 走向 $v$ 的道路：

• 如果 $v$ 被封锁，不允许这次转移。
• 如果 $v=n$，转移费用为 $0$。
• 否则，如果 $v$ 普通，转移费用为 $P$；如果 $v$ 危险，转移费用为 $Q$。

所以，同一条无向道路的两个方向可能有不同费用，因为费用取决于到达的城市。程序不需要另建有向带权图，在枚举邻点时计算进入费用即可。

令 d[1] = 0，用小根堆维护暂定费用，运行 Dijkstra。每次弹出尚未确定的城市 u，将它标记为已确定，再尝试沿允许的道路更新相邻城市。最后的 d[n] 就是答案。

STD 只在转移时显式判断 j != n，没有额外判断 j != 1。这是正确的：起点已经有 d[1] = 0，所有费用都非负，返回起点的转移不可能得到严格小于 $0$ 的距离，因此不会更新起点。这种写法不会使答案多收一次起点住宿费。

正确性证明

首先，多源 BFS 按道路条数从小到大扩展。将全部封锁城市同时作为距离为 $0$ 的源点，等价于同时考察从所有封锁城市出发的路线。因此每座可达城市首次获得的距离，恰好是它到最近封锁城市的最少道路条数。程序按该距离是否不超过 $s$ 标记危险城市，分类正确。

其次，固定一条不经过封锁城市的简单路线。程序对每座到达的中间城市收取其对应住宿费，对终点收费为 $0$，起点初始费用为 $0$，所以沿途转移费用之和恰好等于这条路线的住宿费。反过来，程序中的每条可行路径都不进入封锁城市，其转移也对应实际道路。

由于所有费用都非负，删除路线中的环不会增加费用，故一定存在一条简单的最优路线。返回起点的转移不会改善 d[1]，也不会影响这条最优简单路线的表示。

于是，原问题的最优值等于上述非负边权图上从 $1$ 到 $n$ 的最短路长度。Dijkstra 能正确求出该最短路，因此程序输出最小住宿费。

复杂度

多源 BFS 的时间复杂度为 $O(n+m)$，堆优化 Dijkstra 的时间复杂度为 $O((n+m)\log n)$，总空间复杂度为 $O(n+m)$。多组数据的总处理量按各组复杂度求和。

代码实现要点

• e 是原图邻接表，两轮搜索共用它；只有费用最短路阶段跳过封锁城市。
• d 在 BFS 阶段表示道路距离，在 Dijkstra 阶段重新初始化，改为表示住宿总费用，不能保留上一阶段的值。
• st 表示 Dijkstra 中距离已经确定的城市，不是 BFS 的访问标记。小根堆可能含同一城市的旧记录，弹出已确定城市时直接跳过。
• 危险边界包含距离恰好等于 $s$ 的城市。$s=0$ 时，没有未封锁城市会因该条件被标记为危险。
• 最优简单路线至多经过 $n-2$ 座中间城市，费用可能达到 $(n-2)Q$，超过 $32$ 位整数范围，因此 d 和堆中的费用使用 LL。
• 每组开始清空本组城市的邻接表，并重置标记、距离和队列指针。即使前一组城市较多，随后某组重新使用那些下标时，也会在读入新边前清空。
• 当前题面每组 $n\le10^5$，STD 的 N = 1e5 + 10 足够；总点数上限是多组之和，不要求把单组数组扩大到该总和。
• 题面保证终点可达，因此程序可以直接输出 d[n]，不需要另设无法到达时的输出。

参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;
const int N = 1e5 + 10;
vector<int> e[N];
int n, m, k, s, P, Q;
int q[N], g[N];   // 0普通, 1危险, 2封锁
LL d[N];
bool st[N];
LL dijkstra() {
	memset(st, 0, sizeof st);
	memset(d, 0x3f, sizeof d);
	d[1] = 0;
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	heap.push({0, 1});
	while (heap.size()) {
		int u = heap.top().second;
		heap.pop();
		if (st[u]) continue;
		st[u] = true;
		for (int j : e[u]) {
			if (g[j] == 2) continue;
			LL dist = d[u];
			if (j != n) {
				if (g[j] == 0) dist += P;
				else dist += Q;
			}
			if (dist < d[j]) {
				d[j] = dist;
				heap.push({d[j], j});
			}
		}
	}
	return d[n];
}
int main() {
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m >> k >> s >> P >> Q;
		for (int i = 1; i <= n; i ++) e[i].clear();
		memset(g, 0, sizeof g);
		memset(d, -1, sizeof d);
		int hh = 1, tt = 0;
		while (k --) {
			int x;
			cin >> x;
			g[x] = 2;
			d[x] = 0;
			q[ ++ tt] = x;  // 封锁城市入队
		}
		while (m --) {
			int a, b;
			cin >> a >> b;
			e[a].push_back(b);
			e[b].push_back(a);
		}
		while (hh <= tt) {
			int u = q[hh ++];
			for (int j : e[u]) {
				if (d[j] == -1) {
					d[j] = d[u] + 1;
					if (d[j] <= s) g[j] = 1;
					q[ ++ tt] = j;
				}
			}
		}
		cout << dijkstra() << "\n";
	}
	return 0;
}

T6 展品归位（shelf）

简要题意

有 $n$ 个固定格子，每格放一件展品，展品分为 $m$ 类。可以取出若干件，再将取出的展品任意放回这些空格；没有取出的展品必须留在原位置。希望最后同一类展品占据一段连续格子，各类别块的顺序可以任意选择，求最少取出的展品数量。

每组 $n\le10^5$、$m\le20$，每类至少出现一次。每个输入文件至多 $10$ 组，$\sum n\le2\times10^5$、$\sum2^m\le2^{21}$。

部分分路线

本题有 $20$ 个独立测试点，每点 $5$ 分。

测试点	附加限制	对应做法	本组分值
$1\sim4$	$n\le100,m\le9$	枚举类别顺序，逐格评价	$20$ 分
$5\sim8$	$m\le9$	枚举类别顺序，用前缀计数评价
$9\sim12$	$n\le100$	集合 DP，每次转移直接扫描该类别块
$13\sim20$	无	集合 DP 加前缀计数	$40$ 分

先记每一类展品的数量。枚举全部 $m!$ 种类别顺序后，目标排列已经确定，可以逐格统计原类别与目标类别不同的位置数。这个数量恰好是该目标所需取出的件数，证明见下一节。每种顺序花费 $O(n)$，总时间 $O(m!n)$，对应前 $20$ 分。

进一步预处理每类展品的前缀计数，就能在 $O(1)$ 时间求出一个目标类别块中的错位数。评价一种顺序只需计算 $m$ 个块，总时间降为 $O(nm+m!m)$，解决全部 $m\le9$ 的公开数据，累计 $40$ 分。

另一条自然的中间路线是使用下文的集合 DP，但计算一个类别块的代价时直接扫描该块，不做前缀计数。所有状态转移总共扫描 $n2^{m-1}$ 个位置，再加上集合长度计算，时间复杂度为 $O(n2^m)$。当 $m\le9$ 或 $n\le100$ 时可采用这一做法，覆盖前 $12$ 个测试点，累计 $60$ 分。这里的 $60$ 分来自同一套 DP 覆盖三组限制，无需在无法处理的输入上猜答案。

正解推导

1. 固定类别顺序后，答案等于错位格子数

设第 $i$ 类有 cnt[i] 件。最终每类都必须形成一个完整的连续块，因此只要确定类别块的先后顺序，各块长度和每个位置应有的类别就全部确定。

如果某个格子的原类别与目标类别不同，该格子的展品必须取出，所以取出数量至少是错位格子数。

反过来，只取出全部错位格子中的展品就一定足够。对任意类别，原来与目标匹配的展品可以保留；该类总件数不变，因此被取出的该类件数，恰好等于目标中尚需填入该类的空格数。将它们填回这些空格即可实现目标排列。

所以，对一个固定的类别块顺序，最少取出数量就是错位格子数。题目的计数对象是取出的展品件数：交换两件错位展品需要取出两件。空格也不会自动合并，不能把保留展品当作可以随意平移的子序列。

2. 用前缀计数求一个块的代价

STD 将输入类别减一，用 $0\sim m-1$ 表示类别，便于直接对应二进制位。

定义 sum[p][i] 为原排列前 $p$ 个位置中第 $i$ 类的数量，sum[0][i] = 0。如果第 $i$ 类在目标中占据区间 $[l,r]$，其长度必须为 cnt[i]。这个区间中已经是第 $i$ 类的数量为

$$\operatorname{sum}[r][i]-\operatorname{sum}[l-1][i].$$

所以该块中的错位数为

$$\operatorname{cnt}[i]-\bigl(\operatorname{sum}[r][i]-\operatorname{sum}[l-1][i]\bigr).$$

预处理前缀计数后，这个代价能在 $O(1)$ 时间计算。

3. 已经安排的类别集合决定右端位置

当 $m=20$ 时，枚举 $m!$ 种顺序仍然过慢。观察到：如果前面已经安排了类别集合 $S$，不论这些类别内部按什么顺序摆放，它们占据的总长度都是

$$r(S)=\sum_{i\in S}\operatorname{cnt}[i].$$

因此，后续类别从哪里开始摆，只取决于已经安排了哪些类别，不依赖它们的内部顺序。可以把所有具有相同集合的情况合并，保留其中最小代价。

定义 $f[S]$：让前 $r(S)$ 个格子由集合 $S$ 中各类别的完整块组成时，这些格子的最少错位数。$S$ 用一个 $m$ 位二进制整数表示，第 $i$ 位为 $1$ 表示第 $i$ 类已经安排。

初始化 $f[0]=0$，其余状态为无穷大。最终答案是

$$f[2^m-1].$$

4. 枚举当前状态的最后一类

STD 按状态编号从小到大枚举 $S$。对于每个状态，先扫描其中的类别，现场计算总长度 $r=r(S)$，没有另外维护一个集合长度数组。

接着枚举当前集合中的类别 $i$，假设它是最后一个类别块。记

$$t=S\setminus\{i\},\qquad l=r-\operatorname{cnt}[i]+1.$$

由于最后一块占据 $[l,r]$，前面的完整类别块恰好对应状态 $t$，转移为

$$f[S]=\min_{i\in S}\left\{ f[S\setminus\{i\}] +\operatorname{cnt}[i] -\bigl(\operatorname{sum}[r(S)][i]-\operatorname{sum}[r(S)-\operatorname{cnt}[i]][i]\bigr) \right\}.$$

对应代码中先计算 t = s - (1 << i) 和 l = r - cnt[i] + 1，再用 f[t] 更新 f[s]。因为枚举的第 $i$ 位原本就是 $1$，减去 1 << i 恰好删除这个类别，并且 $t<s$，按整数递增顺序计算不会访问尚未完成的状态。

正确性证明

先由固定顺序的结论可知：对任何合法目标排列，其最少取出数量等于各类别块错位数之和。

下面按集合大小证明 $f[S]$ 等于其定义的最小错位数。空集合不占格子，代价为 $0$，初始化正确。

考虑非空集合 $S$ 的一个最优排列，设最后一个类别为 $i$。这个类别块长度固定为 cnt[i]，且右端位置固定为 $r(S)$，所以它必然占据 $[r(S)-\operatorname{cnt}[i]+1,r(S)]$。删掉最后一块后，前缀是集合 $S\setminus\{i\}$ 的一个合法排列，其代价至少为 $f[S\setminus\{i\}]$。因此，该最优排列的代价不会小于转移式给出的最小值。

反过来，对于转移枚举的任意 $i\in S$，取一个达到 $f[S\setminus\{i\}]$ 的前缀排列，再在后面放入完整的第 $i$ 类块，就构成集合 $S$ 的一个合法排列。新增错位数正是前缀计数计算出的块代价，所以转移式中的每个候选值都能实现。

两方面结合，转移得到的 $f[S]$ 正好是最优值。归纳成立，全部类别的状态给出了合法目标排列中的最少错位数，也就是所求最少取出件数。

复杂度

统计数量和建立前缀计数需要 $O(nm)$ 时间。共有 $2^m$ 个集合，每个状态用一次 $O(m)$ 扫描计算 r，再用一次 $O(m)$ 扫描枚举最后的类别，总时间仍为 $O(m2^m)$。算法总时间复杂度为

$$O(nm+m2^m),$$

空间复杂度为 $O(nm+2^m)$。STD 使用固定上界数组，并在每组开始整体清零 sum、初始化 f，这会额外产生相应固定容量的初始化开销；不改变上述满规模复杂度。

代码实现要点

• cnt[i] 是第 $i$ 类的总数，决定目标块长度；sum[p][i] 的第一维是位置、第二维是类别，计算区间数量时不要写反。
• 读到第 p 个展品时，先把上一位置的各类前缀计数复制过来，再增加当前类别的计数。
• f[S] 统计错位格子数，不统计块数或交换次数，不能把结果除以二。
• 每个状态的 r 都从 $0$ 开始，累加当前集合包含的类别数量；它表示已经安排的展品总件数，不是集合中的类别数。
• l = r - cnt[i] + 1 是闭区间的左端点，前缀差必须使用 sum[l - 1][i]。每类至少有一件，所以被枚举的块非空。
• 每组重置 cnt、sum 和 f。答案不超过 $n$，计数和 DP 都使用 int 即可。
• 当前题面 $n\le10^5,m\le20$，N = 1e5 + 10、M = 20 和 f[1 << M] 与范围一致。类别减一后，实际访问的是 0 到 m - 1，不会访问第 20 列。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 20;
int n, m;
int a[N], cnt[M], sum[N][M];	// sum[i][j]表示1~i有几个j
int f[1 << M];	// f[s]表示状态为s的最小需要移动的展品数
int main() {
	int T;
	cin >> T;
	while (T --) {
		memset(cnt, 0, sizeof cnt);
		memset(sum, 0, sizeof sum);
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) {
			cin >> a[i];
			a[i] --;
			cnt[a[i]] ++;		// 统计每类展品的个数
			for (int j = 0; j < m; j ++) sum[i][j] += sum[i - 1][j];
			sum[i][a[i]] ++;
		}
		memset(f, 0x3f, sizeof f);
		f[0] = 0;
		for (int s = 1; s < 1 << m; s ++) {
			int r = 0;
			for (int i = 0; i < m; i ++)
				if (s >> i & 1) r += cnt[i]; // r求出已经安排的展品个数之和
			for (int i = 0; i < m; i ++)	// 枚举哪类展品排到最后
				if (s >> i & 1) {
					int t = s - (1 << i), l = r - cnt[i] + 1;
					// [l, r]区间就是第i类展品要安排进去的位置
					f[s] = min(f[s], f[t] + cnt[i] - (sum[r][i] - sum[l - 1][i]));
				}
		}
		cout << f[(1 << m) - 1] << "\n";
	}
	return 0;
}