补题链接

• T1 快递计分（score）
• T2 撤销账目（undo）
• T3 词语轮播（wordplay）
• T4 入场安排（admit）
• T5 蛋糕轮取（cake）
• T6 遗迹符文（runes）

讲题录屏

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

日期: 2026-09-26 19:02:52

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

密码：BHQI

T1 快递计分（score）

简要题意

输入投递包裹数 $P$ 和碰撞次数 $C$（$0\le P,C\le10000$）。每投递一个包裹加 $50$ 分，每碰撞一次扣 $10$ 分；仅当 $P>C$ 时额外加 $500$ 分。输出可以为负数的最终得分。

一句话题解

先计算 $50P-10C$，再根据 $P>C$ 是否成立决定是否加上 $500$。

完整题解

满分做法

设最终得分为 $ans$。先令 $ans=50P-10C$，如果 $P>C$，再令 $ans=ans+500$，最后输出 $ans$。

正确性说明

$P$ 个包裹共带来 $50P$ 分，$C$ 次碰撞共扣去 $10C$ 分，所以未计奖励的得分为 $50P-10C$。程序只在 $P>C$ 时加上题目规定的 $500$ 分，恰好与奖励条件一致。因此输出就是最终得分。

复杂度与边界

只进行固定次数的整数运算和一次判断，时间复杂度为 $O(1)$，空间复杂度为 $O(1)$。答案介于 $-100000$ 和 $500500$ 之间，使用 int 即可。

$P=C$ 时不能获得奖励；最终分数为负数时也必须原样输出，不能改成 $0$。

参考实现

#include<bits/stdc++.h>
using namespace std;
int main() {
	int p, c;
	cin >> p >> c;
	int ans = p * 50 - c * 10;
	if (p > c) ans += 500;
	cout << ans;
	return 0;
}

常见错误

• 把 > 写成 >=：例如 $P=C=1$ 时，正确答案为 $40$，不是 $540$。
• 忘记奖励：样例 1 会错误输出 $230$。
• 无条件加奖励：$P=0,C=1$ 时，正确答案为 $-10$，不是 $490$。
• 认为分数不能为负：$P=0,C=10$ 时，应输出 $-100$。

本题的任务就是正确执行全部计分规则，不应为简单的条件计算引入更复杂的数据结构。

T2 撤销账目（undo）

简要题意

输入 $n$ 次操作（$1\le n\le3\times10^5$），每次给出一个 $0$ 到 $100$ 的整数。正数追加到账目末尾，$0$ 删除最后一条尚未被撤销的记录，且保证删除时账目非空。输出最终所有记录的和；没有记录时输出 $0$。

一句话题解

用数组 stk 模拟栈，tt 表示栈顶位置；正数入栈，遇到 $0$ 就弹出栈顶，最后对栈内元素求和。

完整题解

满分：直接维护当前账目的末尾

不需要保留已经撤销的记录。使用数组 stk 模拟栈，tt 表示当前栈顶位置，也就是尚未撤销的记录条数。

• 初始 tt=0。代码中的 tt 是全局变量，会自动初始化为 $0$。
• 读到正数 $x$：执行 stk[++ tt] = x，将这条记录压入栈顶。
• 读到 $0$：执行 tt --，弹出最后一条尚未撤销的记录。

操作结束后，将 stk[1] 到 stk[tt] 相加，得到最终答案。这里不必清空被弹出位置的旧值：只要它不在有效区间 $[1,tt]$ 中，就不再属于当前账目；以后入栈时会直接覆盖它。

栈遵循“后进先出”，恰好对应题目要求的“撤销最后一条记录”。参考实现使用数组模拟栈，不依赖 STL 容器。

正确性证明

证明每次操作完成后，stk[1] 到 stk[tt] 都恰好是当前账目中的记录，且顺序一致。

开始时两者都为空，结论成立。若下一个数是正数 $x$，题目要求在末尾加入 $x$，程序也将 $x$ 压入栈顶；若下一个数是 $0$，题目要求删除最后一项，程序将 tt 减一，恰好让最后一项不再属于有效区间。题目保证删除前非空，因此 tt 不会变为负数。

由归纳法，所有操作结束时有效数组恰好是最终账目，对其求和即得到正确答案。

复杂度与实现边界

每次操作花费 $O(1)$ 时间，最后求和最多访问 $n$ 个数，因此总时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。数组容量开到 $3\times10^5+10$ 即可。

账目为空时，求和循环不执行，答案自然为 $0$。最大可能答案为 $100n\le3\times10^7$，使用 int 足够。

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int stk[N], tt;
int main() {
	int n, x;
	cin >> n;
	while (n --) {
		cin >> x;
		if (x) stk[ ++ tt] = x;
		else tt --;
	}
	int ans = 0;
	for (int i = 1; i <= tt; i ++) ans += stk[i];
	cout << ans;
	return 0;
}

另一种满分做法

也可以倒着读已经存下来的操作，用一个计数器记录“尚需抵消多少个正数”。遇到 $0$，计数器加一；遇到正数时，若计数器大于 $0$，就把该正数抵消并把计数器减一，否则把它加入答案。

每个 $0$ 从右向左配对到尚未匹配的正数，与从左向右撤销最后一条记录完全对应。这也是 $O(n)$ 完整算法，不能当成非预期错解。

常见误区与反例

• 认为 $0$ 表示清空整个账目：操作 $1,2,0$ 的结果应是 $1$，不是 $0$。
• 只删除原输入中紧邻 $0$ 的数：操作 $1,2,0,0$ 应得到 $0$，连续撤销时第二次要继续删除剩下的 $1$。
• 删除最早的记录：操作 $1,2,0$ 应留下 $1$，不是 $2$。
• 连续撤销时反复扣除最近读到的同一个正数：操作 $2,1,0,0,3$ 应得到 $3$，错误地重复扣除 $1$ 会得到 $4$；即使把负结果截到 $0$，这个反例也仍然成立。

赛时看到“最后加入且尚未删除的一项”，就可以尝试用数组的末尾指针来维护，而不是每次重新寻找。

T3 词语轮播（wordplay）

简要题意

每组给出 $K$ 个互不相同的小写英文词以及 $N$ 次首字母请求，$1\le K,N\le10^5$，词长为 $1\sim21$。每次在对应首字母的词中，先选此前使用次数最少的，再以字典序破同分，输出所选词。保证每次都有候选。至多 $10$ 组，同文件 $\sum K,\sum N$ 分别不超过 $2\times10^5$，不同组的次数独立。

一句话题解

按首字母分组、组内按字典序排序，再为每组建立队列；每次输出对应队首，并把它移到队尾。

完整题解

60 分：严格按规则扫描

测试点 $1\sim12$ 保证每组 $K,N\le499$。为每个词维护使用次数。处理请求时扫描全部词，忽略首字母不符的词；按“使用次数优先、字典序其次”比较，确定最优候选并把其次数加一。

这就是题目规则的直接实现，因此对所有合法输入都正确，但规模变大后时间不足。设最长词长为 $L\le21$，时间为 $O(KNL)$，空间为 $O(KL)$。小范围内至多十组，工作量可接受。

