2022ICPC杭州站打完到现在每次复盘我还是会翻K、A、C、G、M这五道题的提交记录。这篇是个人复盘向的题解不是官方标程汇编核心是把每道题从“读题”到“建模”再到“写代码”的完整链路重新走一遍。K题是字符串加Trie离线计数C题是带惩罚项的分组背包G题是树哈希与换根DPA题是同余最短路M题是无脑签到。如果你正在备战区域赛这五题里有三题的套路能直接迁移到其他场次如果只是查漏补缺后面记录的踩坑点也值得扫一眼。下面的题面描述按我自己的理解和补题记忆做了抽象细节以原题为准重点看每一类模型怎么想到、怎么落地。1. 赛题总览五道题在整场比赛里的位置1.1 难度与考点速览先把五道题的定位列出来方便对照后面各章节。题号核心考点难度代码量现场建议开题顺序M结论签到 / 简单博弈签到约30行1A裴蜀定理 同余最短路中等约120行3KTrie 离线计数较难约180行2C分组背包 枚举被扣除项中等偏难约130行4G树哈希 换根DP中等偏难约200行5这五题的中位数难度其实不算特别高但区域赛的体验从来不是“你会不会”而是“你能不能在现场把模型快速想清楚并且不写崩”。K题和G题都是典型的“原理一句话、实现十行坑”类型看榜上过题数就知道队伍在两题上分化非常明显。A题是数论入门题但现场用错的队伍不少。C题的题干包装得花里胡哨剥开之后就是一个分组背包变形。1.2 现场选题逻辑哪些题值得先开我们当时的分工是M题一眼签到直接让代码手去写我负责把K题和A题先读掉队友去看C和G的题面。这种并行读题的习惯非常重要区域赛前30分钟如果全队都在盯同一道题基本就输了一半。先开M是因为它大概率是“读题即出思路”的题拿到的是一血机会和稳定罚时。K题属于那种“看着像字符串难题、实际是计数题”的题值得前期耗时间A题是标准数论模型读完题就应该能判断能不能做。C和G留给队友的原因是它们都有比较厚的包装需要先花几分钟剥离出真实模型。盯榜也有技巧哪个题号过题数涨得最快说明哪题是纸老虎。很多队伍容易被题面吓到看到“Subgraph”这个词就以为G题要写网络流实际上树上的同构判定是常规套路。2. K题Trie离线统计把排列查询变成二维矩阵求和2.1 题意抽象与第一步转化K题的原始模型我记忆里是给一堆字符串然后给出一堆字母表排列对每个排列问按这个顺序排序后逆序对的数量。n个串的总长度在1e5级别查询次数可以到1e5级别。直接每个查询重新排序一次肯定不可能必须把“排序结果如何受字母表影响”剥离出来。两个字符串比较大小只有两种情况。第一种一个串是另一个串的前缀那么短串永远更小跟字母表排列没有关系。第二种两个串在某个位置第一次出现不同字符假设分别是a和b那么谁排在前面只取决于a和b在这个排列里的相对位置。这个观察是整道题的灵魂。所以我们要做的不是对每个排列重新算排序而是预先统计所有字符串对之间“第一次分叉”的字符对数量。设cnt[a][b]表示按输入顺序前面那个串第一次分叉字符是a、后面那个串第一次分叉字符是b的串对数量。对于一个具体排列如果a排在b前面那么这一对字符串的顺序和输入顺序一致不贡献逆序如果a排在b后面顺序被翻转贡献1个逆序。再加上前缀关系产生的固定贡献答案就能O(26^2)算出来。2.2 Trie上统计字符对贡献统计cnt需要一个结构把字符串按前缀挂起来自然是Trie。把所有串插入Trie之后每个节点需要维护两类信息子树内所有串的编号列表以及在该节点结束的串编号列表。DFS后序遍历每个节点。对节点u先递归处理所有孩子然后把孩子的编号列表和u自己的结束串列表合并排序后存到u上。排序的作用是支持两个列表间的有序配对统计。接着枚举u的两个不同孩子分支a和b计算“a分支里的串编号小于b分支里的串编号”的对数这个就是cnt[a][b]反向数量自然就是cnt[b][a]。固定贡献在同一个节点处理u的结束串是短串任何一个孩子分支里的串都是长串无论字母表怎么排短串一定在前面。但如果输入顺序里长串排在短串前面排序后位置反转就产生了1个逆序。用lower_bound统计每个结束串编号前有多少个长串编号即可。void dfs(int u) { vectorint ids; for (int c 0; c 26; c) { int v tr[u].ch[c]; if (!v) continue; dfs(v); ids.insert(ids.end(), tr[v].ids.begin(), tr[v].ids.end()); } ids.insert(ids.end(), tr[u].ends.begin(), tr[u].ends.end()); sort(ids.begin(), ids.end()); tr[u].ids ids; for (int a 0; a 26; a) { int va tr[u].ch[a]; if (!va) continue; for (int e : tr[u].ends) { fixed lower_bound(tr[va].ids.begin(), tr[va].ids.end(), e) - tr[va].ids.begin(); } for (int b a 1; b 26; b) { int vb tr[u].ch[b]; if (!vb) continue; long long cross countLess(tr[va].ids, tr[vb].ids); cnt[a][b] cross; cnt[b][a] 1LL * tr[va].ids.size() * tr[vb].ids.size() - cross; } } }这里countLess就是两个有序数组之间单向的二元组计数用归并或者双指针都能写注意long long。重复字符串不会产生字符对贡献因为它们在同一个叶子结束跨分支统计不会包含它们前缀贡献里短串和长串也不是相等串处理是对的。2.3 查询部分的实现与优化查询时给定字母表排列记pos[x]表示字符x在新排列中的位置。先累加fixed然后枚举所有26乘26的字符对long long ans fixed; for (int a 0; a 26; a) for (int b 0; b 26; b) if (pos[a] pos[b]) ans cnt[a][b]; printf(%lld\n, ans);为什么是pos[a]大于pos[b]就加cnt[a][b]cnt[a][b]的意义是输入顺序中第一个串分叉字符为a、第二个串分叉字符为b。如果a在排列里排在b后面说明按新字典序第一个串反而应该排在第二个串后面原来输入顺序被翻转产生1个逆序。这个方向初学者很容易搞反建议自己拿两个串手推一遍。复杂度方面q是1e526乘26是676总加法不到7千万次用scanf和printf或者关闭同步的cin都能过。现场有人觉得这个复杂度会超时去优化其实没必要真正要卡的常数是Trie统计部分vector的排序和合并。如果害怕卡常可以把固定答案和字符对答案拆开用前缀和优化但对这题的数据规模来说收益不大反而增加写错的风险。2.4 K题容易踩的三个坑第一个坑是固定前缀贡献的方向。只统计长串编号小于短串编号的数量也就是长串在输入顺序里先出现的情况反过来不贡献因为排序后顺序没有变化。这个我写错了一次样例通常能暴露出来。第二个坑是Trie节点vector的合并成本。我在第一版里把每个节点的ids都复制了一遍到父节点实际上一个串会出现在它路径上每个节点的ids里总存储量就是所有串的总长度这是可接受的。但如果你在每个节点做的是深拷贝并参与排序复杂度就变成总长度乘以某个深度级别很可能TLE。第三个坑是答案要用long long。字符串对数量是n平方级别的n到1e5的时候会直接溢出int。很多队伍现场WA在这里查了半天以为是计数逻辑错。3. C题带惩罚项的分组背包枚举被扣除的最大值3.1 为什么直接做普通背包会错C题剥开包装后我理解的模型是这样的有n个技能组每个组有若干选项每个选项有收益值和花费值容量限制为C。正常来说就是经典分组背包。但题目加了一个惩罚如果你选中的方案里存在某个特定类型的选项最终收益要扣除所有选中项里收益最大的那一项。最容易想到的错误做法是先忽略惩罚跑一个普通分组背包拿到最大总收益再把这个最大总收益减去某个最小收益项。这不对原因很直接被扣除的项占用了容量它参与影响了哪些选项能被选进来。你减掉它之后释放的容量原本可以用来放其他更有价值的选项。也就是说“最大总收益”和“扣除最大收益后的最大总收益”对应的是两套完全不同的选择方案。所以必须把“哪一个选项是被扣除的最大值”作为枚举对象让它在DP过程中固定在选择方案里。3.2 枚举最大值后的分组背包设计设第p个选项是最终被扣除的最大值它的收益是val[p]代价是cost[p]属于组g[p]。那么合法的选择方案需要满足第g[p]组必须选p其他组如果选选到的选项收益不能超过val[p]最终总收益等于所有选中收益之和减去val[p]。这个限制非常适合做分组背包。对每个被枚举的p把其他组中收益大于val[p]的选项直接删掉相当于只有收益不超过val[p]的选项可供选择。然后跑一遍分组背包普通组照常做p所在组强制只选p。最终答案取所有情况下背包价值减val[p]的最大值。状态转移注意一点普通组的“不选”要保留所以初始化ndp等于上一轮dp而p所在组必须选p不能保留“不选”的状态否则方案非法。我第一版就是这个细节写错导致答案偏大。long long ans 0; for (int id 0; id m; id) { int g groupOf[id]; vectorlong long dp(C 1, -INF), ndp(C 1); dp[0] 0; for (int i 0; i n; i) { if (i g) { fill(ndp.begin(), ndp.end(), -INF); for (int j 0; j cost[id] C; j) ndp[j cost[id]] max(ndp[j cost[id]], dp[j] val[id]); } else { ndp dp; for (auto op : group[i]) { if (op.val val[id]) continue; for (int j C - op.cost; j 0; j--) ndp[j op.cost] max(ndp[j op.cost], dp[j] op.val); } } dp.swap(ndp); } for (int j 0; j C; j) if (dp[j] -INF / 2) ans max(ans, dp[j] - val[id]); }3.3 参考实现与复杂度说明上面代码是清理掉“包装”之后最直白的版本复杂度是O(m * n * C * avgK)其中m是总选项数avgK是每组平均选项数。如果n到50、总选项到2000、C到500这个复杂度大概在5乘10的8次方量级C优化后勉强能跑。现场如果数据更大就需要用离线增量或者对每组的可选项做单调性处理但那是工程优化层面模型选对了就有抢救空间。我补题时发现一个更好的组织方式对每个枚举项p只重新跑一遍dp太浪费因为很多组在不同p下的可选集合是相同的。把选项按收益从小到大排序随着p的收益增大会有越来越多的组逐渐“解锁”新的选项。这种增量思路可以把复杂度压到O(m * C)级别但写起来要非常小心组内选项只能选一个的限制建议有一定背包经验再尝试。3.4 现场调DP的状态细节这类分组背包变形题现场最容易崩的地方有两个。第一是初始化dp数组一定要用负无穷而不是0因为有些容量状态不可达用0会让非法方案混进来。第二是强制选p的组的转移要单独处理不能用常规组的逻辑。还有一个细节容易被忽略被扣除项和其他某个选中项收益相等时枚举p仍然正确。因为多个最大值时扣除哪一个都一样我们枚举的是“被扣除的那个选项”其他相同收益的选项在别的枚举中被处理。不要把相等项排除掉否则答案会漏。我现场写这题时犯的错是忘记把普通组的“不选”状态保留结果每个组都强制选了一个选项容量利用率反而下降答案偏差不小。调试时用样例和自己构造的小数据对拍很快就定位到了。4. G题树哈希 换根DP判断子树同构4.1 树哈希的基本思路G题我按“判断两棵树是否同构”这个模型来复盘如果是更大的子图同构思路是在这个基础上扩展到多轮匹配但核心的哈希工具是一样的。树同构不能直接比较节点的儿子顺序因为儿子顺序不影响树的结构所以每个节点的哈希应该由“孩子哈希的多重集”决定而不是“孩子哈希的有序序列”。最常见的写法是对每个节点u定义h[u]等于一个由孩子哈希多重集计算出的哈希值。实现方式可以是把所有孩子哈希排序后拼成一个字符串再哈希也可以用随机权重做累加。前者直观但换根时会遇到排序的更新困难后者方便换根是我更推荐的方式。具体来说给每个不同的子树哈希值分配一个随机权重然后定义h[u] 1 sum(weight[h[v]]) 对v是u的孩子这里的加法和权重计算都在模数下进行。由于同一个哈希值会映射到同一个随机权重这种设计保证了两棵结构相同的子树算出相同的h值结构不同的子树大概率不同。4.2 用随机权重的可减哈希实现换根换根DP的难点不是计算根节点的哈希而是当根从u换到v时u那边的那棵“分支”变成了v的一个孩子需要快速算出这个分支的哈希。随机权重哈希最大的好处就是可减u原来的哈希包含了v这个孩子的权重减掉它就得到了u去掉v子树后的哈希。设ru是u作为根时整棵树的哈希。要转移到孩子v时u去掉v子树后的哈希nu等于ru减去weight[h[v]]模一下补正。然后以v为根时v的孩子就是原来的孩子再加上这个nu分支所以rv等于1加上所有孩子哈希的权重之和。这个过程只需要O(1)计算每一个转移整棵树换根一遍是O(n)。实现时要注意换根过程中产生的nu这个哈希值可能是全新的以它作为下一层的分支哈希时需要先给它分配随机权重。否则下一层计算W[nu]会得到0结构信息直接丢了。void reroot(int u, int fa, ull up1, ull up2) { ull ru1 1, ru2 1; for (int v : g[u]) { if (v fa) continue; ru1 (ru1 W1[h1[v]]) % MOD1; ru2 (ru2 W2[h2[v]]) % MOD2; } if (fa ! 0) { ru1 (ru1 W1[up1]) % MOD1; ru2 (ru2 W2[up2]) % MOD2; } allHashes.insert({ru1, ru2}); for (int v : g[u]) { if (v fa) continue; ull nu1 (ru1 - W1[h1[v]] MOD1) % MOD1; ull nu2 (ru2 - W2[h2[v]] MOD2) % MOD2; getWeight(nu1, nu2); reroot(v, u, nu1, nu2); } }这个写法里W1和W2是两个映射表把哈希值映射成随机权重。如果不用双哈希只保留一组权重碰撞风险在正式比赛里不可接受后面会细说。4.3 完整判定流程判断A树能否与B树同构流程分三步。第一步对A做一次普通DFS预先得到以某个固定节点为根的哈希然后以A的每个节点为根跑一遍换根DP把所有可能的无根哈希存入集合。第二步对B同样做换根DP对每个节点的根哈希检查是否出现在集合里。第三步如果出现了说明A和B存在同构关系输出对应的根节点信息。如果题目要求的是“B中是否存在某个连通子图与A同构”也就是B比A大那么需要在B上对每个节点枚举“只保留一部分分支”的哈希相当于做子树截断后再比较。这个操作仍然可以用可减哈希完成比如对每个节点枚举它保留哪些孩子分支但复杂度会高一些需要用树上背包的思想按子树大小做限制。赛场上如果时间不够先把同构判断写对拿一部分分再考虑扩展。4.4 哈希碰撞与精度控制树哈希本质上是一个概率算法虽然实际比赛中碰撞概率极低但被卡过的人绝对不会只写单哈希。单模自然溢出很容易被构造数据定向碰撞尤其是随机权重本身如果生成方式被摸清的情况下。我的习惯是双模数加随机权重模数选1e97和1e99权重用mt19937_64随机生成。判断相等时两个模数都必须相等。有些选手会直接用unsigned long long自然溢出当作一个哈希这也不是不行但强烈建议再加一个质数模。双哈希的时间开销很小换根DP本身就O(n)多一次运算无伤大雅。还有一点权重分配表的map查找在递归里很频繁用unordered_map会快很多。但unordered_map在哈希碰撞攻击下可能退化建议提前reserve或者直接用数组把哈希值映射到一个自增索引再存随机权重效率更高也更稳。5. A题裴蜀定理判可行性同余最短路求最小步数5.1 先看是否有解裴蜀定理A题的问题形态本质上是给定两个操作数a和b目标模数M以及目标余数c问能否通过若干次“加上a或加上b再取模”的操作从0走到c。先不要急着跑最短路第一步应该用裴蜀定理判断无解。因为每次加a或加b当前值模gcd(a,b)永远不会变。从0出发能到达的状态必须满足“该状态模gcd(a,b)等于0”。再考虑取模M的影响整体能到达的余数集合是gcd(a, b, M)的倍数。所以如果c不是gcd(a, b, M)的倍数直接无解这是O(log)的判断比跑一遍最短路快得多也能避免在无解数据上浪费大量时间。如果gcd为1那理论上所有余数都可达接下来要解决的是“最小步数”问题。这个最小步数是经典的同余最短路模型。5.2 同余最短路的建图方式把0到M-1这M个余数看成图上的节点。从节点x出发加a取模到(x a) mod M加b取模到(x b) mod M两条边的边权都是1。问题是求0到目标c的最短路。由于边权全是1直接用普通BFS就够了不需要Dijkstra。但要注意M可能到1e6级别邻接表根本不用建每次转移算出两个后继节点就行。visited数组和dist数组都用int初始化为无穷大。如果数据范围更大比如M到1e9就不能开数组。这时候先用裴蜀定理把问题缩小把所有数同时除以gcd(a, b, M)等价类就压缩到了可处理大小。具体的压缩方法是令g等于gcd(a, b, M)只保留c mod g为0的余数类把a、b、c、M全部除以g后重新建图。5.3 代码骨架与路径还原int solve(int a, int b, int M, int c) { if (c % __gcd(__gcd(a, b), M) ! 0) return -1; vectorint dist(M, INF); queueint q; dist[0] 0; q.push(0); while (!q.empty()) { int x q.front(); q.pop(); int y1 (x a) % M; int y2 (x b) % M; if (dist[y1] dist[x] 1) { dist[y1] dist[x] 1; q.push(y1); } if (dist[y2] dist[x] 1) { dist[y2] dist[x] 1; q.push(y2); } } return dist[c]; }如果需要输出具体操作序列就维护一个pre数组每次松弛时记录是从哪个状态、哪个操作转移过来的最后从c倒推回0。因为边权为1BFS天然保证了第一次到达时的路径就是最短的pre不会反复更新。5.4 这类题的通用套路同余最短路不只是这一道题用得上。给定若干种面额问凑出某个余数的最小数量给定若干种步长问从0到目标模值的最短步数甚至某些线性丢番图方程求非负整数解也可以转化成同余最短路。看到“若干操作 模意义下 最小步数”这三个特征同时出现基本就可以往这个模型上联想。一个提高效率的细节是如果a和b都是M的因子那么BFS的图会退化成若干个互不相连的环可以先按gcd缩点。否则直接跑也不慢。现场很多人纠结要不要用01BFS其实只有在边权是0和1的时候才需要这题边权全1普通队列就是最优解。6. M题签到题也要按流程来6.1 从样例反推结论M题我印象里是一个读完题就能写结论的签到大意和取石子或者模4判断有关最终落点是一个奇偶或者模周期性判断。这类题最忌讳的是拿到题就开始枚举情况正确的打开方式是先写一个爆搜在小范围内把所有可能结果打出来看规律再证明。以取石子博弈为例如果规则是每人每次取1到3个取到最后一个的赢那爆搜会发现只要n是4的倍数先手必败否则先手必胜。因为你无论取几个后手都可以把每轮凑成4个最后把局面留给你面对4的倍数。M题如果也是这种结构结论推导完全一致。不要觉得这个流程小题大做区域赛的签到题现场翻车率其实很高。因为大家急着抢一血样例一过就交结果WA在边界上。签到题更要稳。6.2 最小可用的判断代码puts(n % 4 0 ? No : Yes);这种代码没有任何复杂的数据结构但前提是结论完全正确。交之前至少构造三组测试最小的n、恰好是结论临界点的n、比较大的n。比如n等于1、2、3、4、5都跑一遍确认没有越界逻辑。如果题目的一句话题面不是这个思考方式和上面一样找到状态转移里的周期压缩成常数判断。不要想着靠记忆背模板区域赛签到题的包装千变万化背不住的。6.3 不要因为题目简单就乱交很多队伍签到最后变成负贡献不是因为不会做而是因为过早提交又反复WA白白增加罚时。我的习惯是签到题至少两个人确认结论一个人写代码另一个人拿样例和暴力对拍。区域赛一次罚时20分钟与其抢两分钟的一血不如稳一手。另外M题这种题经常藏在榜末不一定题号最小就最简单。开题前先全局扫一遍所有题面的第一段把明显是送分的题找出来。这个动作能节省大量时间也能避免全队在一道题上钻进死胡同。7. 复盘后的几个通用习惯这次杭州站复盘之后我给自己定了几条规矩写出来供参考。第一卡题超过30分钟必须把模型写在纸上而不是在脑子里反复绕。K题和C题虽然模型不同但都是“先抽象成数学结构再写代码”的类型。空想很容易漏条件写下来反而能看清楚哪些是托词、哪些是真实难点。第二背包问题先想清楚状态能不能合并。C题如果一上来就按“当前是谁被扣”设二维状态复杂度很难压换一个角度枚举最大值反而简单。分组背包的变种在区域赛出现频率很高状态设计要学会往“枚举特殊项”这个方向靠。第三涉及哈希的题目一律双哈希没有例外。G题的随机权重方案虽然概率极低但赛场上一旦被构造数据卡掉整个队伍的节奏就崩了。双模数只是多写几行性价比极高。第四签到题也要做边界测试。M题这种题WA一次浪费的罚时可能比后面一道中等题多写两分钟还贵。样例通过只是开始临界值和最小值才是翻车点。第五补题比刷新题重要。我每次区域赛后都会挑五道题重新写一遍并且不只写标准做法还会把现场错误版本和正确版本放在一起对比。这个方法帮我避开了很多同类坑。这套杭州站复盘帖就是在这种对比习惯下整理出来的。
2022ICPC杭州站打完到现在每次复盘我还是会翻K、A、C、G、M这五道题的提交记录。这篇是个人复盘向的题解不是官方标程汇编核心是把每道题从“读题”到“建模”再到“写代码”的完整链路重新走一遍。K题是字符串加Trie离线计数C题是带惩罚项的分组背包G题是树哈希与换根DPA题是同余最短路M题是无脑签到。如果你正在备战区域赛这五题里有三题的套路能直接迁移到其他场次如果只是查漏补缺后面记录的踩坑点也值得扫一眼。下面的题面描述按我自己的理解和补题记忆做了抽象细节以原题为准重点看每一类模型怎么想到、怎么落地。1. 赛题总览五道题在整场比赛里的位置1.1 难度与考点速览先把五道题的定位列出来方便对照后面各章节。题号核心考点难度代码量现场建议开题顺序M结论签到 / 简单博弈签到约30行1A裴蜀定理 同余最短路中等约120行3KTrie 离线计数较难约180行2C分组背包 枚举被扣除项中等偏难约130行4G树哈希 换根DP中等偏难约200行5这五题的中位数难度其实不算特别高但区域赛的体验从来不是“你会不会”而是“你能不能在现场把模型快速想清楚并且不写崩”。K题和G题都是典型的“原理一句话、实现十行坑”类型看榜上过题数就知道队伍在两题上分化非常明显。A题是数论入门题但现场用错的队伍不少。C题的题干包装得花里胡哨剥开之后就是一个分组背包变形。1.2 现场选题逻辑哪些题值得先开我们当时的分工是M题一眼签到直接让代码手去写我负责把K题和A题先读掉队友去看C和G的题面。这种并行读题的习惯非常重要区域赛前30分钟如果全队都在盯同一道题基本就输了一半。先开M是因为它大概率是“读题即出思路”的题拿到的是一血机会和稳定罚时。K题属于那种“看着像字符串难题、实际是计数题”的题值得前期耗时间A题是标准数论模型读完题就应该能判断能不能做。C和G留给队友的原因是它们都有比较厚的包装需要先花几分钟剥离出真实模型。盯榜也有技巧哪个题号过题数涨得最快说明哪题是纸老虎。很多队伍容易被题面吓到看到“Subgraph”这个词就以为G题要写网络流实际上树上的同构判定是常规套路。2. K题Trie离线统计把排列查询变成二维矩阵求和2.1 题意抽象与第一步转化K题的原始模型我记忆里是给一堆字符串然后给出一堆字母表排列对每个排列问按这个顺序排序后逆序对的数量。n个串的总长度在1e5级别查询次数可以到1e5级别。直接每个查询重新排序一次肯定不可能必须把“排序结果如何受字母表影响”剥离出来。两个字符串比较大小只有两种情况。第一种一个串是另一个串的前缀那么短串永远更小跟字母表排列没有关系。第二种两个串在某个位置第一次出现不同字符假设分别是a和b那么谁排在前面只取决于a和b在这个排列里的相对位置。这个观察是整道题的灵魂。所以我们要做的不是对每个排列重新算排序而是预先统计所有字符串对之间“第一次分叉”的字符对数量。设cnt[a][b]表示按输入顺序前面那个串第一次分叉字符是a、后面那个串第一次分叉字符是b的串对数量。对于一个具体排列如果a排在b前面那么这一对字符串的顺序和输入顺序一致不贡献逆序如果a排在b后面顺序被翻转贡献1个逆序。再加上前缀关系产生的固定贡献答案就能O(26^2)算出来。2.2 Trie上统计字符对贡献统计cnt需要一个结构把字符串按前缀挂起来自然是Trie。把所有串插入Trie之后每个节点需要维护两类信息子树内所有串的编号列表以及在该节点结束的串编号列表。DFS后序遍历每个节点。对节点u先递归处理所有孩子然后把孩子的编号列表和u自己的结束串列表合并排序后存到u上。排序的作用是支持两个列表间的有序配对统计。接着枚举u的两个不同孩子分支a和b计算“a分支里的串编号小于b分支里的串编号”的对数这个就是cnt[a][b]反向数量自然就是cnt[b][a]。固定贡献在同一个节点处理u的结束串是短串任何一个孩子分支里的串都是长串无论字母表怎么排短串一定在前面。但如果输入顺序里长串排在短串前面排序后位置反转就产生了1个逆序。用lower_bound统计每个结束串编号前有多少个长串编号即可。void dfs(int u) { vectorint ids; for (int c 0; c 26; c) { int v tr[u].ch[c]; if (!v) continue; dfs(v); ids.insert(ids.end(), tr[v].ids.begin(), tr[v].ids.end()); } ids.insert(ids.end(), tr[u].ends.begin(), tr[u].ends.end()); sort(ids.begin(), ids.end()); tr[u].ids ids; for (int a 0; a 26; a) { int va tr[u].ch[a]; if (!va) continue; for (int e : tr[u].ends) { fixed lower_bound(tr[va].ids.begin(), tr[va].ids.end(), e) - tr[va].ids.begin(); } for (int b a 1; b 26; b) { int vb tr[u].ch[b]; if (!vb) continue; long long cross countLess(tr[va].ids, tr[vb].ids); cnt[a][b] cross; cnt[b][a] 1LL * tr[va].ids.size() * tr[vb].ids.size() - cross; } } }这里countLess就是两个有序数组之间单向的二元组计数用归并或者双指针都能写注意long long。重复字符串不会产生字符对贡献因为它们在同一个叶子结束跨分支统计不会包含它们前缀贡献里短串和长串也不是相等串处理是对的。2.3 查询部分的实现与优化查询时给定字母表排列记pos[x]表示字符x在新排列中的位置。先累加fixed然后枚举所有26乘26的字符对long long ans fixed; for (int a 0; a 26; a) for (int b 0; b 26; b) if (pos[a] pos[b]) ans cnt[a][b]; printf(%lld\n, ans);为什么是pos[a]大于pos[b]就加cnt[a][b]cnt[a][b]的意义是输入顺序中第一个串分叉字符为a、第二个串分叉字符为b。如果a在排列里排在b后面说明按新字典序第一个串反而应该排在第二个串后面原来输入顺序被翻转产生1个逆序。这个方向初学者很容易搞反建议自己拿两个串手推一遍。复杂度方面q是1e526乘26是676总加法不到7千万次用scanf和printf或者关闭同步的cin都能过。现场有人觉得这个复杂度会超时去优化其实没必要真正要卡的常数是Trie统计部分vector的排序和合并。如果害怕卡常可以把固定答案和字符对答案拆开用前缀和优化但对这题的数据规模来说收益不大反而增加写错的风险。2.4 K题容易踩的三个坑第一个坑是固定前缀贡献的方向。只统计长串编号小于短串编号的数量也就是长串在输入顺序里先出现的情况反过来不贡献因为排序后顺序没有变化。这个我写错了一次样例通常能暴露出来。第二个坑是Trie节点vector的合并成本。我在第一版里把每个节点的ids都复制了一遍到父节点实际上一个串会出现在它路径上每个节点的ids里总存储量就是所有串的总长度这是可接受的。但如果你在每个节点做的是深拷贝并参与排序复杂度就变成总长度乘以某个深度级别很可能TLE。第三个坑是答案要用long long。字符串对数量是n平方级别的n到1e5的时候会直接溢出int。很多队伍现场WA在这里查了半天以为是计数逻辑错。3. C题带惩罚项的分组背包枚举被扣除的最大值3.1 为什么直接做普通背包会错C题剥开包装后我理解的模型是这样的有n个技能组每个组有若干选项每个选项有收益值和花费值容量限制为C。正常来说就是经典分组背包。但题目加了一个惩罚如果你选中的方案里存在某个特定类型的选项最终收益要扣除所有选中项里收益最大的那一项。最容易想到的错误做法是先忽略惩罚跑一个普通分组背包拿到最大总收益再把这个最大总收益减去某个最小收益项。这不对原因很直接被扣除的项占用了容量它参与影响了哪些选项能被选进来。你减掉它之后释放的容量原本可以用来放其他更有价值的选项。也就是说“最大总收益”和“扣除最大收益后的最大总收益”对应的是两套完全不同的选择方案。所以必须把“哪一个选项是被扣除的最大值”作为枚举对象让它在DP过程中固定在选择方案里。3.2 枚举最大值后的分组背包设计设第p个选项是最终被扣除的最大值它的收益是val[p]代价是cost[p]属于组g[p]。那么合法的选择方案需要满足第g[p]组必须选p其他组如果选选到的选项收益不能超过val[p]最终总收益等于所有选中收益之和减去val[p]。这个限制非常适合做分组背包。对每个被枚举的p把其他组中收益大于val[p]的选项直接删掉相当于只有收益不超过val[p]的选项可供选择。然后跑一遍分组背包普通组照常做p所在组强制只选p。最终答案取所有情况下背包价值减val[p]的最大值。状态转移注意一点普通组的“不选”要保留所以初始化ndp等于上一轮dp而p所在组必须选p不能保留“不选”的状态否则方案非法。我第一版就是这个细节写错导致答案偏大。long long ans 0; for (int id 0; id m; id) { int g groupOf[id]; vectorlong long dp(C 1, -INF), ndp(C 1); dp[0] 0; for (int i 0; i n; i) { if (i g) { fill(ndp.begin(), ndp.end(), -INF); for (int j 0; j cost[id] C; j) ndp[j cost[id]] max(ndp[j cost[id]], dp[j] val[id]); } else { ndp dp; for (auto op : group[i]) { if (op.val val[id]) continue; for (int j C - op.cost; j 0; j--) ndp[j op.cost] max(ndp[j op.cost], dp[j] op.val); } } dp.swap(ndp); } for (int j 0; j C; j) if (dp[j] -INF / 2) ans max(ans, dp[j] - val[id]); }3.3 参考实现与复杂度说明上面代码是清理掉“包装”之后最直白的版本复杂度是O(m * n * C * avgK)其中m是总选项数avgK是每组平均选项数。如果n到50、总选项到2000、C到500这个复杂度大概在5乘10的8次方量级C优化后勉强能跑。现场如果数据更大就需要用离线增量或者对每组的可选项做单调性处理但那是工程优化层面模型选对了就有抢救空间。我补题时发现一个更好的组织方式对每个枚举项p只重新跑一遍dp太浪费因为很多组在不同p下的可选集合是相同的。把选项按收益从小到大排序随着p的收益增大会有越来越多的组逐渐“解锁”新的选项。这种增量思路可以把复杂度压到O(m * C)级别但写起来要非常小心组内选项只能选一个的限制建议有一定背包经验再尝试。3.4 现场调DP的状态细节这类分组背包变形题现场最容易崩的地方有两个。第一是初始化dp数组一定要用负无穷而不是0因为有些容量状态不可达用0会让非法方案混进来。第二是强制选p的组的转移要单独处理不能用常规组的逻辑。还有一个细节容易被忽略被扣除项和其他某个选中项收益相等时枚举p仍然正确。因为多个最大值时扣除哪一个都一样我们枚举的是“被扣除的那个选项”其他相同收益的选项在别的枚举中被处理。不要把相等项排除掉否则答案会漏。我现场写这题时犯的错是忘记把普通组的“不选”状态保留结果每个组都强制选了一个选项容量利用率反而下降答案偏差不小。调试时用样例和自己构造的小数据对拍很快就定位到了。4. G题树哈希 换根DP判断子树同构4.1 树哈希的基本思路G题我按“判断两棵树是否同构”这个模型来复盘如果是更大的子图同构思路是在这个基础上扩展到多轮匹配但核心的哈希工具是一样的。树同构不能直接比较节点的儿子顺序因为儿子顺序不影响树的结构所以每个节点的哈希应该由“孩子哈希的多重集”决定而不是“孩子哈希的有序序列”。最常见的写法是对每个节点u定义h[u]等于一个由孩子哈希多重集计算出的哈希值。实现方式可以是把所有孩子哈希排序后拼成一个字符串再哈希也可以用随机权重做累加。前者直观但换根时会遇到排序的更新困难后者方便换根是我更推荐的方式。具体来说给每个不同的子树哈希值分配一个随机权重然后定义h[u] 1 sum(weight[h[v]]) 对v是u的孩子这里的加法和权重计算都在模数下进行。由于同一个哈希值会映射到同一个随机权重这种设计保证了两棵结构相同的子树算出相同的h值结构不同的子树大概率不同。4.2 用随机权重的可减哈希实现换根换根DP的难点不是计算根节点的哈希而是当根从u换到v时u那边的那棵“分支”变成了v的一个孩子需要快速算出这个分支的哈希。随机权重哈希最大的好处就是可减u原来的哈希包含了v这个孩子的权重减掉它就得到了u去掉v子树后的哈希。设ru是u作为根时整棵树的哈希。要转移到孩子v时u去掉v子树后的哈希nu等于ru减去weight[h[v]]模一下补正。然后以v为根时v的孩子就是原来的孩子再加上这个nu分支所以rv等于1加上所有孩子哈希的权重之和。这个过程只需要O(1)计算每一个转移整棵树换根一遍是O(n)。实现时要注意换根过程中产生的nu这个哈希值可能是全新的以它作为下一层的分支哈希时需要先给它分配随机权重。否则下一层计算W[nu]会得到0结构信息直接丢了。void reroot(int u, int fa, ull up1, ull up2) { ull ru1 1, ru2 1; for (int v : g[u]) { if (v fa) continue; ru1 (ru1 W1[h1[v]]) % MOD1; ru2 (ru2 W2[h2[v]]) % MOD2; } if (fa ! 0) { ru1 (ru1 W1[up1]) % MOD1; ru2 (ru2 W2[up2]) % MOD2; } allHashes.insert({ru1, ru2}); for (int v : g[u]) { if (v fa) continue; ull nu1 (ru1 - W1[h1[v]] MOD1) % MOD1; ull nu2 (ru2 - W2[h2[v]] MOD2) % MOD2; getWeight(nu1, nu2); reroot(v, u, nu1, nu2); } }这个写法里W1和W2是两个映射表把哈希值映射成随机权重。如果不用双哈希只保留一组权重碰撞风险在正式比赛里不可接受后面会细说。4.3 完整判定流程判断A树能否与B树同构流程分三步。第一步对A做一次普通DFS预先得到以某个固定节点为根的哈希然后以A的每个节点为根跑一遍换根DP把所有可能的无根哈希存入集合。第二步对B同样做换根DP对每个节点的根哈希检查是否出现在集合里。第三步如果出现了说明A和B存在同构关系输出对应的根节点信息。如果题目要求的是“B中是否存在某个连通子图与A同构”也就是B比A大那么需要在B上对每个节点枚举“只保留一部分分支”的哈希相当于做子树截断后再比较。这个操作仍然可以用可减哈希完成比如对每个节点枚举它保留哪些孩子分支但复杂度会高一些需要用树上背包的思想按子树大小做限制。赛场上如果时间不够先把同构判断写对拿一部分分再考虑扩展。4.4 哈希碰撞与精度控制树哈希本质上是一个概率算法虽然实际比赛中碰撞概率极低但被卡过的人绝对不会只写单哈希。单模自然溢出很容易被构造数据定向碰撞尤其是随机权重本身如果生成方式被摸清的情况下。我的习惯是双模数加随机权重模数选1e97和1e99权重用mt19937_64随机生成。判断相等时两个模数都必须相等。有些选手会直接用unsigned long long自然溢出当作一个哈希这也不是不行但强烈建议再加一个质数模。双哈希的时间开销很小换根DP本身就O(n)多一次运算无伤大雅。还有一点权重分配表的map查找在递归里很频繁用unordered_map会快很多。但unordered_map在哈希碰撞攻击下可能退化建议提前reserve或者直接用数组把哈希值映射到一个自增索引再存随机权重效率更高也更稳。5. A题裴蜀定理判可行性同余最短路求最小步数5.1 先看是否有解裴蜀定理A题的问题形态本质上是给定两个操作数a和b目标模数M以及目标余数c问能否通过若干次“加上a或加上b再取模”的操作从0走到c。先不要急着跑最短路第一步应该用裴蜀定理判断无解。因为每次加a或加b当前值模gcd(a,b)永远不会变。从0出发能到达的状态必须满足“该状态模gcd(a,b)等于0”。再考虑取模M的影响整体能到达的余数集合是gcd(a, b, M)的倍数。所以如果c不是gcd(a, b, M)的倍数直接无解这是O(log)的判断比跑一遍最短路快得多也能避免在无解数据上浪费大量时间。如果gcd为1那理论上所有余数都可达接下来要解决的是“最小步数”问题。这个最小步数是经典的同余最短路模型。5.2 同余最短路的建图方式把0到M-1这M个余数看成图上的节点。从节点x出发加a取模到(x a) mod M加b取模到(x b) mod M两条边的边权都是1。问题是求0到目标c的最短路。由于边权全是1直接用普通BFS就够了不需要Dijkstra。但要注意M可能到1e6级别邻接表根本不用建每次转移算出两个后继节点就行。visited数组和dist数组都用int初始化为无穷大。如果数据范围更大比如M到1e9就不能开数组。这时候先用裴蜀定理把问题缩小把所有数同时除以gcd(a, b, M)等价类就压缩到了可处理大小。具体的压缩方法是令g等于gcd(a, b, M)只保留c mod g为0的余数类把a、b、c、M全部除以g后重新建图。5.3 代码骨架与路径还原int solve(int a, int b, int M, int c) { if (c % __gcd(__gcd(a, b), M) ! 0) return -1; vectorint dist(M, INF); queueint q; dist[0] 0; q.push(0); while (!q.empty()) { int x q.front(); q.pop(); int y1 (x a) % M; int y2 (x b) % M; if (dist[y1] dist[x] 1) { dist[y1] dist[x] 1; q.push(y1); } if (dist[y2] dist[x] 1) { dist[y2] dist[x] 1; q.push(y2); } } return dist[c]; }如果需要输出具体操作序列就维护一个pre数组每次松弛时记录是从哪个状态、哪个操作转移过来的最后从c倒推回0。因为边权为1BFS天然保证了第一次到达时的路径就是最短的pre不会反复更新。5.4 这类题的通用套路同余最短路不只是这一道题用得上。给定若干种面额问凑出某个余数的最小数量给定若干种步长问从0到目标模值的最短步数甚至某些线性丢番图方程求非负整数解也可以转化成同余最短路。看到“若干操作 模意义下 最小步数”这三个特征同时出现基本就可以往这个模型上联想。一个提高效率的细节是如果a和b都是M的因子那么BFS的图会退化成若干个互不相连的环可以先按gcd缩点。否则直接跑也不慢。现场很多人纠结要不要用01BFS其实只有在边权是0和1的时候才需要这题边权全1普通队列就是最优解。6. M题签到题也要按流程来6.1 从样例反推结论M题我印象里是一个读完题就能写结论的签到大意和取石子或者模4判断有关最终落点是一个奇偶或者模周期性判断。这类题最忌讳的是拿到题就开始枚举情况正确的打开方式是先写一个爆搜在小范围内把所有可能结果打出来看规律再证明。以取石子博弈为例如果规则是每人每次取1到3个取到最后一个的赢那爆搜会发现只要n是4的倍数先手必败否则先手必胜。因为你无论取几个后手都可以把每轮凑成4个最后把局面留给你面对4的倍数。M题如果也是这种结构结论推导完全一致。不要觉得这个流程小题大做区域赛的签到题现场翻车率其实很高。因为大家急着抢一血样例一过就交结果WA在边界上。签到题更要稳。6.2 最小可用的判断代码puts(n % 4 0 ? No : Yes);这种代码没有任何复杂的数据结构但前提是结论完全正确。交之前至少构造三组测试最小的n、恰好是结论临界点的n、比较大的n。比如n等于1、2、3、4、5都跑一遍确认没有越界逻辑。如果题目的一句话题面不是这个思考方式和上面一样找到状态转移里的周期压缩成常数判断。不要想着靠记忆背模板区域赛签到题的包装千变万化背不住的。6.3 不要因为题目简单就乱交很多队伍签到最后变成负贡献不是因为不会做而是因为过早提交又反复WA白白增加罚时。我的习惯是签到题至少两个人确认结论一个人写代码另一个人拿样例和暴力对拍。区域赛一次罚时20分钟与其抢两分钟的一血不如稳一手。另外M题这种题经常藏在榜末不一定题号最小就最简单。开题前先全局扫一遍所有题面的第一段把明显是送分的题找出来。这个动作能节省大量时间也能避免全队在一道题上钻进死胡同。7. 复盘后的几个通用习惯这次杭州站复盘之后我给自己定了几条规矩写出来供参考。第一卡题超过30分钟必须把模型写在纸上而不是在脑子里反复绕。K题和C题虽然模型不同但都是“先抽象成数学结构再写代码”的类型。空想很容易漏条件写下来反而能看清楚哪些是托词、哪些是真实难点。第二背包问题先想清楚状态能不能合并。C题如果一上来就按“当前是谁被扣”设二维状态复杂度很难压换一个角度枚举最大值反而简单。分组背包的变种在区域赛出现频率很高状态设计要学会往“枚举特殊项”这个方向靠。第三涉及哈希的题目一律双哈希没有例外。G题的随机权重方案虽然概率极低但赛场上一旦被构造数据卡掉整个队伍的节奏就崩了。双模数只是多写几行性价比极高。第四签到题也要做边界测试。M题这种题WA一次浪费的罚时可能比后面一道中等题多写两分钟还贵。样例通过只是开始临界值和最小值才是翻车点。第五补题比刷新题重要。我每次区域赛后都会挑五道题重新写一遍并且不只写标准做法还会把现场错误版本和正确版本放在一起对比。这个方法帮我避开了很多同类坑。这套杭州站复盘帖就是在这种对比习惯下整理出来的。
分析法实现IF-ELSE翻译程序：四元式与真假链回填)
