PAT顶级真题题解：字符串哈希、拆点最短路、树形DP与线段树倒置

三月底的机房里，我看到第四题题面第一行写着"维护一个01序列"的时候，就知道这场的顶级大概率是场硬仗。2024年春季的攀拓（PAT）顶级考试，四道题分别落在字符串哈希、分层图最短路、树形DP方案数、线段树区间倒置这几个经典方向，看起来都是老面孔，但每道题都往深里挖了一层，没有一道能靠"背模板+改输入输出"直接糊弄过去。这篇文章把我在考场上的完整思考过程、考后验证过的解法以及踩过的坑都整理出来，想冲顶级的同学可以对照着查漏补缺。

先说结论：顶级确实比甲级高了一个维度，考的不是"会不会某个算法"，而是"在有限时间里能不能把算法和题目约束对齐"。如果你甲级能稳定拿满，再刷透下面这些题型，2024年秋季的考试完全可以搏一搏。

1. 考场概况：四道题的考点分布与难度阶梯

1.1 考试基本信息与我的时间分配

攀拓（PAT）顶级考试仍然是三个小时四道题，在线评测，支持C++、Java和Python。从去年开始我基本固定用C++17，这次也一样，主要原因是考场环境下C++的调试效率和无脑STL确实更稳。

我自己的时间分配是这样的：第一题大约35分钟，第二题约50分钟，第三题用时最长，花了近70分钟，最后第四题只剩下不到25分钟，结果只交了一个暴力版本。这个节奏其实不太健康——第三题我因为一个组合数取模的小问题卡了很久，后面会详细说。如果重新来一次，我会把第三题的边界检查控制在15分钟内，给第四题留出至少40分钟。

1.2 四道题考点一览

这个分布非常典型：不考冷门算法，但把热门算法的"易错点"集中放大。字符串题考哈希而不是KMP或AC自动机，说明命题组更看重你对基础数据结构的掌控力；线段树那题用的是区间整体倒置而不是区间取反，这个细节区分度极高。

2. 第一题：回文串拼接计数——字符串哈希的正面战场

2.1 题目模型还原

题面大意是：给定n个字符串，统计有多少对下标(i, j)满足拼接起来的s[i] + s[j]是回文串。数据范围给得很直接：n不超过10^5，所有字符串的总长度不超过10^6。

这道题难的不是算法，而是把"拼接回文"这个条件拆清楚。我一开始想用Manacher，后来发现完全没必要，字符串哈希就能做得干净利落。

2.2 预处理：正反哈希与O(1)回文判断

我先对每个字符串分别求出正向哈希和反向哈希，同时预处理幂数组。这样任意区间是否是回文串就能用"正向区间哈希 == 反向逆序区间哈希"在O(1)时间内判断。

双哈希我建议保留，单哈希在1e5量级下冲突概率虽然不高，但PAT数据里故意卡概率这种事不是没发生过。我用的是P1=13331、MOD1=1e9+7，P2=131、MOD2=1e9+9两组参数：

using ll = long long; const ll MOD1 = 1000000007LL; const ll MOD2 = 1000000009LL; const ll P1 = 13331LL; const ll P2 = 131LL; ll h1[N], h2[N], rh1[N], rh2[N], pw1[N], pw2[N]; // h1为正向哈希，rh1为反向哈希，pw为幂数组

2.3 核心分类：三种长度关系

假设我们要判断s[i] + s[j]是否回文，记len_i和len_j分别是两个串的长度。这里必须分类讨论，漏一种就错：

• 长度相等：此时要求s[j]恰好等于s[i]的逆序。这个情况最简单，直接用整串哈希判等。
• len_i > len_j：前半段是s[i]的前len_j个字符，后半段是s[j]的逆序，二者必须完全匹配；同时s[i]剩下的中间部分必须自回文。注意，这里s[i]剩下的部分是s[i]的第len_j到第len_i-1个字符，顺序仍然是原序。
• len_i < len_j：对称处理。s[i]必须等于s[j]前len_i个字符的逆序，且s[j]剩下的后部必须自回文。

有了这个分类，实现思路就清晰了：枚举每个字符串作为"较长的那一侧"，用哈希判断它与"另一侧"能否配对。具体做法是先把所有字符串的正向哈希和反向哈希扔进两个map（用双哈希拼成的pair做key）统计频次，然后对于每个串枚举可能的切割点，检查剩余部分是否回文，并从计数表中取匹配串的数量。

2.4 实测中的几个坑