识别入口时，不必先猜出循环规律；看到词数和请求数都不超过 $499$，即可先把“选择最小二元组”正确模拟出来。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, cnt[N];
string a[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 ++) cin >> a[i], cnt[i] = 0;
		while (m --) {
			char ch;
			cin >> ch;
			int pos = 0;
			for (int i = 1; i <= n; i ++) {
				if (a[i][0] != ch) continue;
				if (!pos || cnt[i] < cnt[pos] || (cnt[i] == cnt[pos] && a[i] < a[pos])) pos = i;
			}
			cout << a[pos] << "\n";
			cnt[pos] ++;
		}
	}
	return 0;
}

从次数变化发现循环

不同首字母之间不会竞争同一个词：一次 a 请求只改变 a 开头词的次数。因此可以分别研究每种首字母。

固定一种首字母，把其词按字典序排列为 $w_1,w_2,\ldots,w_s$。最初每个词的次数都是 $0$，第一次必须选 $w_1$。随后 $w_1$ 的次数为 $1$，其余仍为 $0$，所以第二次选择 $w_2$。依此类推，前 $s$ 次请求恰好按顺序选择全部词一次。

此时所有次数又相等，都是 $1$。接下来重复同样的过程。因此无论其他首字母的请求怎样穿插，这种首字母都按

$$w_1,w_2,\ldots,w_s,w_1,w_2,\ldots$$

循环播报。

满分算法

参考实现用 vector<string> v[26] 保存分组后的词，用 queue<string> q[26] 维护各组的播报顺序。

1. 读入词 $s$，令 i = s[0] - 'a'，将其加入 v[i]。
2. 对每个 v[i] 按字典序排序，再依次把其中的词加入 q[i]。这样每组最初的队列顺序就是 $w_1,w_2,\ldots,w_s$。
3. 收到字符 $c$ 的请求时，令 i = c - 'a'，取出并输出 q[i].front()。
4. 将这个词从队首弹出，再压入同一个队列的队尾。

例如一组队列最初为 a,aaa,ab，输出 a 后变成 aaa,ab,a，输出 aaa 后变成 ab,a,aaa。每次都只移动队首，恰好实现按字典序循环播报。

输入保证每次请求都有候选，因此对应队列一定非空。不同首字母使用不同队列，各自独立轮转。

正确性证明

固定一个首字母。在完成 $q$ 个完整循环后，所有词都被选过 $q$ 次。再完成本轮前 $j$ 次选择时，前 $j$ 个词各被选过 $q+1$ 次，剩余词各被选过 $q$ 次。

若 $j<s$，次数最少的恰是剩余词，其中字典序最小者为 $w_{j+1}$。此时队列顺序为 $w_{j+1},\ldots,w_s,w_1,\ldots,w_j$，队首正是应选的词。若 $j=s$，所有次数重新相等，队列也恢复为 $w_1,w_2,\ldots,w_s$，下一次应选择 $w_1$。所以每次取队首、移到队尾，始终符合题目规则。

不同首字母的计数互不影响，合并各组的正确选择即可得到全部请求的正确输出。

复杂度与实现

设最长词长为 $L\le21$，第 $i$ 组包含 $K_i$ 个词。分组排序的比较次数为 $O(\sum_i K_i\log K_i)$，不超过 $O(K\log K)$；每次字符串比较最坏需要 $O(L)$ 时间。读入词、建立队列、处理请求时的字符串复制与输出也需要计入，因此单组总时间为 $O((K\log K+K+N)L)$。

v 和 q 各保存一份词，空间复杂度为 $O(KL)$。当词长上限视为常数时，可以简写为 $O(K\log K+K+N)$ 时间、$O(K)$ 空间。

每组开始时，代码对所有 v[i] 调用 clear()，并反复 pop() 清空所有 q[i]，使新一组从次数全为 $0$ 的状态重新开始。清空旧数据的工作量在所有组中合计为 $O(\sum K)$ 次容器操作。无需存储实际使用次数，也无需保留完整播报历史。

参考实现

#include<bits/stdc++.h>
using namespace std;
vector<string> v[26];
queue<string> q[26];
int main() {
	ios::sync_with_stdio(0);
	int T;
	cin >> T;
	while (T --) {
		for (int i = 0; i < 26; i ++) {
			v[i].clear();
			while (q[i].size()) q[i].pop();
		}
		int n, m;
		cin >> n >> m;
		while (n --) {
			string s;
			cin >> s;
			int i = s[0] - 'a';
			v[i].push_back(s);
		}
		for (int i = 0; i < 26; i ++) {
			sort(v[i].begin(), v[i].end());
			for (auto &s : v[i])
				q[i].push(s);
		}
		while (m --) {
			char c;
			cin >> c;
			int i = c - 'a';
			string s = q[i].front();
			cout << s << "\n";
			q[i].pop();
			q[i].push(s);
		}
	}
	return 0;
}

常见误区

• 按输入顺序轮播。 输入词 ab,a,aaa 时第一次应该选 a，不是 ab。
• 总选字典序最小词。 连续请求 a 时，前例依次是 a,aaa,ab，使用次数的优先级高于字典序。
• 所有字母共用轮播进度。 词 a,aa,b,bb，请求 a,b,a，正确输出 a,b,aa；中间的 b 不应改变 a 的进度。
• 用词长代替字典序。 aaa 比 ab 小，尽管更长。前缀规则只是字典序定义的一部分。
• 先按字母分组，但每次仍扫描该组所有次数。 这样仍然正确；然而所有词和请求都使用同一个首字母时，复杂度仍为 $O(KN)$，只能依赖小数据得分。

赛时建议

先用手工模拟写出同一个首字母连续出现几轮时的选择序列，再考虑其他字母穿插是否影响它。确认“每个字母独立轮转”后，用队列把队首移到队尾，就能直接实现这一规律。

T4 入场安排（admit）

简要题意

每组有编号 $1\sim G$ 的独占位置，$P$ 人按给定顺序到达，第 $i$ 人只能使用 $1\sim g_i$ 中的空位。首次无法安排时立刻停止，求最多能接纳的前缀人数。$1\le G,P\le10^5$，$1\le g_i\le G$；至多 $10$ 组，同文件 $\sum G,\sum P$ 分别不超过 $2\times10^5$，每组重新开始。

一句话题解

每次使用不超过当前上限的最大空闲编号，用 set 保存空位，并取 lower_bound(x + 1) 的前驱得到这个位置。

完整题解

为什么先用较大的位置

小编号能被更多人使用，大编号只能被上限足够大的人使用。因此当前有选择时，应保留小编号，把当前参与者放到其允许的最大空闲位置。

这条直觉需要交换证明，而不能只凭“看起来更灵活”就当作正确。

贪心的交换证明

假设之前的安排已经按贪心确定。当前参与者的最大可用位置为 $y$，考虑一个接纳前缀人数最多的方案。

如果该方案也把当前人放在 $y$，无需修改。否则它把当前人放在某个 $x<y$：

