A. 旅游：把过道映射成一个位置

两张车票，回答四个问题：同车厢、同排、同侧、相邻。

四问是嵌套的。不同车厢，后面三问必然全假；不同排，后两问必然全假。所以输出只有 0000、1000、1100、1110、1111 五种，不可能有别的。代码一路短路下去就行。

坑全在座位排布上。A B C | D F，C 和 D 中间是过道，不相邻。样例 3 就是考这个：01C 和 01D 输出 1100，第三问 1，第四问 0。

还有一个细节，右侧只有 D 和 F，没有 E。如果按字母表顺序算距离，D 和 F 差 2，会被判成不相邻。

我用了一个很省事的写法，把字母映射到一个虚拟的物理位置上：

A → 0，B → 1，C → 2，D → 4，F → 5

过道占掉 3 号位。这样 C 和 D 差 2，不相邻；D 和 F 差 1，相邻。一个映射同时解决了「过道」和「没有 E」两件事。

int pos(char c) {    if (c == 'A') return 0;    if (c == 'B') return 1;    if (c == 'C') return 2;    if (c == 'D') return 4;    return 5;              // 'F'}

四问就这几行：

bool car  = strcmp(c1, c2) == 0;bool row  = car && s1[0] == s2[0] && s1[1] == s2[1];bool L = s1[2] <= 'C', R = s2[2] <= 'C';bool side = row && (L == R);bool adj  = side && abs(pos(s1[2]) - pos(s2[2])) == 1;

车厢号和座位号都是定长两位，直接比字符串，不用转数字。

这题我后来穷举了全部合法的车票对做验证，182 万组，答案确实只有那五种图案。

B. 回文串：指针走段，不走字符

S 被压成 n 段，第 i 段是 a_i 个字符 c_i。总长度能到 2×10^14，展开必死。

不用展开。双指针，只不过指针走的是段，不是字符。

左右各指一段，各自还有 remL、remR 个位置没配。每次取 t = min(remL, remR)。两段字符不同就加上 t，相同就跳过。然后两边各扣掉 t，谁扣到 0 就换下一段。

int i = 0, j = n - 1;long long remL = a[0], remR = a[n - 1], ans = 0;while (i < j) {    long long t = min(remL, remR);    if (c[i] != c[j]) ans += t;    remL -= t;    remR -= t;    if (remL == 0) { ++i; remL = a[i]; }    if (remR == 0) { --j; remR = a[j]; }}

退出时 i 和 j 最多停在同一段上，这段是自己跟自己配对，字符必然相同，不用再算。

拿样例 1 走一遍，aabbc 三段：2 个 a、2 个 b、1 个 c。

左边 remL=2，字符 a；右边 remR=1，字符 c。t=1，字符不同，ans=1。左边还剩 1，右边这一段空了，j 挪到 b 那一段，remR=2。

再取 t=min(1,2)=1，a 和 b 不同，ans=2。左边空了，i 也挪到 b 那一段。现在 i 和 j 都指在第二段，循环结束。

答案 2，和题面一致。

这题有三个坑。

第一个，答案会爆 int。最大约 7.2×10^13，得开 long long。我做了个用 int 的错解，能拿 80 分，丢的两组都在满规模数据上。

第二个，不能一对不匹配的段只算 1 次。段长 10^9 的时候，一次不匹配就是 10^9 个位置要改。这个错解 36 分。

第三个，不能直接拿第 k 段配第 n-1-k 段。段边界不对齐，必须拆。比如左边 2 个 a 配右边 3 个 a，剩下的 1 个 a 还要跟下一段接着配。这个错解能拿 48 分，比前两个都高。

样例里三段都很短，不拆也能过，所以第三点最容易漏。

C. 按位与：从高位往下确定

选恰好 m 个数，让按位与最大。

先排除一个错法：取最大的 m 个数。24、23、22 里取 2 个，最大的是 24 和 23，24 & 23 = 16；但 23 & 22 = 22，反而更大。

正确做法是逐位确定，从第 29 位往第 0 位扫。

为什么从高位往下？因为高位的一个 1，比低位全加起来还值钱。2^29 就比 2^0 到 2^28 的和（也就是 2^29−1）大。所以只要高位能保住，低位牺牲多少都划算，这个顺序不能反。

维护已经确定的掩码 mask。试 cand = mask | (1 << b)，数一数有多少个 a_i 满足 (a_i & cand) == cand。个数不少于 m，这一位就要得起，mask = cand；否则这一位放弃。

为什么是「不少于 m」而不是「恰好 m」？因为够 m 个数包含 cand 的所有位，从这些数里随便挑 m 个，按位与出来一定还带着 cand 这些位。多出来的数不碍事。

int mask = 0;for (int b = 29; b >= 0; --b) {    int cand = mask | (1 << b);    int cnt = 0;    for (int x : a)        if ((x & cand) == cand) ++cnt;    if (cnt >= m) mask = cand;}

O(30n)，六百万次运算，两秒很宽裕。

这题我还试了两个错法。从低位往高位贪心，得到的是最小的合法值，45 分。把条件写成 cnt == m 更亏，只有 20 分，因为「多于 m 个」的情况全被判死了。

D. 纸牌游戏：一条链

这题是全卷最难的。n 局，每局从第 i 张重放，暴力 O(n²)。n 到 5×10^5 的时候是 2.5×10^11 次操作，想都不用想。

先别想每局怎么算，先想一局打完桌面长什么样。

设 L(v) 是点数 v 最后一次出现的位置。

第 i 局第一张打的是 a_i。如果 a_i 在后面还出现过，这张压在底下的牌迟早被清掉：后面来一张 a_i，收牌规则会把桌面上这个点数以及它右边的东西全收走，桌面只剩新的那张 a_i。这一下之后，局面和从 L(a_i) 开始的一局完全一样。

如果 a_i 就是最后一次出现，它永远不会被收走，会一直躺在桌面上。这局的桌面就是 a_i 加上「从 i+1 开始那局的桌面」。

所以每局都能写成一条链：

从 p = i 出发，每一步看 a_p。p 就是 L(a_p) 的话，p 变成 p+1；否则 p 跳到 L(a_p)。

链上经过的那些 a_p，就是留在桌面上的点数，重复的只算一张。

拿样例 2 走一遍。a = 3 1 2 1 3 2 3 1 2 1，L(1)=10，L(2)=9，L(3)=7。第 1 局从 p=1 出发，a_1=3 不是最后一次出现，跳到 7；a_7=3 是最后一次，走到 8；a_8=1 不是最后一次，跳到 10；a_10=1 是最后一次，走到 11，结束。取出 3、3、1、1，去重是 {3, 1}，跟手算对得上。

这里有个关键点。

一个点数 v 在不在某局的桌面上，只看 L(v) 在不在那条链上。

因为链一旦碰到某个 a = v 的位置 p：如果 p < L(v)，下一步必然跳到 L(v)；如果 p 就是 L(v)，下一步走到 L(v)+1，之后再也不会出现 v。两种情况下，「v 出现过」和「L(v) 被经过」是同一件事。

所以 ans[v] 就是「有多少局出发的链经过了 L(v)」。

设 f[p] 是经过位置 p 的起始局数。链严格往前走，下一步不是 p+1 就是大于 p 的 L(a_p)，所以按 p 从小到大推：

f[p] = 1 + 所有「下一步是 p」的位置的 f 之和

那个 1 是 i = p 这一局自己。

vector<long long> f(n + 2, 0);for (int p = 1; p <= n; ++p) {    f[p] += 1;    int nxt = (p == last[a[p]]) ? p + 1 : last[a[p]];    f[nxt] += f[p];}for (int v = 1; v <= m; ++v)    printf("%lld ", f[last[v]]);

O(n + m)。

写到这里我得说件事。这题我第一版正解是错的。

当时写的是「从右往左维护一个桌面栈，弹出的时候结算一段区间」。看着挺像标准做法，样例 1 也过了。样例 2 输出 10 3 4，正确答案是 10 3 3。

我拿逐局重放的暴力才找出问题：那套递推其实等价于把牌倒着发，方向整个反了。

这种错最难查的地方在于样例 1 太短。a = 1 2 1 3，一共四张牌，正着发和倒着发凑巧对得上。

所以现在我的习惯是，遇到这种「能暴力、但暴力会超时」的题，先把 O(n²) 的重放写出来，小数据对拍，确认递推方向对了，再去优化复杂度。这次就是靠它把方向问题揪出来的。

扫码添加助教老师微信，获取更多信奥信息

⬇️扫码咨询详情⬇️