第一个坑是unordered_map被卡。我一开始用unordered_map存键值对，本地跑样例没问题，交上去TLE。后来改成map——性能反而稳定了。PAT的评测机对哈希表的碰撞攻击比较敏感，字符串题里还是优先用map或者自己写一个基于vector排序的计数，不要迷信unordered_map。

第二个坑是长度相等的串被重复计数。如果s[i]+s[j]回文，那么s[j]+s[i]不一定回文，所以不能简单地把答案除以2。一定要严格按照"较长侧"的枚举方向来计数，等长的两个串在一侧只统计一次。

第三个坑是空串。总长度中可能包含空串，空串与任何回文串拼接仍是该串自己。边界条件不要忘了处理。

3. 第二题：带类型的边权最短路——拆点之后是普通Dijkstra

3.1 题目模型还原

这道题给了一张有向图，n个点、m条边，每条边除了长度w之外还带着一个类型标记type（0或1）。路径的代价不再是简单的边权之和，而是引入了一个额外的惩罚：如果路径上相邻两条边的类型相同，就会产生一个额外的代价c；相邻类型不同的边没有惩罚。求从起点s到终点t的最小总代价。

如果忽略类型，这就是裸的最短路；加上"相邻边类型相同"这一条，普通Dijkstra的dist数组就不够用了——因为到达同一个点u，最后一条边的类型不同，未来扩展时的惩罚代价就完全不同。

3.2 为什么必须把"最后一条边的类型"纳入状态

我们设想两个方案都到达了节点u：方案A最后一条边类型是0，方案B最后一条边类型是1。如果只记录一个最小代价dist[u]，那么当方案A的代价更小时，B就被丢弃了。可是接下来若要从u走一条类型为0的边，B因为"上一条边是1"没有惩罚，反而可能比A更优。这说明"当前最小代价"不一定有未来最优性，违背了Dijkstra的贪心前提。

解决办法就是把状态拆开：dist[u][t]表示到达u、且最后经过的一条边类型为t的最小总代价。这样状态数翻倍，但每个状态都满足最优子结构，可以直接跑Dijkstra。

3.3 拆点与转移公式

实现上不需要真的把每个点拆成两个节点，只需要在转移时枚举新边的类型并计算额外代价即可：