• 若 $y$ 在该方案中没有被使用，把当前人从 $x$ 移到 $y$ 即可。
• 若未来某人占据 $y$，则这个人的编号上限至少为 $y$，所以也一定能使用更小的 $x$。交换两人的位置，所有人仍满足要求，接纳人数不变。

所以总存在一个最优方案与当前贪心选择一致。逐人应用这个论证即可证明：贪心不会减少最大可接纳前缀的长度。一旦贪心找不到空位，也就不可能通过改变之前的选择让这一前缀可行。

40 分：向下扫描空位

测试点 $1\sim8$ 保证 $G,P\le2000$。设置布尔数组记录位置是否使用。每次从 $g_i$ 开始向下扫描，找到第一个空位就占用；如果扫到 $0$，记录入口已关闭。

该算法严格执行已经证明的贪心，因此逻辑上完整正确。最坏时间为 $O(GP)$，空间为 $O(G)$，适合这 $40$ 分。

输入含多组数据，入口关闭后仍要读完本组尚未到达者的全部上限，否则会把它们误读成下一组的信息。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
bool st[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		memset(st, 0, sizeof st);
		int ans = 0;
		bool stop = false;
		for (int i = 1; i <= m; i ++) {
			int x;
			cin >> x;
			if (stop) continue;
			while (x && st[x]) x --;
			if (!x) stop = true;
			else st[x] = true, ans ++;
		}
		cout << ans << "\n";
	}
	return 0;
}

满分：用有序集合维护空位

参考实现用 set<int> S 保存所有尚未使用的位置。set 中的编号有序，而且可以快速查找和删除，因此能够直接维护贪心需要的“最大可用位置”。

代码中的 n 对应位置数 $G$，m 对应到达人数 $P$。每组先把 $1\sim n$ 全部插入集合。对于当前读入的上限 $x$，执行：

auto it = S.lower_bound(x + 1);

lower_bound(x + 1) 返回第一个大于等于 $x+1$ 的元素。由于位置编号都是整数，这也就是第一个严格大于 $x$ 的元素。它前面的元素如果存在，就一定是不超过 $x$ 的最大空闲编号。

• 若 it == S.begin()，说明前面没有元素，集合中不存在任何不超过 $x$ 的空位，安排失败。
• 否则先执行 it --，就得到当前应使用的最大空位；令 ans 加一，再执行 S.erase(it)，将该位置从空闲集合中删除。

这里要区分 begin() 和 end()：it == S.end() 并不意味着失败。如果集合非空，这表示所有空位都小于 $x+1$，将迭代器减一就能取到集合中的最大空位。集合为空时 begin() == end()，会被第一种情况正确判为失败，不会执行非法的递减操作。

代码用 flag 表示入口是否仍开放。第一次失败时令 flag=false；之后继续读入剩余上限，但不再查询集合或增加答案。这样既遵守“首次失败就停止接纳”，也能正确处理后续测试组。

数据结构正确性

初始集合包含全部位置，恰好是所有空位。每次成功安排后，只删除被本次使用的位置，因此集合始终恰好保存尚未占用的位置。

lower_bound(x + 1) 把集合分为“不超过 $x$”和“严格大于 $x$”两部分。若前一部分非空，后退一步取得它的最后一个元素，恰好是不超过当前上限的最大空位；否则不存在合法位置，应立即停止接纳。

因此有序集合的每次操作都准确实现了前面已经证明的贪心。最终的 ans 就是最多能接纳的前缀人数。

复杂度与实现边界

初始化逐个插入 $G$ 个位置，耗时 $O(G\log(G+1))$。每个人至多进行一次有序集合查询及一次删除，耗时不超过 $O(\log(G+1))$；失败之后仍需读完输入。因此单组总时间复杂度为 $O((G+P)\log(G+1))$，空间复杂度为 $O(G)$。

每组的 S、flag 和 ans 都在本组循环内重新创建，不会继承上一组的占位情况。由 $x\le10^5$，查找时使用的 x + 1 不会超出 int 范围。

参考实现

