T1 受限航线（route）

简要题意

有 $T\le10$ 组相互独立的数据。每组给出按原顺序排列的 $N$ 个正整数段长 $A_i$，不断把最靠右的偶数段等分，直到所有段长都是奇数。再给出 $Q$ 个不递减、保证存在的位置 $X_j$，逐个输出最终第 $X_j$ 段的长度。$N,Q\le2\times10^5$，$A_i\le10^9$，$X_j\le10^{15}$，同一文件内 $\sum N,\sum Q\le4\times10^5$，最终序列可能远大于输入规模。

一句话题解

每个原始段最终对应一整块相同的奇数段，压缩记录其长度和数量，再用前缀段数二分定位查询。

完整题解

先看一个原始段

一段偶数材料被切成两半，两半又分别按相同规则加工。设 $A_i=b_i2^{k_i}$，其中 $b_i$ 为奇数，则最终得到 $2^{k_i}$ 段，每段长度为 $b_i$。

不需要质因数分解或特殊位运算：令 $c_i=1$，只要当前段长为偶数，就把段长除以 $2$，同时把 $c_i$ 乘以 $2$，即可得到 $b_i,c_i$。

这里的数量是 $2^{k_i}$，不是切分层数 $k_i$，也不是 $k_i+1$。例如 $8$ 最终对应八段 $1$。

为什么可以不模拟“最靠右”

每一次操作都在一个原始段内部进行，其他原始段不可能插入其中。因此，无论哪些段先切，一个原始段的所有后代始终连续，原始段之间也始终保持输入顺序。

最终序列就是先写 $c_1$ 个 $b_1$，再写 $c_2$ 个 $b_2$，依此类推。真正重要的是这个最终顺序，而不是全部切分过程；将原始段排序反而会破坏题意。

用前缀数量查询

定义 $S_i=\sum_{j=1}^{i}c_j$，并令 $S_0=0$。第 $i$ 个块对应的位置区间是 $[S_{i-1}+1,S_i]$。

对于查询 $X$，找到最小的 $i$ 使 $S_i\ge X$，输出 $b_i$。$c_i$ 均为正，所以 $S_i$ 严格递增，可以二分。恰好 $X=S_i$ 时仍属于第 $i$ 块，不能写成寻找第一个严格大于 $X$ 的前缀。

**正确性证明：**前两节证明了每个原始段的最终内容和块间顺序。前缀区间互不相交且恰好覆盖全部合法位置，二分找到的块正是包含查询位置的唯一块，因此输出正确。

复杂度为 $O(N\log A_{\max}+Q\log N)$，空间 $O(N)$。多组数据的总时间按各组相加，数组只需按单组最大规模分配。单段数量最多为 $2^{29}$，但累计数量可以超过 $2^{32}$；前缀和及查询必须使用 64 位整数。仅把有符号整型改为无符号 32 位仍不够。

满分参考实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, q, a[N];
LL sum[N];
void solve() {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		LL cnt = 1;
		while (a[i] % 2 == 0) a[i] /= 2, cnt *= 2;
		sum[i] = sum[i - 1] + cnt;
	}
	cin >> q;
	while (q --) {
		LL x;
		cin >> x;
		int l = 1, r = n;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (sum[mid] >= x) r = mid;
			else l = mid + 1;
		}
		cout << a[l] << "\n";
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

另一份满分做法：不回退的指针