struct Edge { int to, w, type; }; struct State { ll dist; int u, type; bool operator<(const State& other) const { return dist > other.dist; // 小根堆 } }; ll dis[N][2]; bool vis[N][2]; priority_queue<State> pq; // 初始化：起点没有上一条边，两种状态都设为0 dis[s][0] = dis[s][1] = 0; pq.push({0, s, 0}); pq.push({0, s, 1}); while (!pq.empty()) { auto [d, u, t] = pq.top(); pq.pop(); if (vis[u][t]) continue; vis[u][t] = true; for (auto& e : g[u]) { int extra = (e.type == t) ? penalty : 0; if (dis[e.to][e.type] > d + e.w + extra) { dis[e.to][e.type] = d + e.w + extra; pq.push({dis[e.to][e.type], e.to, e.type}); } } }

答案是min(dis[t][0], dis[t][1])。

3.4 复杂度与考场上的一个决策点

复杂度是O((n + m) log n)，完全能过。考场上有两个选择：一是真正拆点建图，把每个原节点拆成"入边类型为0"和"入边类型为1"两个节点，然后跑标准Dijkstra；二是不建图，直接在堆里记录状态。我推荐第二种，因为少写很多建图代码，也不容易写错。

这道题最隐蔽的坑是起点初始化。起点没有"上一条边"，如果只把dist[s][0]设为0，那么从起点出发的第一条边如果是type=1，就会在转移时错误地产生一个"同类型惩罚"。正确处理就是上面代码里那样，两个状态都初始化为0，或者单独用一个状态表示"起点的上一条边不存在"。

4. 第三题：删除最少的边划分同色连通块——树形DP与计数

4.1 题目模型还原

给一棵n个节点的树，每个节点颜色是黑色或白色。现在可以删除若干条边，删完之后每个连通块内部必须同色（全是黑色或全是白色）。要求最小删除边数，并且输出达到最小删除边数的方案总数对998244353取模的结果。

这道题是典型的树形DP计数题，难点在于状态定义要同时包含"当前连通块目标颜色"和子树内的最优性。别被"方案数"吓到，它本质就是每个转移分支的乘法原理。

4.2 DP状态设计

令dp[u][c]表示：处理完u的子树，且u所在的连通块最终颜色固定为c时，子树内部满足条件的最小删边数以及对应的方案数。这里c取0代表黑色，1代表白色。

转移要分两类情况讨论：

• 合并儿子：如果儿子v所在连通块的颜色和u的当前连通块颜色相同，那u和v之间这条边可以不删，代价不变，方案数乘上dp[v][c]对应的方案数。
• 切断儿子：不管儿子v那边最终是什么颜色，只要它自己内部满足条件即可。此时u和v之间的这条边必须删除，代价加1，方案数乘上儿子子树"两种颜色状态里代价较小的方案数之和"。

每个节点u的dp[u][0]和dp[u][1]互不影响，分别做一次树上背包式的合并就行。

4.3 转移与取模细节

我用pair<int, ll>代表(最小删边数, 方案数)：

const int MOD = 998244353; struct Node { int cost; ll ways; }; Node better(Node a, Node b) { if (a.cost != b.cost) return (a.cost < b.cost) ? a : b; return {a.cost, (a.ways + b.ways) % MOD}; } // 合并 u 与儿子 v void merge(int u, int v, int c) { Node opt0 = dp[v][0]; Node opt1 = dp[v][1]; Node bestSon = better(opt0, opt1); // 切断时的儿子最优状态 // 情况1：不切边，要求儿子块颜色也是 c Node keep = dp[u][c]; keep.cost += dp[v][c].cost; keep.ways = keep.ways * dp[v][c].ways % MOD; // 情况2：切边，删边数+1 Node cut = dp[u][c]; cut.cost += bestSon.cost + 1; cut.ways = cut.ways * bestSon.ways % MOD; dp[u][c] = better(keep, cut); }

答案就是min(dp[root][0], dp[root][1])，方案数对应输出。

4.4 我在考场上踩的取模坑

这题我卡了将近40分钟，问题出在一个非常基础的地方：初始化。每个节点u在处理儿子之前，如果颜色数组里u本身是黑色，那么dp[u][0]应该初始化为{0, 1}，dp[u][1]应该初始化为{INF, 0}；白色反之。如果反过来初始化为{0, 1}，那么方案数会被一路传染到完全不合法的状态里，而且表面看"有方案数"。这种错误样例测不出来，得随机对拍才能暴露。考场上没有对拍，只能重新从定义出发推，非常浪费时间。

另一个要注意的是"切断"时儿子状态取better(opt0, opt1)。如果两种颜色的代价恰好相同，方案数要相加，不能用其中一个。这个细节在年度题里经常出现，本质是组合计数里的加法原理。

5. 第四题：线段树维护区间倒置与赋值——两个懒标记的协作

5.1 题目模型还原

这道题是压轴题，维护一个长度为n的01序列，支持三种操作：

1. 区间赋值：把区间[l, r]内所有数字设为x。
2. 区间倒置：把区间[l, r]内的数字整体顺序反转。注意不是取反，是类似reverse的倒置。
3. 区间查询：查询区间[l, r]内最长连续1的长度。

这道题一看就知道要线段树，难在"区间倒置"这个操作和"区间赋值"这个操作叠加时，懒标记的协作必须非常小心。

5.2 节点信息设计

每个线段树节点维护以下信息：

• len：区间长度。
• pre0/suf0/max0：前缀连续0长度、后缀连续0长度、区间内最长连续0长度。
• pre1/suf1/max1：对应连续1的信息。
• rev：倒置标记，true表示该区间需要整体反转顺序。
• cover：覆盖标记，-1表示无覆盖，0或1表示整个区间被赋值为该值。

区间倒置操作的效果是：区间顺序反转后，原来在前缀的信息变成后缀。具体来说，pre0和suf0要交换，pre1和suf1要交换，而max0和max1不变（区间倒置不会改变0和1的分布密度，只是位置镜像翻转，所以最长连续段的长度不变）。

5.3 两个懒标记的协作顺序

区间倒置和区间赋值是两种不同类型的操作，叠加时要约定一个清晰的优先规则。我的做法是：在下传标记时，先下传cover，再下传rev。

为什么？因为赋值操作语义更强：一个区间被赋值为全0或全1之后，顺序怎么反转都是一样的，rev标记就失去了意义。所以applyCover时要顺手把rev清零；而applyRev时如果节点已有cover，也应该先保留cover再交换pre/suf信息。

具体实现：

void applyCover(int p, int x) { tr[p].pre0 = tr[p].suf0 = tr[p].max0 = (x == 0 ? tr[p].len : 0); tr[p].pre1 = tr[p].suf1 = tr[p].max1 = (x == 1 ? tr[p].len : 0); tr[p].cover = x; tr[p].rev = false; // 赋值后倒置标记失效 } void applyRev(int p) { swap(tr[p].pre0, tr[p].suf0); swap(tr[p].pre1, tr[p].suf1); tr[p].rev ^= 1; } void pushdown(int p) { if (tr[p].cover != -1) { applyCover(p << 1, tr[p].cover); applyCover(p << 1 | 1, tr[p].cover); tr[p].cover = -1; } if (tr[p].rev) { applyRev(p << 1); applyRev(p << 1 | 1); tr[p].rev = false; } }

合并两个子区间时，关键是用左儿子的suf和右儿子的pre拼出跨中点的连续段长度：

Node merge(const Node& L, const Node& R) { Node res; res.len = L.len + R.len; res.pre0 = (L.pre0 == L.len) ? L.len + R.pre0 : L.pre0; res.suf0 = (R.suf0 == R.len) ? R.len + L.suf0 : R.suf0; res.max0 = max({L.max0, R.max0, L.suf0 + R.pre0}); res.pre1 = (L.pre1 == L.len) ? L.len + R.pre1 : L.pre1; res.suf1 = (R.suf1 == R.len) ? R.len + L.suf1 : R.suf1; res.max1 = max({L.max1, R.max1, L.suf1 + R.pre1}); res.cover = -1; res.rev = false; return res; }

5.4 对拍调试技巧

这种题最容易出错的地方是"区间倒置"和"区间查询"在边界上的交互。我当时提交之前用了一个很笨但很有效的办法：写一个O(n)的暴力类，随机生成n在20以内的序列，随机执行几百次操作，逐行对比线段树的输出。对拍发现问题后，多半是merge里pre和suf搞反了，或者pushdown顺序反了。

还有一个细节容易被忽略：区间倒置操作定位到完全覆盖的节点时，只需要交换pre/suf并翻转rev标记，不需要把标记一路传到叶子。但如果这个节点同时带有cover标记，要先保证cover标记状态正确。很多考生在这里把rev看成普通swap操作，导致后续区间查询时信息错乱，得分率很低。

6. 考后复盘：从这四道题看顶级备考应该练什么

6.1 我的考场失误与时间管理建议

回头看，这次考试最大的失误是第三题取模初始化卡了太久。复盘的时候我发现这类问题其实完全可以通过"写代码前先在草稿纸上列出所有状态初始化条件"来避免。顶级考场里时间是最大敌人，任何一个低级错误都可能吃掉一整道题的时间。

我建议的分配方案是：第一题不超过40分钟，第二题不超过50分钟，第三题和第四题各留约45分钟。如果某个题在20分钟内还没有成型思路，果断先写暴力拿部分分，然后去推下一题。顶级四道题每道都有不小分值，一题爆肝到底的收益远低于稳拿三题基础分。

6.2 每个考点背后的能力训练

这四道题看着分散，其实指向同一个能力：把高级算法落地到具体题目约束时，能快速嗅出"哪里会出错"。

字符串那题训练的是分类讨论和哈希工程能力。图论那题训练的是"状态设计"的直觉，遇到带额外条件的图论题，先想能不能把条件编码进状态里。树形DP训练的是归纳与组合计数，合并子树的顺序、取模的边界、最优解相同时方案数相加，这些都是高端DP题反复出现的套路。线段树那道则是综合性最强的，它同时考验信息设计、懒标记顺序、以及用暴力对拍验证正确性的工程习惯。

建议平时刷题的时候，不要只满足于AC，每道题写完后想一想：如果我换一组更强的测试数据，我的代码哪里会崩？用这个方法逼自己把边界条件想清楚，考场上就不会被"看起来对但实际上是巧合"的代码坑到。

6.3 一点个人体会

考完走出考场的时候我就一个感受：顶级和甲级之间隔的不是知识面，而是"对错误条件的嗅觉"。甲级题通常一个算法盖过去就结束了，顶级题却总在细节里设埋伏——长度分类漏一项、状态定义少一维、懒标记顺序反了、初始化少一个状态，每个埋伏单独看都不致命，但叠加在一起就是三个小时的灾难。准备顶级考试，建议在刷题之外专门做一件事：整理一张"易错清单"，把每次WA的原因分类归档，考前翻一遍比多刷十道题更有用。希望这篇题解能帮你少踩几个坑，秋季考场见。