#include<bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0);
	int T;
	cin >> T;
	while (T --) {
		int n, m;
		cin >> n >> m;
		set<int> S;
		for (int i = 1; i <= n; i ++) S.insert(i);
		
		bool flag = true;
		int ans = 0;
		while (m --) {
			int x;
			cin >> x;
			if (!flag) continue;
			auto it = S.lower_bound(x + 1);
			if (it == S.begin()) flag = false;
			else {
				it --;
				ans ++;
				S.erase(it);
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

常见错误与自然修补的边界

• 每次使用最小空位。 $G=3$，上限依次为 $3,2,1$，会把前两人放入位置 $1,2$ 后卡住；而安排为 $3,2,1$ 可以让三人都入场。
• 只挪动前一个人补救。 上例中第二人最多只能用位置 $2$，把他搬一次仍救不了第三人；真正需要改变的是第一人的安排。
• 失败时任选一个已安排的人搬一次。 上限依次为 $2,3,1$ 时，最小位置贪心先占 $1,2$，仅搬走一个占位者仍不能腾出 $1$；要先把第二人从 $2$ 搬到 $3$，再把第一人从 $1$ 搬到 $2$。完整增广路径可以正确求解，但“只搬一次”不完整。
• 跳过失败的人。 $G=4$、上限为 $1,1,4$ 时，正确答案是 $1$，不能跳过第二人后接纳第三人。
• 先排序上限。 $G=4$、上限为 $4,1,1$ 时答案是 $2$，排序成 $1,1,4$ 后变成 $1$，已改变题意。
• 仅缓存每个上限上次扫到的位置。 它逻辑上正确，但先占用一大段高位后，再用许多不同上限发起查询，会让不同缓存反复扫描同一段已占用区间，仍可能是平方复杂度。

赛时如何推进

先证明位置分配方向，再用数组扫描拿到 $40$ 分。接着把“从上限向下寻找第一个空位”转化为“查询不超过上限的最大空闲编号”，便能想到用有序集合维护所有空位。关键在于先确定应选哪个位置，再用数据结构加速查找。

T5 蛋糕轮取（cake）

简要题意

给出环上 $N$ 块大小互异的蛋糕，大小为 $A_i$。甲先任取一块，此后乙、甲轮流取与已取区域相邻的蛋糕；乙始终取较大者，甲可任选。求甲最终取得的总大小的最大值。$N\le2000$，$A_i\le10^9$，输出需要使用 64 位整数。

一句话题解

将环展开为两倍长序列，令 $f[i][j]$ 表示剩下 $[i,j]$ 时甲已经取得的最大收益，按区间长度递减，从两个长度多一的前驱转移，最后单独处理剩下的一块。

完整题解

15 分：直接搜索

枚举第一块取哪一块。取走这块后，剩余蛋糕构成一段连续区间，以后每次只能取区间的一端。

轮到甲时，分别搜索取左端、右端，取较优结果；轮到乙时，严格按题意拿走较大的一端，不需要分支。空区间返回 $0$。

只有甲的回合会产生两个分支，因此时间复杂度可界为 $O(N2^{\lceil N/2\rceil})$，递归栈为 $O(N)$；$N\le20$ 时很容易运行。赛时先抓住“可取位置始终只有两端”，就能迅速写出这档代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4010;
int n, a[N];
LL dfs(int l, int r, int turn) {
	if (l > r) return 0;
	if (!turn) return max(a[l] + dfs(l + 1, r, 1), a[r] + dfs(l, r - 1, 1));
	if (a[l] > a[r]) return dfs(l + 1, r, 0);
	return dfs(l, r - 1, 0);
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i], a[i + n] = a[i];
	LL ans = 0;
	for (int i = 1; i <= n; i ++) ans = max(ans, a[i] + dfs(i + 1, i + n - 1, 1));
	cout << ans << "\n";
	return 0;
}

60 分：对每个首选位置分别做区间 DP

固定第一块后，剩下长度为 $N-1$ 的线性序列。相同剩余区间会在搜索中反复出现，可以用记忆化或按长度递增计算，每个首选位置用 $O(N^2)$ 时间。

这一档参考代码中的 $f[l][r]$ 表示：固定首选位置 $s$ 后，还剩下 $A_{s+l},\ldots,A_{s+r}$ 时，甲在后续过程中最多还能取得多少。它依赖更短区间，因此按长度递增计算；空区间取 $0$。下文满分实现会改用“已经取得的收益”这一状态定义。

一共枚举 $N$ 个首选位置，总时间 $O(N^3)$、空间 $O(N^2)$，适合 $N\le300$，可获得前 $12$ 个测试点的 $60$ 分。这里的低效之处不是转移，而是不同首选位置之间又重复算了同一区间。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2010;
int n, a[N * 2];
LL f[N][N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i], a[i + n] = a[i];
	LL ans = 0;
	for (int s = 1; s <= n; s ++) {
		for (int len = 1; len < n; len ++)
			for (int l = 1; l + len <= n; l ++) {
				int r = l + len - 1;
				if ((n - len) % 2 == 0)
					f[l][r] = max(a[s + l] + f[l + 1][r], a[s + r] + f[l][r - 1]);
				else if (a[s + l] > a[s + r]) f[l][r] = f[l + 1][r];
				else f[l][r] = f[l][r - 1];
			}
		ans = max(ans, a[s] + f[1][n - 1]);
	}
	cout << ans << "\n";
	return 0;
}

满分：按照取块顺序缩短剩余区间

以下沿用 cake.cpp 中的变量：n 表示蛋糕块数，w[i] 表示第 $i$ 块的大小。代码注释中的“小明”对应题意中的甲。

1. 复制数组，并把所有首次取块位置一起考虑。

令 $w_{i+n}=w_i$，得到长度为 $2n$ 的数组。环上任意一段连续剩余蛋糕，都能表示成这个数组中的一个区间。

任意长度为 $n$ 的窗口 $[i,i+n-1]$ 都恰好包含原环上的全部蛋糕，可以将它看作尚未取块时的一种展开方式。对所有这些窗口同时建立初始状态，就能覆盖所有首次选择：若第一块要取原环上的第 $s$ 块，就从窗口 $[s,s+n-1]$ 的左端取走它。后续剩下 $[s+1,s+n-1]$，与实际过程完全一致。

不同窗口可能表示同一种初始局面，这只会重复考虑合法选择，不会改变最大值。

2. 状态记录已经得到的收益。

定义

$$f[i][j]=\text{恰好剩下区间 }[i,j]\text{ 时，甲此前已经取得的总大小的最大值。}$$

这里尚未计算 $[i,j]$ 中任何一块的收益。对于同一个剩余区间，已经取走了多少块、下一次轮到谁都已确定，后续合法行动也只与区间端点有关，因此只需保留此前收益最大的方案。

初始时一块都没有取，故令所有长度为 $n$ 的窗口满足

$$f[i][i+n-1]=0\qquad(1\le i\le n+1).$$

其他状态初始化为负无穷，表示尚不可达。这与代码中的 memset(f, -0x3f, sizeof f) 对应，不能把整张表初始化为 $0$，否则不可达的局面也会被当作合法起点。

3. 按“刚刚取走的人”推导转移。

设当前目标区间为 $[i,j]$，长度 $len=j-i+1$。到达这个状态时，已经取走了 $n-len$ 块。

甲先取第一块，所以奇数次取块由甲执行，偶数次取块由乙执行。因此：

已取块数	刚刚取走一块的人	代码条件
$n-len$ 为奇数	甲	len % 2 != n % 2
$n-len$ 为偶数	乙	len % 2 == n % 2

这里判断的是产生当前状态的上一步由谁执行。当前区间形成后，下一次轮到的人恰好相反。

若刚刚由甲取走一块，当前状态只有两种来源：

• 原先剩下 $[i-1,j]$，甲取走左端 $w_{i-1}$。
• 原先剩下 $[i,j+1]$，甲取走右端 $w_{j+1}$。

甲可以自由选择，因此

$$f[i][j]=\max\left\{f[i-1][j]+w_{i-1},\ f[i][j+1]+w_{j+1}\right\}.$$

若刚刚由乙取走一块，同样检查两个前驱，但必须验证乙在那个前驱局面中确实会取走相应的一端：

• 从 $[i-1,j]$ 转移过来时，乙面对的两端是 $w_{i-1}$ 和 $w_j$。只有 $w_{i-1}>w_j$，乙才会取走左端，从而得到 $[i,j]$：

  $$f[i][j]=\max\{f[i][j],f[i-1][j]\}.$$

• 从 $[i,j+1]$ 转移过来时，乙面对的两端是 $w_i$ 和 $w_{j+1}$。只有 $w_{j+1}>w_i$，乙才会取走右端，从而得到 $[i,j]$：

  $$f[i][j]=\max\{f[i][j],f[i][j+1]\}.$$

乙取得的蛋糕不计入甲的收益，所以这两条转移都不加蛋糕大小。两个条件检查的是两个不同的前驱局面，可能同时成立，必须分别使用 if，不能写成互斥的 if...else。

另外，应比较前驱区间的两端，不能比较当前区间的 $w_i$ 与 $w_j$。当前区间已经是取完之后的局面，刚刚被取走的蛋糕位于它外面。

4. 从长区间转移到短区间。

每个 $f[i][j]$ 都依赖长度为 $len+1$ 的两个前驱。因此从已经初始化的长度 $n$ 出发，依次计算

$$len=n-1,n-2,\ldots,1.$$

代码虽然通过检查前驱来计算当前格子，但整个 DP 仍沿实际取块过程推进：取走一块后，剩余区间缩短，累计收益增加或保持不变。

5. 剩下最后一块时统一结算。

计算结束后，$f[i][i]$ 只统计前 $n-1$ 次取块中甲取得的收益，位置 $i$ 的最后一块还没有被取走。

• $n$ 为奇数时，第 $n$ 次轮到甲，须再加上 $w_i$。
• $n$ 为偶数时，第 $n$ 次轮到乙，甲的收益保持不变。

所以答案为

$$\max_{1\le i\le 2n} \begin{cases} f[i][i]+w_i,&n\text{ 为奇数},\\ f[i][i],&n\text{ 为偶数}. \end{cases}$$

枚举到 $2n$ 是为了直接覆盖展开数组中的全部单点状态；其中的重复表示不会影响取最大值。

正确性证明

状态可以完整描述局面。 第一次取块后，已取部分始终连续，剩余部分也始终是一段连续区间。之后每次恰好取走这个区间的一端。对于同一个剩余区间，已取块数相同，行动者相同，后续可取蛋糕相同；乙的选择只取决于两端大小。因此，保留甲已经取得的最大收益足以完成后续决策。

初始化覆盖所有首次选择。 任意长度为 $n$ 的初始窗口都表示原环的全部蛋糕，收益为 $0$。任意首次选择 $s$ 都可表示成从 $[s,s+n-1]$ 左端取块，故初始化没有遗漏。反过来，从任一初始窗口的端点首次取块，也都是题目允许的选择。

转移恰好枚举所有合法前驱。 按区间长度递减归纳。假设长度为 $len+1$ 的状态已经正确，对任意长度为 $len$ 的目标区间 $[i,j]$，上一步只能从 $[i-1,j]$ 取走左端，或从 $[i,j+1]$ 取走右端。若上一步由甲执行，两种选择都合法，分别增加所取蛋糕的大小；若由乙执行，只有对应蛋糕是前驱中较大的一端时才能转移，且甲的收益不增加。程序恰好执行这些转移并取最大值，所以 $f[i][j]$ 正确。

最后，任意完整方案在取走前 $n-1$ 块后都对应某个单点区间。根据 $n$ 的奇偶处理最后一块，就得到该状态对应的完整收益；对所有单点取最大值，便得到全局最优答案。

复杂度与实现边界

展开后的区间状态数为 $O(n^2)$，每个状态检查两个前驱，耗时 $O(1)$，因此时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。

f[4010][4010] 使用 long long，约占 $128.6$ MB，即 $122.7$ MiB，符合 $256$ MiB 限制。甲最多取得 $\lceil n/2\rceil$ 块，每块不超过 $10^9$，答案不超过 $10^{12}$，DP 和答案必须使用 long long。

几个与这份代码直接相关的边界：

• 数组外侧是不可达前驱。 当 $i=1$ 或 $j=2n$ 时，代码会访问 f[0][j] 或 f[i][2*n+1]。这些位置位于已分配数组内，始终保持极小值，不代表实际局面。即使在甲的转移中加上一个蛋糕大小，也仍远小于合法收益，不会影响答案。全局数组中 w[0] 和 w[2*n+1] 默认为 $0$。
• 严格大于成立的前提是蛋糕大小互异。 DP 中乙的每次转移都从长度至少为 $2$、至多为 $n$ 的前驱区间取块，两端对应不同的原始蛋糕，因此不会相等。复制数组虽会产生相同值，但间隔为 $n$ 的两个副本不会同时成为这些前驱区间的两端。
• 仅计算到长度 $1$，不继续套用转移计算空区间。 剩一块时左右两端是同一块，严格大于的比较不再适用；代码直接按总块数奇偶结算最后一块，避免了这一问题。
• $n=1$ 时也成立。 长度递减循环不执行，两个长度为 $1$ 的初始窗口收益均为 $0$，最后加上唯一一块的大小，得到正确答案。

常见误区

• 把 $f[i][j]$ 解释成后续还能取得的收益。 这会让状态含义与本代码的初始化、转移方向、最后一块结算全部错位。
• 根据当前长度判断下一位行动者，却用于本代码的前驱转移。 len % 2 != n % 2 表示刚刚由甲取走了一块，此时下一次其实轮到乙。
• 乙的转移比较错端点。 从左侧前驱过来时比较 $w_{i-1}$ 和 $w_j$，从右侧前驱过来时比较 $w_{j+1}$ 和 $w_i$。
• 把乙的两个 if 合并成 if...else。 它们检验不同前驱，两种来源都可能合法，需要共同参与取最大值。
• 把乙当成会全局优化的对手。 乙只取当前较大端，不会为了减少甲的总收益而选择较小端。
• 甲也始终取较大端，或首次只取全局最大块。 当前取得的大小会影响以后暴露的两端，局部贪心不能代替区间 DP。
• 漏掉最后一块，或无论奇偶都加上最后一块。 $f[i][i]$ 没有统计位置 $i$ 的收益，只有 $n$ 为奇数时这块才属于甲。

参考实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4010;
int w[N], n;
LL f[N][N]; // 最后剩下[l, r]的最大价值
int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> w[i], w[n + i] = w[i];
	
	memset(f, -0x3f, sizeof f);
	for (int i = 1; i + n - 1 <= 2 * n; i ++) f[i][i + n - 1] = 0;
	for (int len = n - 1; len >= 1; len --) {
		for (int i = 1; i + len - 1 <= 2 * n; i ++) {
			int j = i + len - 1;
			if (len % 2 != n % 2) { // 小明取走了一块
				f[i][j] = max(f[i - 1][j] + w[i - 1], f[i][j + 1] + w[j + 1]);
			} else {
				if (w[i - 1] > w[j]) f[i][j] = max(f[i][j], f[i - 1][j]);
				if (w[j + 1] > w[i]) f[i][j] = max(f[i][j], f[i][j + 1]);
			}
		}
	}
	LL ans = 0;
	for (int i = 1; i <= 2 * n; i ++) {
		LL t = f[i][i];
		if (n % 2) t += w[i];
		ans = max(ans, t);
	}
	cout << ans;
	return 0;
}