查询本身不递减，因此所属原始块也不会向左移动。用一个指针从前往后推进，每个块最多经过一次，查询部分可以做到 $O(N+Q)$。这是自然且完整正确的另一份满分算法，不能把所有线性扫描都当成超时做法；真正应阻断的是每个查询都重新从头扫描。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, q, a[N];
LL sum[N];
void solve() {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		LL cnt = 1;
		while (a[i] % 2 == 0) a[i] /= 2, cnt *= 2;
		sum[i] = sum[i - 1] + cnt;
	}
	cin >> q;
	int pos = 1;
	while (q --) {
		LL x;
		cin >> x;
		while (sum[pos] < x) pos ++;
		cout << a[pos] << "\n";
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

部分分一：展开最终序列，25 分

当所有 $A_i\le8$ 时，最终段数不超过 $8N$。逐个原始段递归等分，遇到奇数就追加到全局结果数组中，之后直接按下标回答。时间 $O(N+Q+\sum c_i)$，空间 $O(N+\sum c_i)$，能完整覆盖测试点 $1\sim5$。

不要用“每切一段就把整个数组后半部分搬移一次”的实现；那可能变成平方复杂度，即使在这一档也不稳定。下面数组容量按该公开范围选择，一般范围不能用这份展开程序。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, M = 1600010;
int n, q, cnt, a[N], b[M];
void split(int x) {
	if (x % 2) b[++ cnt] = x;
	else split(x / 2), split(x / 2);
}
void solve() {
	cnt = 0;
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i <= n; i ++) split(a[i]);
	cin >> q;
	while (q --) {
		LL x;
		cin >> x;
		cout << b[x] << "\n";
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

部分分二：每次从头寻找所属块，35 分

已经得到每个原始段的长度和数量，但尚未想到二分时，可以逐段从查询位置中扣除块长。$N,Q\le1000$ 时，$O(NQ+N\log A_{\max})$ 可以完成；对其他大范围，查询集中在后段会迫使反复扫描。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, q, a[N];
LL cnt[N];
void solve() {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		cnt[i] = 1;
		while (a[i] % 2 == 0) a[i] /= 2, cnt[i] *= 2;
	}
	cin >> q;
	while (q --) {
		LL x;
		cin >> x;
		for (int i = 1; i <= n; i ++) {
			if (x <= cnt[i]) {
				cout << a[i] << "\n";
				break;
			}
			x -= cnt[i];
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

两条部分分合写，60 分

若所有 $A_i\le8$，使用展开法；否则使用每次从头扫描的方法。两个分支都是真实算法，分别覆盖测试点 $1\sim5$、$6\sim12$，因此预期累计为 $25+35=60$ 分。没有识别文件编号、主动退出或故意输出错误答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, M = 1600010;
int n, q, tot, a[N], b[M];
LL cnt[N];
void split(int x) {
	if (x % 2) b[++ tot] = x;
	else split(x / 2), split(x / 2);
}
void solve() {
	tot = 0;
	cin >> n;
	bool small = true;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
		if (a[i] > 8) small = false;
	}
	for (int i = 1; i <= n; i ++) {
		if (small) split(a[i]);
		cnt[i] = 1;
		while (a[i] % 2 == 0) a[i] /= 2, cnt[i] *= 2;
	}
	cin >> q;
	while (q --) {
		LL x;
		cin >> x;
		if (small) cout << b[x] << "\n";
		else for (int i = 1; i <= n; i ++) {
			if (x <= cnt[i]) {
				cout << a[i] << "\n";
				break;
			}
			x -= cnt[i];
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

多组数据与独立计分

本题 $20$ 个文件各 $5$ 分，不跨文件捆绑。展开法、逐查询扫描法和二者组合分别应获得 $25$、$35$、$60$ 分。附加限制要求文件内每一组都满足；允许组外的每个文件都必须被真实规模或反例阻断，不能依靠同档中的别的文件。

每组重新读取 $N,Q$ 并覆盖有效数组区间。展开程序的结果计数器必须清零；单调指针必须从 $1$ 重新开始。查询只在本组内不递减，不能把前一组的指针沿用到下一组。

常见错误与赛时切入点

• 把切分层数当段数：用 $8$ 亲手展开即可发现；复杂输入中还要核对不同块的交界。
• 将原始段排序：操作中的“最靠右”不是排序指令。比如原序列 $[8,3]$ 最终应是八个 $1$ 后跟一个 $3$。
• 前缀边界写错：位置 $8$ 属于上述第一个块，位置 $9$ 才属于第二个。
• 32 位前缀：大量 $2^{29}$ 级段数相加会溢出，无符号也不能解决。

本题赛时宜先手算几个单段，再判断最终序列能否真的存下。观察到“同一原始段对应一块重复值”后，先写出压缩或展开的可得分版本，再选择二分或单调指针完成满分。

T2 通行券（ticket）

简要题意

初始有 $R$ 张红券、$B$ 张蓝券，事先知道依次经过的 $Q$ 道检查站的全部方案。每站给出两个方案，必须选一个：消耗一张指定颜色的券，或支付指定现金。券不补充，不能用未提供的方式付款。输入至多 $20$ 组独立数据，每组给出 $R,B$ 和各站两个方案，逐组输出通过全程的最小现金支出，无解输出 $-1$。所有组的 $Q$ 之和不超过 $2\times10^5$，其中 $0\le R,B\le10^5$，$1\le Q\le10^5$，每个现金金额在 $[0,10^4]$ 内。

一句话题解

先扣除强制使用的红蓝券，再把用券抵现金的机会按节省金额降序处理，同时满足各颜色额度，并给只能用券的站点保留足够的券。

完整题解

1. 先想清楚：顺序到底限制了什么

题面要求按照检查站顺序通过，但所有方案事先已知。假如提前决定了每一站的付款方式，并且红券总用量不超过 $R$、蓝券总用量不超过 $B$，那么执行到任意一站时都不会发生券不够的问题。

原因是券只会被消耗，不会产生负消耗：任意前缀使用的某种券，不会多于整个方案使用的该种券。

因此，我们并不是擅自允许改变路线，而是证明了：只要选出的方案满足两种券的总量限制，就能按照原顺序执行。 不必用“处理到第几站、还剩多少红蓝券”这样庞大的状态逐步规划。

2. 将不同检查站放回它们对应的资源约束

忽略同站两个选项的左右顺序，共有以下六类。

类型	处理方式
RR	必须使用一张红券
BB	必须使用一张蓝券
TT	支付两个现金额中的较小值
RB	必须使用一张券，但颜色任选
RT	先按现金支付；若改用红券，可省去这一现金额
BT	先按现金支付；若改用蓝券，可省去这一现金额

先预留 RR、BB 的全部强制消耗。下面用 $r,b$ 表示预留后剩余的券数，用 $C$ 表示 RB 类站点数量。

如果 $r<0$ 或 $b<0$，说明某颜色的强制消耗已超库存，无解。如果 $r+b<C$，则连全部 RB 站都无法通过，也无解。

除此之外一定存在可行方案：RT、BT 全部付现金，RB 用剩余券即可。

3. 从“最少付款”改成“最多节省”

先将 TT 的最小现金以及全部 RT、BT 的现金金额计入基线答案。每个 RT、BT 就变成一个机会：使用一张对应颜色的券，节省 $x$ 元。

所选机会需要满足三个条件：

• 使用红券的机会不超过 $r$ 个。
• 使用蓝券的机会不超过 $b$ 个。
• 总共不超过 $r+b-C$ 个，给 RB 留下至少 $C$ 张券。

将全部机会按节省金额降序排序。如果当前机会对应颜色还有券，并且用掉一张后仍能保留 $C$ 张券，就接受它，从基线现金中减去 $x$。

注意条件写成当前 $r+b>C$，而不是 $r+b\ge C$。当两者相等时，所有剩余券都必须留给 RB，不能再抵现金。

4. 为什么这个贪心正确

设初始可用于抵现金的券最多为 $K=r+b-C$ 张。

固定某种颜色使用了 $k$ 张券，最优选择一定可以取该颜色金额最大的 $k$ 个机会。若选了一个较小金额而没选同颜色的更大金额，交换二者不改变任何券数限制，且不会让答案变差。

所以，红色只需考虑它最大的至多 $r$ 个机会，蓝色只需考虑它最大的至多 $b$ 个机会；其他机会不可能优于同颜色已经保留的项。把这两份候选合并，从中取最大的至多 $K$ 项即可。因为每种颜色的候选本来就没有超过该色券数，这样不会违反颜色限制。

统一排序、颜色额度满后跳过，等价于上面的选择过程。停止时为 RB 保留了足够的券，又获得了最大的现金节省，因而现金支出最小。

金额相等时任选顺序都不影响最优值。金额为 $0$ 的机会可以接受也可以不接受，只要仍满足所有券数限制即可。

5. 复杂度与实现边界

每组最多有 $Q$ 个抵现金机会，时间复杂度为 $O(Q\log Q)$；整个文件为 $O(\sum Q\log Q)$，使用的空间为 $O(\max Q)$。只需定长全局数组和排序，不需要背包、网络流或复杂数据结构。

RR 和 BB 都只扣一张券，TT 只支付较小的一笔。读入 T-x 时，短横线是方案格式的一部分，不是负号。现金基线不超过 $Q\times10^4\le10^9$；实现使用 LL，无需为本范围虚构 32 位溢出的限制。

每组都要重新读入红蓝券数，将现金答案、机会个数和 RB 需求计数归零；只处理当前组的数组有效区间。某组无解后只结束该组，不能直接退出整个程序。

参考实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
struct Node {
	int x, c;
	bool operator < (const Node &t) const {
		return x > t.x;
	}
} a[N];
int r, b, n, cnt, need;
LL ans;
int get_cost(string s) {
	int x = 0;
	for (int i = 2; i < (int)s.size(); i ++) x = x * 10 + s[i] - '0';
	return x;
}
void solve() {
	ans = 0;
	cnt = 0;
	need = 0;
	cin >> r >> b >> n;
	for (int i = 1; i <= n; i ++) {
		string s, t;
		cin >> s >> t;
		if (s == "R" && t == "R") r --;
		else if (s == "B" && t == "B") b --;
		else if (s[0] == 'T' && t[0] == 'T') ans += min(get_cost(s), get_cost(t));
		else if (s[0] != 'T' && t[0] != 'T') need ++;
		else {
			if (s[0] == 'T') swap(s, t);
			int x = get_cost(t);
			ans += x;
			a[++ cnt] = {x, s == "R" ? 0 : 1};
		}
	}
	if (r < 0 || b < 0 || r + b < need) {
		cout << -1 << "\n";
		return;
	}
	sort(a + 1, a + cnt + 1);
	for (int i = 1; i <= cnt && r + b > need; i ++) {
		if (a[i].c == 0 && r) r --, ans -= a[i].x;
		else if (a[i].c == 1 && b) b --, ans -= a[i].x;
	}
	cout << ans << "\n";
	return;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

6. 各档部分分怎样获得

测试点 $2\sim3$ 的“方案只有 T、R”包括 RR 和 TT，并不保证每站恰好一个红券方案和一个现金方案。

路线	正确范围和做法	累计分值
只考虑现金支付	每站在现金方案中取最小值；完整覆盖测试点 1、4～6	$20$
按顺序能用券就用	对单站输入及全现金输入完整正确；覆盖测试点 1～6	$30$
只使用红券和现金，进行最优分配	先留强制红券，再给最大金额免单；覆盖测试点 1～6、12～15	$50$
先留强制红蓝券，再顺序使用剩余券	在纯券情况下，剩余 RB 只需检查总数；覆盖测试点 1～11	$55$
先安排 RB，再分别优化两色免单	无 RB 的单色现金情况与无现金情况均正确；覆盖测试点 1～15	$75$
把颜色上限和 RB 总需求同时考虑	完整贪心	$100$

表中每个代表策略都对其承诺范围完整正确，不是用输入编号或故意提前退出拼分。每个正式文件独立计分；范围外偶然答对某个逻辑 case，不代表答对整个文件。

20 分：现金限定策略。 所有方案都是现金时，每站独立取小即可。以下程序在一般输入中尝试完全不使用券，因此遇到没有现金选项的站会认为不可行；这不是一般情况下的正确结论。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int r, b, n;
LL ans;
bool ok = true;
int get_cost(string s) {
	int x = 0;
	for (int i = 2; i < (int)s.size(); i ++) x = x * 10 + s[i] - '0';
	return x;
}
void solve() {
	ans = 0;
	ok = true;
	cin >> r >> b >> n;
	for (int i = 1; i <= n; i ++) {
		string s, t;
		cin >> s >> t;
		int x = 1e9;
		if (s[0] == 'T') x = min(x, get_cost(s));
		if (t[0] == 'T') x = min(x, get_cost(t));
		if (x == 1e9) ok = false;
		else ans += x;
	}
	cout << (ok ? ans : -1) << "\n";
	return;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

30 分：顺序贪心。 优先选择当前可用的券，没有券可选时支付较小现金。只有一站时，这就是正确的最优选择；全现金时也正确。但它没有给未来预留资源。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int r, b, n;
LL ans;
bool ok = true;
int get_cost(string s) {
	int x = 0;
	for (int i = 2; i < (int)s.size(); i ++) x = x * 10 + s[i] - '0';
	return x;
}
void solve() {
	ans = 0;
	ok = true;
	cin >> r >> b >> n;
	for (int i = 1; i <= n; i ++) {
		string s, t;
		cin >> s >> t;
		if ((s == "R" || t == "R") && r) r --;
		else if ((s == "B" || t == "B") && b) b --;
		else {
			int x = 1e9;
			if (s[0] == 'T') x = min(x, get_cost(s));
			if (t[0] == 'T') x = min(x, get_cost(t));
			if (x == 1e9) ok = false;
			else ans += x;
		}
	}
	cout << (ok ? ans : -1) << "\n";
	return;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

50 分：只优化红券。 当所有选项均为 R 或 T 时，预留 RR 后，将红券用于现金较大的 RT 站。参考程序即使读到蓝券方案也不使用蓝券，所以不能完整解决纯双色券测试点。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int r, b, n, cnt, a[N];
LL ans;
bool ok = true;
int get_cost(string s) {
	int x = 0;
	for (int i = 2; i < (int)s.size(); i ++) x = x * 10 + s[i] - '0';
	return x;
}
void solve() {
	ans = 0;
	cnt = 0;
	ok = true;
	cin >> r >> b >> n;
	for (int i = 1; i <= n; i ++) {
		string s, t;
		cin >> s >> t;
		bool red = s == "R" || t == "R";
		int x = 1e9;
		if (s[0] == 'T') x = min(x, get_cost(s));
		if (t[0] == 'T') x = min(x, get_cost(t));
		if (red && x == 1e9) r --;
		else if (!red && x == 1e9) ok = false;
		else {
			ans += x;
			if (red) a[++ cnt] = x;
		}
	}
	if (r < 0) ok = false;
	sort(a + 1, a + cnt + 1, greater<int>());
	for (int i = 1; i <= cnt && i <= r; i ++) ans -= a[i];
	cout << (ok ? ans : -1) << "\n";
	return;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

55 分：预留强制消耗。 先扣除所有 RR、BB，再按顺序处理其他站。纯券输入中只剩 RB，可以使用任意剩余券；现金与券混合时仍可能将券浪费在小额机会。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int r, b, n, c[N], w[N];
LL ans;
int get_cost(string s) {
	int x = 0;
	for (int i = 2; i < (int)s.size(); i ++) x = x * 10 + s[i] - '0';
	return x;
}
void read_data() {
	cin >> r >> b >> n;
	for (int i = 1; i <= n; i ++) {
		string s, t;
		cin >> s >> t;
		if (s == "R" && t == "R") c[i] = 0;
		else if (s == "B" && t == "B") c[i] = 1;
		else if (s[0] == 'T' && t[0] == 'T') c[i] = 2, w[i] = min(get_cost(s), get_cost(t));
		else if (s[0] != 'T' && t[0] != 'T') c[i] = 3;
		else {
			if (s[0] == 'T') swap(s, t);
			c[i] = s == "R" ? 4 : 5;
			w[i] = get_cost(t);
		}
	}
}
void solve() {
	ans = 0;
	read_data();
	for (int i = 1; i <= n; i ++) {
		if (c[i] == 0) r --;
		if (c[i] == 1) b --;
	}
	bool ok = r >= 0 && b >= 0;
	for (int i = 1; i <= n && ok; i ++) {
		if (c[i] == 2) ans += w[i];
		else if (c[i] == 3) {
			if (r) r --;
			else if (b) b --;
			else ok = false;
		}
		else if (c[i] == 4) {
			if (r) r --;
			else ans += w[i];
		}
		else if (c[i] == 5) {
			if (b) b --;
			else ans += w[i];
		}
	}
	cout << (ok ? ans : -1) << "\n";
	return;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

75 分：将两个局部模型拼起来。 先让 RB 使用剩余数量较多的颜色，再分别将红蓝券用于最大金额。纯券时这能正确判断可行性，单色现金时没有 RB 需要分配，所以也正确。但一般情况下，某颜色库存多并不意味着该颜色更适合先分给 RB。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
struct Node {
	int x, c;
	bool operator < (const Node &t) const {
		return x > t.x;
	}
} a[N];
int r, b, n, cnt, need;
LL ans;
int get_cost(string s) {
	int x = 0;
	for (int i = 2; i < (int)s.size(); i ++) x = x * 10 + s[i] - '0';
	return x;
}
void read_data() {
	cin >> r >> b >> n;
	for (int i = 1; i <= n; i ++) {
		string s, t;
		cin >> s >> t;
		if (s == "R" && t == "R") r --;
		else if (s == "B" && t == "B") b --;
		else if (s[0] == 'T' && t[0] == 'T') ans += min(get_cost(s), get_cost(t));
		else if (s[0] != 'T' && t[0] != 'T') need ++;
		else {
			if (s[0] == 'T') swap(s, t);
			int x = get_cost(t);
			ans += x;
			a[++ cnt] = {x, s == "R" ? 0 : 1};
		}
	}
}
void solve() {
	ans = 0;
	cnt = 0;
	need = 0;
	read_data();
	if (r < 0 || b < 0 || r + b < need) {
		cout << -1 << "\n";
		return;
	}
	while (need --) {
		if (r >= b && r) r --;
		else b --;
	}
	sort(a + 1, a + cnt + 1);
	for (int i = 1; i <= cnt; i ++) {
		if (a[i].c == 0 && r) r --, ans -= a[i].x;
		else if (a[i].c == 1 && b) b --, ans -= a[i].x;
	}
	cout << ans << "\n";
	return;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

7. 小规模独立验证思路

每一站只有两个选择。可以直接按原顺序 DFS，记录剩余红蓝券及已付现金，枚举所有合法选择，取最小支出。它完全不依赖上述离线贪心模型，适合在小规模验证答案。

最坏枚举 $2^Q$ 种选择，不能作为一般规模算法。本次公开范围并没有给出一个专门的 $Q\le12$ 档，因此这份程序是独立小规模校验解，不将它误称为稳定的某档正式部分分。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
const LL INF = 1LL << 60;
int n, r, b, c[N][2], w[N][2];
LL ans = INF;
void dfs(int u, int red, int blue, LL cost) {
	if (u > n) {
		ans = min(ans, cost);
		return;
	}
	for (int j = 0; j < 2; j ++) {
		if (c[u][j] == 0 && red) dfs(u + 1, red - 1, blue, cost);
		else if (c[u][j] == 1 && blue) dfs(u + 1, red, blue - 1, cost);
		else if (c[u][j] == 2) dfs(u + 1, red, blue, cost + w[u][j]);
	}
}
void solve() {
	ans = INF;
	cin >> r >> b >> n;
	for (int i = 1; i <= n; i ++)
		for (int j = 0; j < 2; j ++) {
			string s;
			cin >> s;
			if (s == "R") c[i][j] = 0;
			else if (s == "B") c[i][j] = 1;
			else {
				c[i][j] = 2;
				w[i][j] = stoi(s.substr(2));
			}
		}
	dfs(1, r, b, 0);
	cout << (ans == INF ? -1 : ans) << "\n";
	return;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve();
	return 0;
}

8. 容易想到但错误的方向

先留强制券，再有券就用，也不正确。 取 $R=1,B=0$，两站依次为 (R,T-1)、(R,T-100)。正确答案是 $1$；先用券会支付 $100$。这两站没有 RR、BB，增加“预留强制券”的补丁并不能解决问题。

RB 使用剩余更多的颜色，也不正确。 取 $R=2,B=1$，依次为 (R,B)、(R,T-100)、(R,T-99)。第一站用蓝券、后两站用红券，支出为 $0$。若第一站用库存较多的红券，就会至少多付 $99$。

两色分别最优，未必全局可行。 取 $R=B=1$，依次为 (R,B)、(R,T-10)、(B,T-20)。把两张券都用于免现金会留下无法通过的 RB；正确支出是 $10$，不是 $0$。

局部退券不能代替全局比较。 如果先用券免掉一笔红色的 $1$ 元，以及许多蓝色的 $100$ 元，后来需要撤销一次免单为 RB 留券，应撤销 $1$ 元那笔。只在最近两笔或最近若干笔中寻找，会漏掉更早的便宜选择。

只看总券数会把颜色用错。 例如没有红券但有很多蓝券时，(R,T-10) 仍必须支付 $10$，不能把蓝券用于这个站。

同样，三个无解条件不能互相代替：强制红券不足、强制蓝券不足，以及两色均未超用但剩余总数不足以支付 RB，都需要分别判断。大量另一种颜色的券，可能在总数上掩盖某颜色已经为负的问题。

赛时可以依次问自己：哪些站强制消耗某颜色？哪些站只是提供现金折扣？哪些站必须用券却允许换颜色？模型提取到这一步，满分做法只剩几个计数和一次排序。

T3 受限航线（route）

简要题意

给定 $T\le10$ 组相互独立的无向多重图。每组有 $N\le2000$ 个点、$M\le10000$ 条边，边上给出正的航行时间和非负的船体损耗，船体厚度为 $K\le200$。从指定的 $A$ 到 $B$，要求总损耗严格小于 $K$，逐组输出最小总时间，无解输出 $-1$。同一文件内 $\sum N\le4000$、$\sum M\le20000$，单条时间不超过 $10^5$、损耗不超过 $200$。

一句话题解

把“所在岛屿、累计船体损耗”一起作为状态，使用 Dijkstra 求这些状态之间的最短时间。

完整题解

一、为什么普通最短路的状态不够

如果只记录到达每座岛屿的最短时间，可能丢掉最终必须使用的方案。

例如船体厚度为 $5$，从起点到中转岛有两种走法：第一种用时 $1$、损耗 $4$，第二种用时 $3$、损耗 $1$；从中转岛到终点还要损耗 $3$。第一种虽然更快，但已经没有足够的船体厚度走完后半程；第二种才可能完成任务。

因此，到达同一座岛时，“时间更少”和“损耗更少”是两个不同的优势，不能只按其中一个比较。即使保留两个、八个当前较快的方案，也没有依据：合法输入可以让同一座岛出现更多组互不支配的时间与损耗组合。

二、把船体损耗加入状态

设 $f[u][h]$ 表示从起点出发，到达岛屿 $u$，累计损耗恰好为 $h$ 的最短时间。只考虑 $0\le h<K$ 的状态。

初始状态为 $f[A][0]=0$，其余状态设为无穷大。

假设当前位于状态 $(u,h)$，一条航线连接 $u,v$，航行时间为 $t$、损耗为 $d$。当 $h+d<K$ 时，可以转移：

$$f[v][h+d]=\min\bigl(f[v][h+d],f[u][h]+t\bigr).$$

将每个 $(u,h)$ 看作一个新节点，上述转移就是一条权值为 $t$ 的有向边。所有 $t$ 均为正，因此可以使用 Dijkstra。

不需要把完整状态图建出来。取出状态 $(u,h)$ 时，遍历原图中与 $u$ 相连的航线，现场检查新的损耗即可。

答案为 $\min_{0\le h<K} f[B][h]$。也可以在 Dijkstra 第一次从堆中取出一个距离仍有效、且所在岛屿为 $B$ 的状态时立即返回；这时它已经是全部终点状态中的最小值。

三、正确性证明

引理 1： 每条合法航行路线都对应状态图中从 $(A,0)$ 出发的一条路径，且总时间不变。

沿原路线累加损耗。由于每个前缀损耗均严格小于 $K$，每一步都会成为上述合法转移，状态图边权之和就是原路线的总时间。

引理 2： 状态图中从 $(A,0)$ 到任意 $(B,h)$ 的路径都对应一条合法航行路线，且总时间不变。

每条状态图边来自一条真实航线，所有经过的状态均满足损耗小于 $K$，因此按这些航线依次航行不会使船体损坏。

引理 3： 对同一状态 $(u,h)$，只保留最短到达时间不会丢掉更优答案。

两种方案此时位于同一岛屿，已损耗厚度也完全相同，后续可使用的航线序列相同。较早到达不会限制后续选择，所以较晚的方案可以舍弃。

由引理 1、2，原问题等价于状态图上的最短路；由引理 3，距离表具有充分的状态信息。状态图边权为正，Dijkstra 正确，故算法得到的最短时间恰为原问题最优值；无终点状态可达时输出 $-1$ 也正确。

四、复杂度与实现细节

单组最多有 $KN$ 个状态、约 $2KM$ 次方向相关的边扩展。使用二叉堆，时间复杂度为 $O(KN+KM\log(KN))$。距离表占 $O(KN)$，原图占 $O(N+M)$；使用允许重复入堆的写法时，堆的最坏额外空间为 $O(KM)$，不能把整个程序空间只写成距离表大小。

多组复杂度是各组复杂度之和。当前总量限制给出 $\sum KN\le8\times10^5$、$\sum KM\le4\times10^6$。各组数组和原图可反复使用，不必同时保存全部任务。

• 损耗恰好等于 $K$ 时不能经过，因此判断是 nh >= k 时跳过。
• 损耗为 $0$ 的边合法；它不增加损耗下标，但仍增加正的时间。
• 不同重边可能体现时间与损耗的不同取舍，不能只保留最快的一条。
• 取出堆元素时检查它是否仍等于距离表，舍弃过时记录。
• 每组清空邻接表和距离状态。正解会提前返回，所以新一组开始时也必须清空上一组遗留的堆。
• 参考代码使用 LL 保存时间与无穷大，避免把无穷大参与相加时溢出。

五、20 分：零损耗边上跑 Floyd

测试点 $1\sim4$ 的每组均有 $K=1$，合法总损耗只能是 $0$。因为边损耗非负，所以只有损耗为 $0$ 的边能够使用。删去其他边，问题成为普通无向图最短路。

每组 $N\le200$，可以用 Floyd 枚举中转点，复杂度 $O(N^3+M)$、空间 $O(N^2)$。同文件最多 $10$ 组，因此这一档总的立方工作量不超过 $8\times10^7$。

重边取时间最小值只在这里安全：留下的边损耗都是 $0$，不再存在时间与损耗的取舍。档外程序仍正常执行自己的算法，不靠识别测试点或主动退出获取分数。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2010;
const LL INF = 1LL << 60;
int n, m, k, a, b;
LL f[N][N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> k >> n >> m;
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= n; j ++) f[i][j] = (i == j ? 0 : INF);
		for (int i = 1; i <= m; i ++) {
			int u, v, t, h;
			cin >> u >> v >> t >> h;
			if (!h) f[u][v] = f[v][u] = min(f[u][v], (LL)t);
		}
		cin >> a >> b;
		for (int p = 1; p <= n; p ++)
			for (int i = 1; i <= n; i ++) {
				if (f[i][p] == INF) continue;
				for (int j = 1; j <= n; j ++) f[i][j] = min(f[i][j], f[i][p] + f[p][j]);
			}
		cout << (f[a][b] == INF ? -1 : f[a][b]) << "\n";
	}
	return 0;
}

六、40 分：零损耗边上跑普通 Dijkstra

测试点 $5\sim8$ 仍然保证每组 $K=1$，但点数可达到 $2000$。模型不变，用普通 Dijkstra 代替 Floyd，单组时间复杂度 $O(N+M\log N)$。

这份程序也能完整处理前四个测试点，累计应获得 $40$ 分。不能仅按后面的性质组把它记为 $20$ 分。本题每个文件独立计 $5$ 分，不存在跨文件捆绑。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;
const int N = 2010;
const LL INF = 1LL << 60;
struct Edge {
	int v, t;
};
vector<Edge> e[N];
priority_queue<PII, vector<PII>, greater<PII>> q;
LL f[N];
int n, m, k, a, b;
LL dijkstra() {
	while (!q.empty()) q.pop();
	for (int i = 1; i <= n; i ++) f[i] = INF;
	f[a] = 0;
	q.push({0, a});
	while (!q.empty()) {
		PII t = q.top();
		q.pop();
		int u = t.second;
		if (t.first != f[u]) continue;
		if (u == b) return t.first;
		for (auto it : e[u])
			if (f[it.v] > t.first + it.t) {
				f[it.v] = t.first + it.t;
				q.push({f[it.v], it.v});
			}
	}
	return -1;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> k >> n >> m;
		for (int i = 1; i < N; i ++) e[i].clear();
		for (int i = 1; i <= m; i ++) {
			int u, v, t, h;
			cin >> u >> v >> t >> h;
			if (!h) {
				e[u].push_back({v, t});
				e[v].push_back({u, t});
			}
		}
		cin >> a >> b;
		cout << dijkstra() << "\n";
	}
	return 0;
}

七、满分参考实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2010, H = 210;
struct Edge {
	int v, t, h;
};
struct Node {
	LL d;
	int u, h;
	bool operator < (const Node &b) const {
		return d > b.d;
	}
};
vector<Edge> e[N];
priority_queue<Node> q;
int n, m, k, a, b;
LL f[N][H];
LL dijkstra() {
	while (!q.empty()) q.pop();
	for (int i = 1; i <= n; i ++) memset(f[i], 0x3f, sizeof f[i]);
	f[a][0] = 0;
	q.push({0, a, 0});
	while (!q.empty()) {
		Node t = q.top();
		q.pop();
		int u = t.u, h = t.h;
		if (t.d != f[u][h]) continue;
		if (u == b) return t.d;
		for (auto it : e[u]) {
			int j = it.v, nh = h + it.h;
			if (nh >= k) continue;
			if (f[j][nh] > t.d + it.t) {
				f[j][nh] = t.d + it.t;
				q.push({f[j][nh], j, nh});
			}
		}
	}
	return -1;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> k >> n >> m;
		for (int i = 1; i < N; i ++) e[i].clear();
		for (int i = 1; i <= m; i ++) {
			int u, v, t, h;
			cin >> u >> v >> t >> h;
			e[u].push_back({v, t, h});
			e[v].push_back({u, t, h});
		}
		cin >> a >> b;
		cout << dijkstra() << "\n";
	}
	return 0;
}

八、常见错误方向

只保留最快方案，或只保留固定数量的较快方案，会忽略后程所需要的低损耗状态。可以用多条到达中转点的路径，使时间逐渐增加、损耗逐渐减少，再在较远处设置需要较多剩余厚度的航线，检验这种策略。

只保留损耗最少的方案也不正确：题目最小化的是时间，只要厚度足够，就允许用更多损耗换取更短时间。

删除全部正损耗航线是有严格适用范围的 $40$ 分做法，不是一般情况下的完整算法。一般档一个文件有多组数据；即使它能答对其中的无解任务，也必须答对同文件其他任务才能获得该点分数。

赛时识别顺序可以是：先发现 $K=1$ 时必须只走零损耗边，争取普通最短路的 $40$ 分；再问自己“同一岛屿的两种到达方式，是否真的只要比较时间”，从而找到需要增加的损耗维。

环湖集章（stamp）

简要题意

输入包含 $T\le20$ 组相互独立的活动，每组给出周长 $L\le10^9$ 的环形步道上 $N\le200$ 个点的顺时针坐标 $X_i$ 和截止时刻 $T_i\le10^9$，其中 $0<X_1<\cdots<X_N<L$。从坐标 $0$、时刻 $0$ 出发，以每秒 $1$ 米的速度沿步道自由行走、折返，首次不晚于截止时刻到达一个点即可取得该点的章，盖章不耗时；过期点仍可经过，每点只计一次，不要求返回起点。同一输入文件中 $\sum N\le600$，对每组分别输出最多能取得的不同印章数量。

一句话题解

把已首次经过的点表示为起点两侧扩展出的区间，以两侧点数、当前端点和取得章数为状态，保存最早到达时间。

完整题解

1. 不枚举任意点的访问排列

从起点沿某个方向前往一个尚未到达的点，路上更近的点一定会先被经过。因此，“已首次经过的点”始终由顺时针方向的前 $i$ 个点和逆时针方向的后 $j$ 个点组成。下一个首次经过的点只能是 $i+1$ 或 $N-j$。

在遇到下一个新点之前，额外的往返和等待都只会使到达更晚，不会增加可取得的印章。因此，考虑最优方案时，只需记录停在已探查区间的哪一个端点，并选择向哪一侧扩展。

注意“经过”不等于“取得印章”。即使一个点已经过期，也可以经过它，继续前往后面的点；若首次到达就已经过期，以后再回来也不会变成有效点。

2. 两端扩展搜索：15 分

记录 $(i,j,p,now,cnt)$：两侧分别经过 $i,j$ 个点，当前处于端点 $p$，时刻为 $now$，已取得 $cnt$ 枚章。每步选择首次经过左侧或右侧的下一个点，计算到达时间并判断能否取得印章。

每层至多两个分支、深度 $N$，时间复杂度 $O(2^N)$，递归栈 $O(N)$。每次扩展只用常数时间，不再枚举任意点的全排列。$N\le15$ 时覆盖测试点 1～3，共 15 分。

可以增加“现有章数加剩余点数不超过当前答案”的正确剪枝，但这不能保证大数据复杂度。只有在每个公开范围内均能稳定完成时，才能认为该路线覆盖对应分数。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 205;
int n, ans;
LL len, x[N], t[N];
void dfs(int i, int j, int p, int cnt, LL now) {
	ans = max(ans, cnt);
	if (i + j == n) return;
	LL a = now + (p == 0 ? x[i + 1] - x[i] : len - x[n - j + 1] + x[i + 1]);
	LL b = now + (p == 0 ? x[i] + len - x[n - j] : x[n - j + 1] - x[n - j]);
	dfs(i + 1, j, 0, cnt + (a <= t[i + 1]), a);
	dfs(i, j + 1, 1, cnt + (b <= t[n - j]), b);
}
void solve_case() {
	ans = 0;
	cin >> n >> len;
	for (int i = 1; i <= n; i ++) cin >> x[i];
	for (int i = 1; i <= n; i ++) cin >> t[i];
	x[n + 1] = len;
	dfs(0, 0, 0, 0, 0);
	cout << ans << "\n";
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve_case();
	return 0;
}

3. 用时间作维度：另一条 15 分路线

当所有截止时刻不超过 $200$ 时，时刻 $200$ 之后不可能再获得新的印章。定义 $g[i][j][t][p]$ 为到达相同探查区间、相同端点、恰好时刻 $t$ 时，可以取得的最多章数。扩展一侧后，按到达时间转移，并更新章数。

时间只需枚举 $0\ldots200$，时间复杂度 $O(N^2\cdot200)$，空间复杂度相同，覆盖测试点 1、4、5，共 15 分。参考程序在任意输入上都诚实求“前 200 秒内最多取得多少枚章”；大时间输入上可能少计，而不是看到大数就直接退出。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 205, M = 201;
int n, ans, f[N][N][M][2];
LL len, x[N], t[N];
void solve_case() {
	ans = 0;
	cin >> n >> len;
	for (int i = 1; i <= n; i ++) cin >> x[i];
	for (int i = 1; i <= n; i ++) cin >> t[i];
	x[n + 1] = len;
	memset(f, -1, sizeof f);
	f[0][0][0][0] = f[0][0][0][1] = 0;
	// 只求活动开始后 200 秒内最多可以取得的章数。
	for (int s = 0; s < n; s ++)
		for (int i = 0; i <= s; i ++) {
			int j = s - i;
			for (int now = 0; now < M; now ++)
				for (int p = 0; p < 2; p ++) {
					int cnt = f[i][j][now][p];
					if (cnt < 0) continue;
					LL a = now + (p == 0 ? x[i + 1] - x[i] : len - x[n - j + 1] + x[i + 1]);
					LL b = now + (p == 0 ? x[i] + len - x[n - j] : x[n - j + 1] - x[n - j]);
					if (a < M) {
						int u = cnt + (a <= t[i + 1]);
						f[i + 1][j][a][0] = max(f[i + 1][j][a][0], u);
						ans = max(ans, u);
					}
					if (b < M) {
						int u = cnt + (b <= t[n - j]);
						f[i][j + 1][b][1] = max(f[i][j + 1][b][1], u);
						ans = max(ans, u);
					}
				}
		}
	cout << ans << "\n";
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve_case();
	return 0;
}

将两条路线组合：$N\le15$ 时运行完整搜索，否则运行上述 200 秒内的 DP，可覆盖测试点 1～5，共 25 分。测试点 1 只能计算一次，不是 30 分。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 205, M = 201;
int n, ans, f[N][N][M][2];
LL len, x[N], t[N];
void dfs(int i, int j, int p, int cnt, LL now) {
	ans = max(ans, cnt);
	if (i + j == n) return;
	LL a = now + (p == 0 ? x[i + 1] - x[i] : len - x[n - j + 1] + x[i + 1]);
	LL b = now + (p == 0 ? x[i] + len - x[n - j] : x[n - j + 1] - x[n - j]);
	dfs(i + 1, j, 0, cnt + (a <= t[i + 1]), a);
	dfs(i, j + 1, 1, cnt + (b <= t[n - j]), b);
}
void solve_time() {
	memset(f, -1, sizeof f);
	f[0][0][0][0] = f[0][0][0][1] = 0;
	for (int s = 0; s < n; s ++)
		for (int i = 0; i <= s; i ++) {
			int j = s - i;
			for (int now = 0; now < M; now ++)
				for (int p = 0; p < 2; p ++) {
					int cnt = f[i][j][now][p];
					if (cnt < 0) continue;
					LL a = now + (p == 0 ? x[i + 1] - x[i] : len - x[n - j + 1] + x[i + 1]);
					LL b = now + (p == 0 ? x[i] + len - x[n - j] : x[n - j + 1] - x[n - j]);
					if (a < M) {
						int u = cnt + (a <= t[i + 1]);
						f[i + 1][j][a][0] = max(f[i + 1][j][a][0], u);
						ans = max(ans, u);
					}
					if (b < M) {
						int u = cnt + (b <= t[n - j]);
						f[i][j + 1][b][1] = max(f[i][j + 1][b][1], u);
						ans = max(ans, u);
					}
				}
		}
}
void solve_case() {
	ans = 0;
	cin >> n >> len;
	for (int i = 1; i <= n; i ++) cin >> x[i];
	for (int i = 1; i <= n; i ++) cin >> t[i];
	x[n + 1] = len;
	if (n <= 15) dfs(0, 0, 0, 0, 0);
	else solve_time();
	cout << ans << "\n";
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve_case();
	return 0;
}

4. 将章数作为维度：100 分

完整数据的时间范围达到 $10^9$，不能继续枚举每个时刻；但章数只可能是 $0\ldots N$。把“最多章数”和“最早时间”交换位置，定义

$$f[i][j][k][p]=\text{顺时针经过 }i\text{ 个点、逆时针经过 }j\text{ 个点，取得 }k\text{ 枚章，停在端点 }p\text{ 的最早时间。}$$

规定 $p=0$ 为顺时针端点，$p=1$ 为逆时针端点。补两个表示起点的坐标 $X_0=0$、$X_{N+1}=L$。初始化 $f[0][0][0][0]=f[0][0][0][1]=0$，其余为无穷大。

设当前时刻为 $v=f[i][j][k][p]$。向顺时针侧扩展，下一点为 $i+1$：

• 若 $p=0$，到达时刻 $a=v+X_{i+1}-X_i$；
• 若 $p=1$，到达时刻 $a=v+L-X_{N-j+1}+X_{i+1}$。

令 $k'=k+[a\le T_{i+1}]$，用 $a$ 更新 $f[i+1][j][k'][0]$。

向逆时针侧扩展，下一点为 $N-j$：

• 若 $p=0$，到达时刻 $b=v+X_i+L-X_{N-j}$；
• 若 $p=1$，到达时刻 $b=v+X_{N-j+1}-X_{N-j}$。

令 $k'=k+[b\le T_{N-j}]$，用 $b$ 更新 $f[i][j+1][k'][1]$。方括号在条件成立时为 $1$，否则为 $0$。

按 $i+j$ 递增转移，所有可达状态中的最大 $k$ 就是答案。无需强求最后停在哪一端，也不必另加回到起点的路程。

5. 正确性证明

首先，任一行走过程的已首次经过点形成起点两侧的连续区间，下一个新点必定是两侧之一。删除遇到下一个新点之前的多余等待或折返，只会使到达时间提前，因此 DP 枚举的两种扩展足以涵盖一个最优方案。

其次，给定同一个探查区间、端点和已取得章数，较早到达不会使后面的任何印章变得更难取得。沿同一后续行走路线，更早出发将不晚于原来的时刻到达每个新点，取得的章数只可能增加。因此只保留最早时刻，不会降低最终可取得的最多章数。

最后，两种转移所增加的路程正是从当前端点沿已探查弧段出发、到达所选下一新点的距离；且恰好在到达时刻不超过截止时才增加一次章数。每个点只在首次扩展进区间时判断一次，不会重复计数。初始化对应真实起点，所有转移对应合法行走，结合前两点，取所有可达状态的最大章数得到最优答案。

6. 复杂度与实现边界

单组状态数为 $O(N^3)$，每个状态两次常数转移，因此整份输入的时间复杂度为 $O(\sum N^3)$。每组 $N\le200$、$\sum N\le600$，所以 $\sum N^3\le200^2\cdot600=2.4\times10^7$。参考实现使用定长全局四维数组，空间复杂度 $O(N^3)$，声明数组约为 $132$ MiB，内存限制为 $512$ MiB。利用 $i+j$ 分层可滚动为 $O(N^2)$ 空间，但不要求选手必须做这项优化。

本实现仍保留超过最大截止时刻的可达状态，累计行走时间可能超过 32 位整数范围，因此用 64 位整数。若另一种实现明确舍弃超过最大截止时刻的状态，并保证加法及无穷大处理不溢出，使用较小整数类型也可能正确，不能仅凭出现 int 就判为错解。截止比较包含等号。跨到另一端时，不能直接取两个坐标在圆周上的较短距离而忽略途中尚未计入状态的新点。

各组复用同一份全局数组。每组必须将答案归零，并重新初始化本组可能访问的全部 DP 状态；不能让前一组较早的到达时刻进入后一组。按组依次输出一行，不添加组号或遗漏分隔。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 205;
const LL INF = 4e18;
int n, ans;
LL len, x[N], t[N], f[N][N][N][2];
void solve_case() {
	ans = 0;
	cin >> n >> len;
	for (int i = 1; i <= n; i ++) cin >> x[i];
	for (int i = 1; i <= n; i ++) cin >> t[i];
	x[n + 1] = len;
	for (int i = 0; i <= n; i ++)
		for (int j = 0; i + j <= n; j ++)
			for (int k = 0; k <= i + j; k ++)
				f[i][j][k][0] = f[i][j][k][1] = INF;
	f[0][0][0][0] = f[0][0][0][1] = 0;
	for (int s = 0; s <= n; s ++)
		for (int i = 0; i <= s; i ++) {
			int j = s - i;
			for (int k = 0; k <= s; k ++)
				for (int p = 0; p < 2; p ++) {
					LL now = f[i][j][k][p];
					if (now == INF) continue;
					ans = max(ans, k);
					if (s == n) continue;
					LL a = now + (p == 0 ? x[i + 1] - x[i] : len - x[n - j + 1] + x[i + 1]);
					LL b = now + (p == 0 ? x[i] + len - x[n - j] : x[n - j + 1] - x[n - j]);
					int u = k + (a <= t[i + 1]), v = k + (b <= t[n - j]);
					f[i + 1][j][u][0] = min(f[i + 1][j][u][0], a);
					f[i][j + 1][v][1] = min(f[i][j + 1][v][1], b);
				}
		}
	cout << ans << "\n";
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) solve_case();
	return 0;
}

7. 常见错误方向

• 最近点优先、最早截止优先，甚至取几种贪心结果的最大值，都会忽略当前折返对后续整片点的影响。
• 向前看固定少数步仍只是一种局部优化，关键收益可能发生在前瞻范围之外。
• 只允许固定少量折返，会遗漏需要更多次有效改变方向的方案。
• 只保留每个区间当前章数最多的路线，会丢失“当前少拿一些、但更早到达”的潜在选择；是否存在更强的状态简化需要完整证明，不能只看随机数据。
• 到达过期点就停止扩展，把“不能盖章”误读为“不能经过”。样例 1 中第 2 个点已经体现了这一区别。
• 写成 $arrival<T_i$ 会漏掉恰好截止时刻到达的合法印章。

一个具体的丢状态反例是 $L=175$、$N=6$：

编号	1	2	3	4	5	6
$X_i$	7	10	150	154	155	164
$T_i$	33	32	60	57	63	13

顺时针经过 1、2 号，再逆时针经过 6、5 号时，可以在时刻 40 到达 5 号，取得 3 枚章（6 号已过期）；继续到 4、3 号分别为时刻 41、45，可以共取得 5 枚章。但同一探查区间、同一端点也存在时刻 62 到达且已经取得 4 枚章的路线：先去 6 号，再去 1、2 号，最后到 5 号。若只因“当前 4 枚比 3 枚多”就保留后者，后面的 4、3 号均已过期，最终反而只能得到 4 枚。

固定两次折返同样不够。例如 $L=11$，坐标为 $1,2,8,10$，截止时刻依次为 $3,12,7,1$。依次到达坐标 $10,1,8,2$，到达时刻为 $1,3,7,12$，可以取得全部 4 枚章，但需要三次改变方向。

赛时应先识别两端扩展模型，再根据 $N$ 小或截止时间小选择搜索与时间 DP；完整解的关键是把章数移入状态，而不是加入更高级的数据结构。