1. 赛题全貌这套题为什么值得一补再补2017 ACM ICPC Asia Shenyang Regional Contest 这套题在我刷过的区域赛题单里属于后劲很足的那一类。当时打完现场我只AC了6题排名中游偏上赛后花了三个晚上把能补的题补到10道也就是标题里写的 10 / 13。现在回头看这套题的题型分布非常典型既有I题这种看似白给、实际埋雷的签到题也有H题和C题这种让人卡到怀疑人生的硬核题。如果你正在准备区域赛或者想找一套题来检验自己的知识盲区这套题很适合拿来当试金石。我先把整套题的类型和难度按个人体感列个表方便你对照自己的情况安排刷题顺序。题号题目核心考点个人难度评估ABBP Formula数学、精度处理难BBridge图论、仙人掌图难CEmpty Convex Polygon计算几何、DP中难DDefense of the Ancients博弈/DP中难EFive-round Show Hand大模拟中FHeron and His Triangle数学递推、高精度中GInfinite Fraction PathBFS剪枝、字符串中HLegen...AC自动机、矩阵快速幂难ILittle Boxes整数溢出陷阱易JLovers线段树、懒标记中KMahjong大模拟中难LTree树结构、DP中难MWandering Robots随机游走、平稳分布中易现场比较理想的做题顺序是先快速收掉 I、E、M 三题然后进入 F、G、J 的分水岭阶段。F 和 G 属于想通了解法很简单想不通就卡死的类型大部分队伍的时间都耗在这里。H 和 C 是金牌区题目铜牌队伍基本不指望但赛后必须补因为这两题背后的模型非常通用。2. 白给题里也有坑I题与M题的解题思路2.1 I - Little Boxes四个2的幂相加为什么全场WA声一片I题题意极短给你四个整数 a、b、c、d每个数都是 2 的幂求它们的和。看到这个题的第一反应就是a b c d直接输出签到题嘛我一开始也这么写的然后交上去就是一个罚时。问题出在数据范围上。四个数最大都可以取到 2^62四个 2^62 相加等于 2^64而 C 里unsigned long long的最大值是 2^64 - 1刚好差 1直接溢出成 0。也就是说如果你用unsigned long long存答案不出 bug 才怪。我当时现场改成了__int128#include bits/stdc.h using namespace std; void print128(__int128 x) { if (x 0) { cout 0 endl; return; } string s; while (x 0) { s.push_back(char(0 x % 10)); x / 10; } reverse(s.begin(), s.end()); cout s endl; } int main() { int T; cin T; while (T--) { __int128 a, b, c, d; // 实际读入时按字符串或 unsigned long long 读都行 // 这里省略具体读入重点是求和用 __int128 __int128 ans a b c d; print128(ans); } return 0; }这题的教训很实在看到2的幂就要条件反射去算边界。2^62 × 4 恰好是 2^64这是出题人故意设计的陷阱。用__int128是现场最稳的做法如果是 Python 选手直接用 Python 的 int 就行根本不存在溢出问题。算法竞赛里这种签到题里埋溢出雷的套路几乎每年都有I题属于最典型的一例。2.2 M - Wandering Robots随机游走的平稳分布答案其实是度数占比M题看起来是个概率题一个 n×n 的网格上有一个机器人每一步从当前格子等概率移动到相邻的非障碍格子网格里有一些障碍n 可以非常大障碍数量 k 相对很小。问经过足够长时间后机器人停留在某个区域具体是右下角相关的一个区域的概率。第一反应是列状态转移矩阵做马尔可夫链但 n 如果到 1e9 级别矩阵根本开不下。这里的关键结论是在一个无向连通图上做随机游走平稳分布与每个点的度数成正比。也就是说经过无限长时间后机器人停在点 v 的概率是π(v) deg(v) / Σ deg(u)其中 deg(v) 是 v 的可走邻居数量分母对所有非障碍点求和。这个结论不需要真的去迭代概率它是马尔可夫链理论里的基本定理。有了这个公式题目就变成了一个计数问题计算右下角目标区域里所有点的度数之和再除以整张图所有可达点的度数之和。n 很大但不能暴力遍历所有点好在障碍只有 k 个度数异常的点只出现在障碍周围和网格边界附近内部点的度数全部是 4。所以只需要把障碍周边的一圈点拿出来特殊处理其余部分用公式直接计数。这题的转化思路在区域赛里很有代表性看到随机游走先想平稳分布而不是直接上概率DP。很多队伍在这里浪费了大量时间写状态转移实际上只需要几十行代码就能过。3. 两道分水岭F题的Pell递推与G题的BFS剪枝3.1 F - Heron and His Triangle海伦公式推出Pell递推F题说的是三边长为 t-1、t、t1 的三角形如果面积是整数就把 t 称为一个合法值。给定一个很大的 n求不小于 n 的最小合法 t。先做数学推导。根据海伦公式半周长 p 3t/2面积 S 满足S² p(p - (t-1))(p - t)(p - (t1)) (3t/2) × ((t2)/2) × (t/2) × ((t-2)/2) 3t²(t² - 4) / 16要让 S 是整数关键在于 3(t² - 4) 需要是一个完全平方数。整理后会发现这其实是一个 Pell 方程解出来的 t 满足非常漂亮的递推关系t₁ 4, t₂ 14, tₙ 4 × tₙ₋₁ - tₙ₋₂前几项是 4、14、52、194、724…… 验证一下t 4 时三边是 3、4、5面积 6是整数t 14 时三边是 13、14、15面积 84t 52 时三边是 51、52、53面积 1170。全都符合。现场我推到这个递推之后发现 n 最大可以到 10^30 级别C 的long long完全不够用。我当时直接用 Python 预处理出一张表然后二分查找答案。比赛时如果允许用 Python 交题这是最省事的方案如果只能用 C就得手写高精度加法乘法或者用__int128先跑再看会不会爆——实际上一百多项就会超过 10^30手写大数也不难。这题的核心价值在于把几何问题转化为数论递推。看到海伦公式不要慌先把表达式化简再观察是否落入 Pell 方程的套路。区域赛的数学题经常这样题目包装成几何内核是数论。3.2 G - Infinite Fraction Path多源BFS的去重剪枝G题题意很有意思给一个长度为 n 的数字串 s只含 0-9从每个位置 i 出发下一步会走到 (i² 1) mod n 这个位置。这样从任意位置出发沿着边一直走就能得到一个无限长的数字序列。要求字典序最大的起始位置如果有多个输出下标最小的。这题的本质是每个点只有一条出边所以整张图是若干个一个环加若干棵树的函数图。我需要从这个函数图中找一条字典序最大的无限路径。最简单的想法是第一轮把所有 s[i] 最大的位置加入候选集合。然后每一轮从当前所有候选位置往后走一步比较下一步位置的数字只保留下一步数字最大的那些候选。如果两个候选走到了同一个位置它们后续的路径就完全一样了可以合并成一个这个入度去重是算法能跑得动的关键。这个剪枝的复杂度近似 O(n log n)因为每个点最多被入队一次。我用一个队列模拟多源BFS每层处理时记录当前层的最大字符只有字符等于最大值的那些节点才能进入下一层。现场我刚开始写了个朴素的按层扩展没有去重结果在 n 1e5 的数据上直接超时。加上vis数组去重之后瞬间降到几十毫秒。vectorint cand, nxt; int global_max -1; bool vis[N]; // 第一轮加入所有最大字符的位置 // 每次扩展 while (true) { int best -1; for (int u : cand) { int v (1LL * u * u 1) % n; best max(best, s[v] - 0); } nxt.clear(); for (int u : cand) { int v (1LL * u * u 1) % n; if (s[v] - 0 best !vis[v]) { vis[v] true; nxt.push_back(v); } } cand nxt; if (cand.size() 1) break; // 如果跑满 n 轮还没结束说明后续完全一致取最小下标即可 }这里有个容易被忽略的点(i² 1) mod n在 i 是 int 时会溢出必须用1LL * i * i转成 long long 再取模。这个细节不贵但WA一次很影响心态。4. J题线段树区间“追加数字”操作背后的懒标记推导J题是这套题里最典型的数据结构板子换皮题维护一个数组支持区间操作——把区间内每个数字 x 变成 10x v也就是在十进制末尾追加一个数字 v以及区间求和。q 和 n 都可以到 1e5所以必须用线段树加懒标记。关键在于懒标记的合并方式。每个位置 x 经过一次操作会变成 10x v我把这种变换抽象成x mul × x add初始时 mul 1add 0。那么对一个节点整体做一次追加 v操作节点维护的区间和 sum 会变成sum 10 × sum v × len其中 len 是区间长度。因为区间内每个元素都乘以 10 再加 v所以总和就是原 sum 乘以 10再加上 v 乘以元素个数。接下来是懒标记本身的合并。如果一个节点已经有懒标记 (mul, add)现在要再叠加一层追加 v的操作那么整体变换是x → mul × x add → 10 × (mul × x add) v (10 × mul) × x (10 × add v)所以新的懒标记是mul mul × 10 add add × 10 v下传的时候同样要小心。父节点有个标记 (F_mul, F_add) 要传给子节点子节点原先有一个标记 (mul_c, add_c)合并后子节点的变换应该是先做子节点自己的变换再做父节点的变换x → mul_c × x add_c → F_mul × (mul_c × x add_c) F_add于是mul_c F_mul × mul_c add_c F_mul × add_c F_add同时子节点的 sum 也要更新成sum_c F_mul × sum_c F_add × len_c这题所有操作都在模意义下进行所以每次乘法和加法都要取模。我写的时候一度把合并顺序搞反先乘了 add 导致整棵线段树全是错的。这里有个记法懒标记跟函数复合是反着来的新标记作用在旧标记外面。你只要把x - mul*x add当作函数复合顺序就是先内层后外层不容易错。线段树题目的通病是思路三分钟调BUG三小时J题尤其明显。建议在本地写一个小数据生成器和暴力对拍一秒就能找出合并顺序的问题。5. 两枚硬骨头H题AC自动机加矩阵快速幂、C题空凸包DP5.1 H - Legen...把字符串问题转化为图上最长路H题是这套题的题面担当同时也是做法最贵的一道。题意概括起来就是要构造一个长度为 L 的字符串给定若干模式串每个模式串有一个权值构造出的字符串每出现一个模式串就获得对应权值模式串可以重叠求最大总权值。L 可以到 1e9所以任何线性 DP 都不可行。标准做法是 AC自动机 矩阵快速幂。先对所有模式串建 AC自动机把每个节点看作一个状态在节点 u 后面添加一个字符 c 会转移到一个新节点 v。走到 v 时能获得的权值等于 v 在 fail 树上所有祖先的权值之和——因为命中的模式串可能以 v 结尾也可能以 v 的 fail 祖先结尾。这样问题就变成了在一个状态图上走 L 步每走一步有一定收益求总收益最大值。状态数最多几百个但步数 L 是 1e9所以用矩阵快速幂优化。这里用的不是普通矩阵乘法而是 max-plus 矩阵乘法也就是把乘法换成加法、加法换成取 max。预处理转移矩阵的幂次后用向量乘矩阵的方式在 O(S² log L) 时间内求出答案S 是 AC自动机节点数。现场我们队在这题上卡了很久主要卡在fail 树上的权值累计这一步。建完 AC自动机后一定要把 fail 指针处理成 DAG然后从根往下累加权值否则每个节点只算了自己的权值重叠模式串的情况会漏掉。这题属于代码量不算特别大但对 AC自动机的理解深度要求很高的题值得在补题时完整写一遍。5.2 C - Empty Convex Polygon按极角序做凸包DPC题是要在给定点集中找一个面积最大的空凸包顶点是给定点但凸包内部不能包含任何其他给定点。n 不大大概几十个点但直接枚举凸包的所有组合是指数级的。一个比较经典的思路是把所有点按某个基准点做极角排序然后做一个凸包 DP。设 dp[i][j] 表示凸包的最后一条有向边是从 i 到 j 时凸包的最大面积。转移时枚举前一个点 k要求 k 在向量 i→j 的左侧并且三角形 k-i-j 内部不能有任何给定点。这个三角形内部为空的检查可以预处理。固定 i 和 j 后判断某个点 k 是否在三角形内部只要枚举所有点看是否在三角形内如果有点在内部则这条转移非法。暴力预处理是 O(n^4)但由于 n 只有几十优化到 O(n^3) 后非常快。最后答案取所有合法 dp[i][j] 的最大值。这题你光看题解会觉得道理很简单实际写起来全是细节极角排序的基准点选择、共线点的处理、三角形面积取绝对值、dp 的初始化值用负数还是 0。补这题的时候我建议直接用long double存坐标和面积避免浮点误差在边界数据上爆掉。区域赛的计算几何题基本不会太丧心病狂但精度细节一定要抠死。6. 模拟题和剩余题目怎么处理6.1 E题大模拟把牌型编码成可比较的整数E题是扑克牌比大小的模拟五张牌比牌型类似梭哈的规则。这种题没有任何算法难度拼的就是细心。我的建议是不要写一大堆if嵌套把所有信息压缩成一个可比较的结构。具体做法先把五张牌按点数排序然后统计每种点数的出现次数判断属于哪种牌型同花顺、四条、葫芦、同花、顺子、三条、两对、一对、散牌。每种牌型内部再比较关键牌的大小所以可以设计一个vectorint rank表示这个牌型在比较时的权重序列C 里vector直接支持字典序比较非常方便。比如两对的权重序列可以设计成{大对子点数, 小对子点数, 单牌点数}三条是{三条点数, 剩余最大单牌, 剩余次大单牌}。把所有牌型映射成一个牌型编号 权重序列的组合先比较牌型编号再比较权重序列。这样写出来逻辑清晰调试也快。现场很多队卡在 E 题不是不会做而是 if 写太多把自己绕晕了重构一遍反而几分钟就过。6.2 没补完的三题赛后我的判断标题说 10 / 13说明有三题我当时没有完整补出来。A 题 BBP Formula 是数学题需要处理无理数在十六进制下的逐位计算涉及高精度和浮点误差控制我赛后理解了大致的迭代公式但没有真正实现通过。B 题 Bridge 是仙人掌图上的路径问题需要先掌握圆方树我对这个模型的熟练度不够暂时放下。K 题 Mahjong 是一个麻将判断的大模拟规则细节非常繁琐我当时的精力不足以把整副牌的状态压缩写对。这三题如果之后有时间我会单独写一篇补题记录。不过从应付区域赛的角度来说把 C、F、G、H、J 这五题吃透比硬啃 A、B、K 性价比高很多——前者的模型在后续比赛中反复出现后三者更像是特定知识点的专项训练。7. 补完这套题之后的一些体会这套题最值得学习的地方是它把看似复杂的模型和极其朴素的结论结合得很好。M题的随机游走本质是稳态分布与度数成正比F题的面积整数问题本质是 Pell 方程G题的无限路径本质是函数图上的剪枝。这些题目如果只盯着表面看会觉得难到无从下手但一旦抓住底层模型代码量往往不超过一百行。我在补题时养成了一个习惯每道题补完把自己的推导过程压缩成三五行核心笔记比如F题 海伦公式 → Pell 递推 → 高精度表、G题 函数图 → 多源BFS → 入度去重。这样过几个月回头看一分钟就能复习完一道题。建议你也试试这个方法。另外说一个现场比赛的题外话I题那种溢出陷阱我和队友当时因为罚时懊恼了很久但赛后想想这恰恰是区域赛签到题最常见的出题逻辑——不是考你不会算加法而是考你有没有边界意识。平时刷题养成多问一句数据范围到极限时会发生什么的习惯能省下不少罚时。这套题补完我对这句话的体会比之前任何时候都深。
2017 ACM ICPC沈阳区域赛补题精讲：10/13题覆盖核心算法与陷阱
1. 赛题全貌这套题为什么值得一补再补2017 ACM ICPC Asia Shenyang Regional Contest 这套题在我刷过的区域赛题单里属于后劲很足的那一类。当时打完现场我只AC了6题排名中游偏上赛后花了三个晚上把能补的题补到10道也就是标题里写的 10 / 13。现在回头看这套题的题型分布非常典型既有I题这种看似白给、实际埋雷的签到题也有H题和C题这种让人卡到怀疑人生的硬核题。如果你正在准备区域赛或者想找一套题来检验自己的知识盲区这套题很适合拿来当试金石。我先把整套题的类型和难度按个人体感列个表方便你对照自己的情况安排刷题顺序。题号题目核心考点个人难度评估ABBP Formula数学、精度处理难BBridge图论、仙人掌图难CEmpty Convex Polygon计算几何、DP中难DDefense of the Ancients博弈/DP中难EFive-round Show Hand大模拟中FHeron and His Triangle数学递推、高精度中GInfinite Fraction PathBFS剪枝、字符串中HLegen...AC自动机、矩阵快速幂难ILittle Boxes整数溢出陷阱易JLovers线段树、懒标记中KMahjong大模拟中难LTree树结构、DP中难MWandering Robots随机游走、平稳分布中易现场比较理想的做题顺序是先快速收掉 I、E、M 三题然后进入 F、G、J 的分水岭阶段。F 和 G 属于想通了解法很简单想不通就卡死的类型大部分队伍的时间都耗在这里。H 和 C 是金牌区题目铜牌队伍基本不指望但赛后必须补因为这两题背后的模型非常通用。2. 白给题里也有坑I题与M题的解题思路2.1 I - Little Boxes四个2的幂相加为什么全场WA声一片I题题意极短给你四个整数 a、b、c、d每个数都是 2 的幂求它们的和。看到这个题的第一反应就是a b c d直接输出签到题嘛我一开始也这么写的然后交上去就是一个罚时。问题出在数据范围上。四个数最大都可以取到 2^62四个 2^62 相加等于 2^64而 C 里unsigned long long的最大值是 2^64 - 1刚好差 1直接溢出成 0。也就是说如果你用unsigned long long存答案不出 bug 才怪。我当时现场改成了__int128#include bits/stdc.h using namespace std; void print128(__int128 x) { if (x 0) { cout 0 endl; return; } string s; while (x 0) { s.push_back(char(0 x % 10)); x / 10; } reverse(s.begin(), s.end()); cout s endl; } int main() { int T; cin T; while (T--) { __int128 a, b, c, d; // 实际读入时按字符串或 unsigned long long 读都行 // 这里省略具体读入重点是求和用 __int128 __int128 ans a b c d; print128(ans); } return 0; }这题的教训很实在看到2的幂就要条件反射去算边界。2^62 × 4 恰好是 2^64这是出题人故意设计的陷阱。用__int128是现场最稳的做法如果是 Python 选手直接用 Python 的 int 就行根本不存在溢出问题。算法竞赛里这种签到题里埋溢出雷的套路几乎每年都有I题属于最典型的一例。2.2 M - Wandering Robots随机游走的平稳分布答案其实是度数占比M题看起来是个概率题一个 n×n 的网格上有一个机器人每一步从当前格子等概率移动到相邻的非障碍格子网格里有一些障碍n 可以非常大障碍数量 k 相对很小。问经过足够长时间后机器人停留在某个区域具体是右下角相关的一个区域的概率。第一反应是列状态转移矩阵做马尔可夫链但 n 如果到 1e9 级别矩阵根本开不下。这里的关键结论是在一个无向连通图上做随机游走平稳分布与每个点的度数成正比。也就是说经过无限长时间后机器人停在点 v 的概率是π(v) deg(v) / Σ deg(u)其中 deg(v) 是 v 的可走邻居数量分母对所有非障碍点求和。这个结论不需要真的去迭代概率它是马尔可夫链理论里的基本定理。有了这个公式题目就变成了一个计数问题计算右下角目标区域里所有点的度数之和再除以整张图所有可达点的度数之和。n 很大但不能暴力遍历所有点好在障碍只有 k 个度数异常的点只出现在障碍周围和网格边界附近内部点的度数全部是 4。所以只需要把障碍周边的一圈点拿出来特殊处理其余部分用公式直接计数。这题的转化思路在区域赛里很有代表性看到随机游走先想平稳分布而不是直接上概率DP。很多队伍在这里浪费了大量时间写状态转移实际上只需要几十行代码就能过。3. 两道分水岭F题的Pell递推与G题的BFS剪枝3.1 F - Heron and His Triangle海伦公式推出Pell递推F题说的是三边长为 t-1、t、t1 的三角形如果面积是整数就把 t 称为一个合法值。给定一个很大的 n求不小于 n 的最小合法 t。先做数学推导。根据海伦公式半周长 p 3t/2面积 S 满足S² p(p - (t-1))(p - t)(p - (t1)) (3t/2) × ((t2)/2) × (t/2) × ((t-2)/2) 3t²(t² - 4) / 16要让 S 是整数关键在于 3(t² - 4) 需要是一个完全平方数。整理后会发现这其实是一个 Pell 方程解出来的 t 满足非常漂亮的递推关系t₁ 4, t₂ 14, tₙ 4 × tₙ₋₁ - tₙ₋₂前几项是 4、14、52、194、724…… 验证一下t 4 时三边是 3、4、5面积 6是整数t 14 时三边是 13、14、15面积 84t 52 时三边是 51、52、53面积 1170。全都符合。现场我推到这个递推之后发现 n 最大可以到 10^30 级别C 的long long完全不够用。我当时直接用 Python 预处理出一张表然后二分查找答案。比赛时如果允许用 Python 交题这是最省事的方案如果只能用 C就得手写高精度加法乘法或者用__int128先跑再看会不会爆——实际上一百多项就会超过 10^30手写大数也不难。这题的核心价值在于把几何问题转化为数论递推。看到海伦公式不要慌先把表达式化简再观察是否落入 Pell 方程的套路。区域赛的数学题经常这样题目包装成几何内核是数论。3.2 G - Infinite Fraction Path多源BFS的去重剪枝G题题意很有意思给一个长度为 n 的数字串 s只含 0-9从每个位置 i 出发下一步会走到 (i² 1) mod n 这个位置。这样从任意位置出发沿着边一直走就能得到一个无限长的数字序列。要求字典序最大的起始位置如果有多个输出下标最小的。这题的本质是每个点只有一条出边所以整张图是若干个一个环加若干棵树的函数图。我需要从这个函数图中找一条字典序最大的无限路径。最简单的想法是第一轮把所有 s[i] 最大的位置加入候选集合。然后每一轮从当前所有候选位置往后走一步比较下一步位置的数字只保留下一步数字最大的那些候选。如果两个候选走到了同一个位置它们后续的路径就完全一样了可以合并成一个这个入度去重是算法能跑得动的关键。这个剪枝的复杂度近似 O(n log n)因为每个点最多被入队一次。我用一个队列模拟多源BFS每层处理时记录当前层的最大字符只有字符等于最大值的那些节点才能进入下一层。现场我刚开始写了个朴素的按层扩展没有去重结果在 n 1e5 的数据上直接超时。加上vis数组去重之后瞬间降到几十毫秒。vectorint cand, nxt; int global_max -1; bool vis[N]; // 第一轮加入所有最大字符的位置 // 每次扩展 while (true) { int best -1; for (int u : cand) { int v (1LL * u * u 1) % n; best max(best, s[v] - 0); } nxt.clear(); for (int u : cand) { int v (1LL * u * u 1) % n; if (s[v] - 0 best !vis[v]) { vis[v] true; nxt.push_back(v); } } cand nxt; if (cand.size() 1) break; // 如果跑满 n 轮还没结束说明后续完全一致取最小下标即可 }这里有个容易被忽略的点(i² 1) mod n在 i 是 int 时会溢出必须用1LL * i * i转成 long long 再取模。这个细节不贵但WA一次很影响心态。4. J题线段树区间“追加数字”操作背后的懒标记推导J题是这套题里最典型的数据结构板子换皮题维护一个数组支持区间操作——把区间内每个数字 x 变成 10x v也就是在十进制末尾追加一个数字 v以及区间求和。q 和 n 都可以到 1e5所以必须用线段树加懒标记。关键在于懒标记的合并方式。每个位置 x 经过一次操作会变成 10x v我把这种变换抽象成x mul × x add初始时 mul 1add 0。那么对一个节点整体做一次追加 v操作节点维护的区间和 sum 会变成sum 10 × sum v × len其中 len 是区间长度。因为区间内每个元素都乘以 10 再加 v所以总和就是原 sum 乘以 10再加上 v 乘以元素个数。接下来是懒标记本身的合并。如果一个节点已经有懒标记 (mul, add)现在要再叠加一层追加 v的操作那么整体变换是x → mul × x add → 10 × (mul × x add) v (10 × mul) × x (10 × add v)所以新的懒标记是mul mul × 10 add add × 10 v下传的时候同样要小心。父节点有个标记 (F_mul, F_add) 要传给子节点子节点原先有一个标记 (mul_c, add_c)合并后子节点的变换应该是先做子节点自己的变换再做父节点的变换x → mul_c × x add_c → F_mul × (mul_c × x add_c) F_add于是mul_c F_mul × mul_c add_c F_mul × add_c F_add同时子节点的 sum 也要更新成sum_c F_mul × sum_c F_add × len_c这题所有操作都在模意义下进行所以每次乘法和加法都要取模。我写的时候一度把合并顺序搞反先乘了 add 导致整棵线段树全是错的。这里有个记法懒标记跟函数复合是反着来的新标记作用在旧标记外面。你只要把x - mul*x add当作函数复合顺序就是先内层后外层不容易错。线段树题目的通病是思路三分钟调BUG三小时J题尤其明显。建议在本地写一个小数据生成器和暴力对拍一秒就能找出合并顺序的问题。5. 两枚硬骨头H题AC自动机加矩阵快速幂、C题空凸包DP5.1 H - Legen...把字符串问题转化为图上最长路H题是这套题的题面担当同时也是做法最贵的一道。题意概括起来就是要构造一个长度为 L 的字符串给定若干模式串每个模式串有一个权值构造出的字符串每出现一个模式串就获得对应权值模式串可以重叠求最大总权值。L 可以到 1e9所以任何线性 DP 都不可行。标准做法是 AC自动机 矩阵快速幂。先对所有模式串建 AC自动机把每个节点看作一个状态在节点 u 后面添加一个字符 c 会转移到一个新节点 v。走到 v 时能获得的权值等于 v 在 fail 树上所有祖先的权值之和——因为命中的模式串可能以 v 结尾也可能以 v 的 fail 祖先结尾。这样问题就变成了在一个状态图上走 L 步每走一步有一定收益求总收益最大值。状态数最多几百个但步数 L 是 1e9所以用矩阵快速幂优化。这里用的不是普通矩阵乘法而是 max-plus 矩阵乘法也就是把乘法换成加法、加法换成取 max。预处理转移矩阵的幂次后用向量乘矩阵的方式在 O(S² log L) 时间内求出答案S 是 AC自动机节点数。现场我们队在这题上卡了很久主要卡在fail 树上的权值累计这一步。建完 AC自动机后一定要把 fail 指针处理成 DAG然后从根往下累加权值否则每个节点只算了自己的权值重叠模式串的情况会漏掉。这题属于代码量不算特别大但对 AC自动机的理解深度要求很高的题值得在补题时完整写一遍。5.2 C - Empty Convex Polygon按极角序做凸包DPC题是要在给定点集中找一个面积最大的空凸包顶点是给定点但凸包内部不能包含任何其他给定点。n 不大大概几十个点但直接枚举凸包的所有组合是指数级的。一个比较经典的思路是把所有点按某个基准点做极角排序然后做一个凸包 DP。设 dp[i][j] 表示凸包的最后一条有向边是从 i 到 j 时凸包的最大面积。转移时枚举前一个点 k要求 k 在向量 i→j 的左侧并且三角形 k-i-j 内部不能有任何给定点。这个三角形内部为空的检查可以预处理。固定 i 和 j 后判断某个点 k 是否在三角形内部只要枚举所有点看是否在三角形内如果有点在内部则这条转移非法。暴力预处理是 O(n^4)但由于 n 只有几十优化到 O(n^3) 后非常快。最后答案取所有合法 dp[i][j] 的最大值。这题你光看题解会觉得道理很简单实际写起来全是细节极角排序的基准点选择、共线点的处理、三角形面积取绝对值、dp 的初始化值用负数还是 0。补这题的时候我建议直接用long double存坐标和面积避免浮点误差在边界数据上爆掉。区域赛的计算几何题基本不会太丧心病狂但精度细节一定要抠死。6. 模拟题和剩余题目怎么处理6.1 E题大模拟把牌型编码成可比较的整数E题是扑克牌比大小的模拟五张牌比牌型类似梭哈的规则。这种题没有任何算法难度拼的就是细心。我的建议是不要写一大堆if嵌套把所有信息压缩成一个可比较的结构。具体做法先把五张牌按点数排序然后统计每种点数的出现次数判断属于哪种牌型同花顺、四条、葫芦、同花、顺子、三条、两对、一对、散牌。每种牌型内部再比较关键牌的大小所以可以设计一个vectorint rank表示这个牌型在比较时的权重序列C 里vector直接支持字典序比较非常方便。比如两对的权重序列可以设计成{大对子点数, 小对子点数, 单牌点数}三条是{三条点数, 剩余最大单牌, 剩余次大单牌}。把所有牌型映射成一个牌型编号 权重序列的组合先比较牌型编号再比较权重序列。这样写出来逻辑清晰调试也快。现场很多队卡在 E 题不是不会做而是 if 写太多把自己绕晕了重构一遍反而几分钟就过。6.2 没补完的三题赛后我的判断标题说 10 / 13说明有三题我当时没有完整补出来。A 题 BBP Formula 是数学题需要处理无理数在十六进制下的逐位计算涉及高精度和浮点误差控制我赛后理解了大致的迭代公式但没有真正实现通过。B 题 Bridge 是仙人掌图上的路径问题需要先掌握圆方树我对这个模型的熟练度不够暂时放下。K 题 Mahjong 是一个麻将判断的大模拟规则细节非常繁琐我当时的精力不足以把整副牌的状态压缩写对。这三题如果之后有时间我会单独写一篇补题记录。不过从应付区域赛的角度来说把 C、F、G、H、J 这五题吃透比硬啃 A、B、K 性价比高很多——前者的模型在后续比赛中反复出现后三者更像是特定知识点的专项训练。7. 补完这套题之后的一些体会这套题最值得学习的地方是它把看似复杂的模型和极其朴素的结论结合得很好。M题的随机游走本质是稳态分布与度数成正比F题的面积整数问题本质是 Pell 方程G题的无限路径本质是函数图上的剪枝。这些题目如果只盯着表面看会觉得难到无从下手但一旦抓住底层模型代码量往往不超过一百行。我在补题时养成了一个习惯每道题补完把自己的推导过程压缩成三五行核心笔记比如F题 海伦公式 → Pell 递推 → 高精度表、G题 函数图 → 多源BFS → 入度去重。这样过几个月回头看一分钟就能复习完一道题。建议你也试试这个方法。另外说一个现场比赛的题外话I题那种溢出陷阱我和队友当时因为罚时懊恼了很久但赛后想想这恰恰是区域赛签到题最常见的出题逻辑——不是考你不会算加法而是考你有没有边界意识。平时刷题养成多问一句数据范围到极限时会发生什么的习惯能省下不少罚时。这套题补完我对这句话的体会比之前任何时候都深。