T6 遗迹符文（runes）

简要题意

给定 $n\le10^5$ 个点、$m\le2\times10^5$ 条正权无向边，以及 $k\le7$ 块符文石。第 $i$ 块在 $s_i$，只能到该点激活，激活后开启代价为 $c_i$ 的双向边 $(a_i,b_i)$。符文按激活顺序入栈，只有栈顶的门生效；任意位置可免费弹栈并恢复上一块，每块符文一生只能激活一次，弹出后不能再用。每文件输入 $Q\le10$ 组，$\sum n\le2\times10^5$、$\sum m\le4\times10^5$；每组求从 $S$ 到 $T$ 的最小代价，不可达输出 $-1$。所有边和门的代价为不超过 $10^9$ 的正整数，图可以不连通，允许重边和 $S=T$。

一句话题解

先求至多 $23$ 个关键点之间的普通最短路，再以“当前位置、曾激活集合、当前有序栈”为状态运行 Dijkstra。

完整题解

从直接做法获得部分分

$k=0$ 时没有符文，直接在原图跑 Dijkstra，即可处理测试点 $5\sim8$ 的 20 分。

$k=1$ 时，只需区分未激活、已激活、已撤销三种状态，在原图上分层跑最短路；或者在普通最短路中枚举传送门的使用方向。设 $d(u,v)$ 为不使用任何传送门时的距离，则答案为

$$\min\{d(S,T),\ d(S,s_1)+d(s_1,a_1)+c_1+d(b_1,T),\ d(S,s_1)+d(s_1,b_1)+c_1+d(a_1,T)\}.$$

忽略含不可达距离的项即可。不能漏掉先去 $s_1$ 激活的路程。所有代价为正，在仅允许这一道门时，最优路线不需要反复使用它；撤销也不会带来更小代价，因为不开门从不影响普通通道。结合 $k=0$ 可处理 40 分。对于一般 $k$，自然的延伸是分别尝试每一块符文，并取“最多激活一块”的最好结果；仍不能处理必须组合多块符文的情况。

一般地，直接把完整符文状态和原图位置组合即可得到正确的暴力。小图档的状态数很少，这也给出另一组容易获得的 20 分。将小图暴力与单符文做法结合，可覆盖前 12 个点的 60 分。不能把各档限制机械看成互不相干的算法分数。

80 分路线：保留原图的完整状态最短路

直接保留原图所有位置，不压缩普通行走，在下文定义的完整符文状态上搜索。$k\le3$ 时最多只有 $38$ 种符文状态，因此组合图最多有 $38n$ 个状态；普通边和操作均按需生成，不必显式建立所有边。这样还可以处理测试点 $13\sim16$，累计 80 分。

这份程序没有主动拒绝 $k>3$ 的输入，算法在逻辑上对全部数据正确，但 $k=7$ 时最坏可能需要 $37200n$ 个状态，无法满足本场资源限制。全范围必须减少位置维度，而不是简单扩大数组。

以下参考代码用全局哈希表只保存实际到达的原图状态，适合暴力及部分分，不作为满分空间保证。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1e5 + 10;
vector<PII> e[N];
int n, m, k, S, T, s[7], a[7], b[7], c[7];
unordered_map<LL, LL> d;
LL encode(int u, int used, int code) {
	return ((LL) used * (1 << 21) + code) * n + u - 1;
}
void solve() {
	for (int i = 1; i <= n; i ++) e[i].clear();
	d.clear();
	cin >> n >> m >> k >> S >> T;
	for (int i = 1; i <= m; i ++) {
		int u, v, w;
		cin >> u >> v >> w;
		e[u].push_back({v, w});
		e[v].push_back({u, w});
	}
	for (int i = 0; i < k; i ++) cin >> s[i] >> a[i] >> b[i] >> c[i];
	priority_queue<PLL, vector<PLL>, greater<PLL> > q;
	LL start = encode(S, 0, 0);
	d[start] = 0;
	q.push({0, start});
	while (!q.empty()) {
		LL dis = q.top().first, key = q.top().second;
		q.pop();
		if (dis != d[key]) continue;
		int u = key % n + 1, code = key / n % (1 << 21), used = key / n / (1 << 21);
		if (u == T) {
			cout << dis << "\n";
			return;
		}
		auto relax = [&](int v, int mask, int stack, int w) {
			LL next = encode(v, mask, stack);
			auto it = d.find(next);
			if (it == d.end() || it->second > dis + w) {
				d[next] = dis + w;
				q.push({dis + w, next});
			}
		};
		for (auto it : e[u]) relax(it.first, used, code, it.second);
		for (int i = 0; i < k; i ++)
			if (s[i] == u && !(used >> i & 1)) relax(u, used | (1 << i), code * 8 + i + 1, 0);
		if (code) {
			relax(u, used, code / 8, 0);
			int top = code % 8 - 1;
			if (u == a[top]) relax(b[top], used, code, c[top]);
			if (u == b[top]) relax(a[top], used, code, c[top]);
		}
	}
	cout << "-1\n";
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int Q;
	cin >> Q;
	while (Q --) solve();
	return 0;
}

下面通过压缩普通行走处理全范围。

一、把普通行走压缩到关键点之间

需要保留的位置包括：

• 起点 $S$ 和终点 $T$；
• 每块符文的激活位置 $s_i$；
• 每道传送门的两个端点 $a_i,b_i$。

将这些位置去重，得到 $p\le 3k+2\le23$ 个关键点。在不加入任何传送门的普通图上，从每个关键点各跑一次 Dijkstra，求出普通最短路矩阵 $g$。其中 $g[u][v]$ 表示两个关键点之间只走普通通道的最短距离，不可达时为 inf。

此后，走普通通道只需考虑从一个关键点移动到另一个关键点，代价为 $g[u][v]$。普通最短路可能经过其他符文石，但经过符文石不强制激活，因此可以直接使用这条距离；如果需要在途中激活，就在相应关键点处分成两段。

撤销虽然可以发生在任意房间，但不会影响普通通道。对一段不激活、不传送的普通行走，可以把途中发生的撤销统一移到这段行走的末尾，费用不变，下一次关键操作开始前的栈也不变。因此，压缩后只在关键点执行撤销，仍能覆盖最优方案。

代码中的 add_key(int &x) 同时完成去重与编号转换：key[v] 保存关键点 $v$ 在原图中的编号，而传入的 S、T、s[i]、a[i]、b[i] 会被改写为 $0\sim p-1$ 的关键点编号。原图邻接表仍使用 $1\sim n$ 的原图编号；dijkstra(src) 从原图点 key[src] 出发，最后写入 g[src][i]。

二、状态要区分“用过哪些符文”和“栈里还有哪些符文”

设 $M$ 为曾经激活过的符文集合，$\sigma$ 为当前还没有撤销的有序栈，栈中顺序按栈底到栈顶记录。

• 激活符文 $i$ 时，必须满足 $i\notin M$，然后把它加入 $M$ 并压入栈。
• 使用哪一道传送门，由当前栈顶决定。
• 撤销时只弹出栈顶，不能把这块符文从 $M$ 中删除，因为它以后不能再次激活。

例如，先激活 $0$、再激活 $1$、然后撤销 $1$，此时当前栈是 $[0]$，而曾激活集合是 $\{0,1\}$。这与“只激活过 $0$”具有相同的当前栈，却有不同的后续可用符文。

只记录集合无法知道撤销后恢复哪道门；只记录栈无法判断栈外的符文是否已经用过；只记录集合和栈顶也无法还原更深的栈顺序。因此完整符文状态是 $(M,\sigma)$。

代码用两层编号保存这部分信息：先给每一种有序栈编号，再给每个合法的“曾激活集合 + 有序栈”组合编号。

三、八进制编码并枚举所有有序栈

源码中符文编号为 $0\sim k-1$，编码时用 $i+1$ 表示符文 $i$。这样每一位都在 $1\sim7$ 之间，可以把整个栈视为一个八进制数，空栈编码为 $0$。

• 压入符文 $i$：code * 8 + i + 1。
• 弹出栈顶：code / 8。
• 取得栈顶符文编号：code % 8 - 1。

例如，从栈底到栈顶为 $[0,2,1]$ 的栈，编码就是 $(132)_8$。最后一位为 $2$，对应栈顶符文 $1$。空栈的 code 为 $0$，上述取栈顶表达式得到 $-1$，正好表示没有生效的传送门。

每块符文最多入栈一次，所以栈内元素互不相同。build_stack(code, mask, fa) 从空栈开始递归，枚举每一个当前不在栈中的符文，并把它压入栈。这里参数 mask 表示当前栈包含的符文集合，尚未涉及曾经用过的集合。

对于枚举得到的栈编号 j：

变量	含义
codes[j]	该栈的八进制编码
masks[j]	当前栈内的符文集合
pre[j]	弹出一个栈顶后得到的栈编号
index_code[code]	根据编码查到栈编号
sn	已枚举的有序栈总数

递归先给当前栈编号，再枚举压栈后的子栈，因此 fa 正好是弹栈后的栈编号。空栈的 pre[0] 虽设为 $0$，但后面会单独禁止对空栈执行弹栈。

长度为 $j$ 的栈有 $P(k,j)=k!/(k-j)!$ 种，所以有序栈数量为

$$R(k)=\sum_{j=0}^{k}P(k,j).$$

$k=7$ 时 $R(7)=13700$，源码中的 A = 13710 足够保存全部栈。编码最多有 $7$ 个八进制位，始终小于 $8^7=2^{21}$，因此 index_code[1 << 21] 可以直接按编码查询。

四、枚举合法符文状态，并预处理压栈、弹栈后的编号

枚举曾激活集合 mask 和栈编号 j。它们组成合法状态的必要条件是：栈里的每块符文都已经激活过，即

$$\operatorname{masks}[j]\subseteq\operatorname{mask}.$$

代码用 (mask & masks[j]) == masks[j] 检查这一条件，并建立映射：

变量	含义
id[mask][j]	组合状态 $(\text{mask},j)$ 的编号；不合法时为 $-1$
used[u]	组合状态 u 中曾经激活过的符文集合
stack_id[u]	组合状态 u 对应的栈编号
pop_id[u]	撤销一次后的组合状态编号；空栈时为 $-1$
push_id[u][i]	首次激活符文 $i$ 后的组合状态编号；已经用过时为 $-1$
cnt	合法组合状态总数

masks[stack_id[u]] 与 used[u] 不能混用：前者只包含当前栈内的符文，后者还包含已经撤销的符文。

设当前状态的曾激活集合为 mask，栈编号为 j。

撤销时，集合不变、栈变成父栈，所以下一个组合状态是

id[mask][pre[j]]

但如果当前栈为空，就将 pop_id[u] 设为 $-1$，表示禁止这次操作。

激活符文 $i$ 时，如果 mask 中已有第 $i$ 位，就将 push_id[u][i] 设为 $-1$。否则，新集合为 mask | (1 << i)，新栈编码为 codes[j] * 8 + i + 1，对应状态为

id[mask | (1 << i)][index_code[codes[j] * 8 + i + 1]]

由于当前栈包含于 mask，$i\notin\text{mask}$ 也保证了 $i$ 不在当前栈中，所以压栈后的编码一定已被 build_stack 枚举。这里预处理的只是符文状态变化；执行激活时，还需要另外检查当前位置是否为 s[i]。

若固定一个长度为 $j$ 的有序栈，则栈外每块符文有“尚未激活”和“已经激活并撤销”两种可能。因此合法符文状态总数为

$$H(k)=\sum_{j=0}^{k}P(k,j)2^{k-j}.$$

$H(0)=1$，$H(1)=3$，$H(3)=38$，$H(7)=37200$。源码中的 B = 37210 足够保存全部组合状态。枚举出的状态未必都能在当前图上到达，最短路会自然保留其中不可达状态的无穷大距离。

枚举时首先处理 mask = 0，此时唯一合法的栈是空栈，所以组合状态 $0$ 恰好表示“没有激活过符文，当前栈为空”。这些状态编号只用于数组寻址，最短路的处理顺序由优先队列中的距离决定。

五、在“符文状态 × 关键点”上运行 Dijkstra

定义

$$f[u][v]=\text{到达关键点 }v\text{，且符文组合状态为 }u\text{ 的最小代价}.$$

初始时没有激活过任何符文，位置为起点，因此设置 f[0][S] = 0，其余值为 inf。

从状态 (u, v) 考虑四类转移：

操作	条件	后继状态	增加代价
普通行走	g[v][i] != inf	(u, i)	g[v][i]
撤销栈顶	pop_id[u] != -1	(pop_id[u], v)	$0$
激活符文 $i$	v == s[i] 且 push_id[u][i] != -1	(push_id[u][i], v)
使用栈顶传送门	栈顶为 $i$，且位于 a[i] 或 b[i]	符文状态不变，移动到门的另一端	c[i]

普通行走不改变符文状态；撤销和激活都不改变位置；传送也不消耗符文，传送后这道门仍然生效。

代码将 (u, v) 合并成整数 u * p + v 放入优先队列。取出时，整除 p 得到符文状态编号 u，对 p 取模得到关键点编号 v。初始符文状态为 $0$，所以初始队列元素直接使用 S 作为状态编码。

relax(x, y, w) 表示尝试把 (x, y) 的距离更新为 dist + w。如果 x == -1，说明压栈或弹栈操作不合法，直接忽略。相同状态可能多次入队，所以出堆后先用 f[u][v] != dist 过滤过期项。

压栈、弹栈的代价虽然为 $0$，但全部边权仍然非负，可以运行 Dijkstra。第一次取出位置为 T 的有效状态时即可输出答案，因为它的距离已经确定，并且不大于所有尚未处理状态的距离。到达终点时不要求栈为空，也不要求用完符文。队列耗尽仍未到达终点时，输出 $-1$。

六、正确性证明

1. 压缩普通行走保持最优答案。

把原问题的合法路线按激活、传送等关键事件拆分。每段普通行走的两端都是关键点，其中的撤销可以移到该段末尾，普通行走可以替换为 $g$ 中记录的最短路，均不会增加费用。因此原问题的任意合法方案，都能对应到一个不更贵的压缩状态图方案。

反过来，每条压缩普通边都对应原图中的一条实际路径；激活、撤销和传送转移也都能在原图中执行。因此压缩状态图的任意路线，都能还原为同代价的合法原路线。两个方向结合，压缩前后的最优答案相同。

2. 符文状态包含决定后续操作的全部信息。

used[u] 决定哪些符文还可以首次激活，stack_id[u] 记录完整栈顺序，决定当前生效的门和撤销后恢复的门。与当前位置一起，它们足以确定所有后续合法操作。预处理的压栈、弹栈转移保持“当前栈包含于曾激活集合”的性质，并且不会重复激活符文。

3. Dijkstra 求得所建状态图的最短路。

四类转移覆盖所有合法行动，且转移代价均非负。Dijkstra 因而能求出起始状态到各状态的最短距离。目标允许任何符文状态，只要位置为 $T$；首次出堆的有效终点状态正是这些目标中的最小距离。结合前两点，程序输出的就是原问题的最优答案。

七、复杂度与实现细节

设 $R=R(k)$、$H=H(k)$，关键点数为 $p\le3k+2$。以下复杂度按单组数据计算。

• 普通图上运行 $p$ 次 Dijkstra，时间为 $O\bigl(p(n+m)\log(n+m)\bigr)$。
• 枚举合法组合并预处理后继，时间为 $O(2^kR+Hk)$；源码还会整表清空固定容量的 id 数组。
• 压缩状态图至多有 $Hp$ 个点，每次出堆扫描 $p$ 个普通移动目标及 $k$ 块符文，再检查撤销和传送。状态图 Dijkstra 的时间上界为 $O\bigl(Hp(p+k)\log(Hp)\bigr)$。

$k=7$ 时，符文状态为 $37200$ 个，完整状态最多为 $37200\times23=855600$ 个。代码按需生成转移，无需显式存储整张状态图的所有边。

距离表需要 $O(Hp)$ 空间，符文后继需要 $O(Hk)$ 空间。普通图与原图距离数组需要 $O(n+m)$ 空间；栈编码查表和组合编号表另外占用 index_code[1 << 21]、id[128][A]。源码中的这些状态数组按 $k=7$ 的上限静态分配。

还要计入优先队列：该实现采用“距离改善后重新入队”的方式，队列中可能同时保留多个指向同一状态的条目。组合状态图的堆空间最坏可达 $O\bigl(Hp(p+k)\bigr)$，不能只按距离表大小估算总内存。包含映射和堆的保守空间上界为

$$O\left(n+m+2^{21}+128A+Hk+Hp(p+k)\right),$$

其中 $A=13710$ 为源码中有序栈数组的容量，状态相关项按最大规模计算。

距离必须使用 long long。每块符文最多激活、撤销各一次，因此一条最优路线最多分为 $2k+1$ 段栈配置不变的行走。每段只使用普通图及至多一道生效的门，可取不重复顶点的最短路，费用不超过 $(n-1)10^9$。所以有限最优值不超过 $(2k+1)(n-1)10^9<1.5\times10^{15}$，源码中的 inf = 4e18 足够大；不可达的 g 不参与松弛。

多组数据时，solve() 在读取新一组的 n 之前，先按上一组的 n 清空邻接表，然后重置 p、sn、cnt，重建编号并初始化本组使用的距离。index_code 无需整表清零，因为每次实际查询的合法栈编码，都已由本组的 build_stack 重新写入。

参考实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;
const int N = 1e5 + 10, K = 23, A = 13710, B = 37210;
const LL inf = 4e18;
vector<PII> e[N];
int n, m, k, S, T, p, key[K], s[7], a[7], b[7], c[7];
int codes[A], masks[A], pre[A], index_code[1 << 21], sn;
int id[128][A], stack_id[B], used[B], pop_id[B], push_id[B][7], cnt;
LL d[N], g[K][K], f[B][K];
void add_key(int &x) {
	for (int i = 0; i < p; i ++)
		if (key[i] == x) {
			x = i;
			return;
		}
	key[p] = x;
	x = p ++;
}
void build_stack(int code, int mask, int fa) {
	int u = sn ++;
	codes[u] = code, masks[u] = mask, pre[u] = fa;
	index_code[code] = u;
	for (int i = 0; i < k; i ++)
		if (!(mask >> i & 1)) build_stack(code * 8 + i + 1, mask | (1 << i), u);
}
void dijkstra(int src) {
	fill(d + 1, d + n + 1, inf);
	priority_queue<PII, vector<PII>, greater<PII> > q;
	d[key[src]] = 0;
	q.push({0, key[src]});
	while (!q.empty()) {
		LL dist = q.top().first;
		int u = q.top().second;
		q.pop();
		if (dist != d[u]) continue;
		for (auto it : e[u]) {
			int v = it.first, w = it.second;
			if (d[v] > dist + w) {
				d[v] = dist + w;
				q.push({d[v], v});
			}
		}
	}
	for (int i = 0; i < p; i ++) g[src][i] = d[key[i]];
}
void solve() {
	for (int i = 1; i <= n; i ++) e[i].clear();
	p = sn = cnt = 0;
	cin >> n >> m >> k >> S >> T;
	for (int i = 1; i <= m; i ++) {
		int u, v, w;
		cin >> u >> v >> w;
		e[u].push_back({v, w});
		e[v].push_back({u, w});
	}
	add_key(S), add_key(T);
	for (int i = 0; i < k; i ++) {
		cin >> s[i] >> a[i] >> b[i] >> c[i];
		add_key(s[i]), add_key(a[i]), add_key(b[i]);
	}
	for (int i = 0; i < p; i ++) dijkstra(i);
	build_stack(0, 0, 0);
	memset(id, -1, sizeof id);
	for (int mask = 0; mask < (1 << k); mask ++)
		for (int j = 0; j < sn; j ++)
			if ((mask & masks[j]) == masks[j]) {
				id[mask][j] = cnt;
				used[cnt] = mask, stack_id[cnt] = j;
				cnt ++;
			}
	for (int u = 0; u < cnt; u ++) {
		int j = stack_id[u], mask = used[u];
		pop_id[u] = codes[j] ? id[mask][pre[j]] : -1;
		for (int i = 0; i < k; i ++)
			push_id[u][i] = mask >> i & 1 ? -1 : id[mask | (1 << i)][index_code[codes[j] * 8 + i + 1]];
		fill(f[u], f[u] + p, inf);
	}
	priority_queue<PII, vector<PII>, greater<PII> > q;
	f[0][S] = 0;
	q.push({0, S});
	while (!q.empty()) {
		LL dist = q.top().first;
		int u = q.top().second / p, v = q.top().second % p;
		q.pop();
		if (f[u][v] != dist) continue;
		if (v == T) {
			cout << dist << "\n";
			return;
		}
		auto relax = [&](int x, int y, LL w) {
			if (x != -1 && f[x][y] > dist + w) {
				f[x][y] = dist + w;
				q.push({f[x][y], x * p + y});
			}
		};
		for (int i = 0; i < p; i ++)
			if (g[v][i] != inf) relax(u, i, g[v][i]);
		relax(pop_id[u], v, 0);
		for (int i = 0; i < k; i ++)
			if (v == s[i]) relax(push_id[u][i], v, 0);
		int top = codes[stack_id[u]] % 8 - 1;
		if (top >= 0) {
			if (v == a[top]) relax(u, b[top], c[top]);
			if (v == b[top]) relax(u, a[top], c[top]);
		}
	}
	cout << "-1\n";
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int Q;
	cin >> Q;
	while (Q --) solve();
	return 0;
}

易错点

• S、T、s[i]、a[i]、b[i] 经 add_key 处理后是关键点编号，不能再当成原图编号直接使用。
• build_stack 中的 mask 表示当前栈内的符文，used[u] 才表示曾经激活过的符文。
• 撤销只删除栈顶，不能清除曾激活集合中的对应位；也不必返回符文石位置才能撤销。
• 激活符文只会压栈，不会自动传送；符文石位置与门端点可以不同。
• 只有栈顶的门生效，不能让所有激活过的门同时可用。门为双向，使用门不弹栈、不消耗符文。
• 原图不连通时仍可能通过传送门到达终点；仅在所有状态均不可达终点时输出 $-1$。
• 首次发现终点不一定最优，应在过滤过期项后，首次取出终点状态时结束。
• $S=T$ 时答案为 $0$；到达终点时不要求清空栈。