AtCoder Beta赛题解：取模哈希前缀和状压DP线段树

昨晚AWC 0009 Beta结束之后我把五道题的代码都重写了一遍顺手把做题时踩到的坑记了下来。AtCoder Weekday Contest 0009 Beta这套题从名字就能看出来是一个偏测试性质的比赛题面风格很接近标准的ABC难度A题送分B题需要一点点哈希思维C题如果反应不过来前缀和会卡一会儿D题是典型的状压DP模板E题则落在经典的线段树区间最大子段和上。整套题覆盖的知识点非常集中取模边界、哈希计数、前缀和差值、状态压缩DP、区间信息合并基本就是把平时刷题最常用的那几把刀都拿出来磨了一遍。如果你是刚接触AtCoder的选手建议先跟着A-C走一遍重点体会“为什么这样想”如果你已经在稳定AC A-C那这篇的D和E部分值得逐行看尤其是E题的查询合并逻辑我自己在比赛里就栽了一次。下面我按比赛顺序逐题聊。1. 先看整体这五道题到底在考什么1.1 难度与知识点分布这场的A到E难度曲线非常规整前两题是纯粹的送分题第三题开始需要一点思维转化第四题进入算法模板第五题才是真正考验代码综合能力的压轴。我整理了一张表方便你对照自己卡在哪一层题号题目名核心考点难度定位AWhen is the Next Contest?取模运算、边界处理签到题BPair Sum哈希表、循环顺序新手友好CLongest Balanced前缀和、哈希映射思维转化题DTraveling Route状态压缩DP进阶模板题ERange Max Subarray Sum线段树、区间信息合并进阶压轴从这张表能看出Beta赛的定位很清晰不考偏门算法不玩复杂数学推理而是把最经典、最常考的知识点拿出来看你能不能写得稳。所以这场比赛很适合用来检验自己的基础是否扎实。1.2 我的做题节奏与时间分配我自己的时间分配是A题3分钟B题10分钟C题15分钟D题30分钟WA了一发E题40分钟第一次编译没过第二次AC。总共花了大约100分钟。这个节奏其实暴露了一个问题真正耗时的不是读题而是那些“我以为很简单”的边界条件。A题快是因为公式一眼就能写出来B题慢是因为我一开始差点写暴力D和E则是标准的模板题但因为细节没处理干净而返工。如果你在这个节奏里遇到了和我相同卡壳的点下面几节基本都能找到对应解释。1.3 本场比赛的三个关键词我复盘之后给这五道题提炼了三个关键词。第一个是“取模边界”。A题把星期几的1~7编号和取模运算搅在一起等着你踩“周日输出0”的坑还顺手埋了一个1e18的大整数。第二个是“用历史信息换时间”。B题的哈希表和C题的前缀和本质上在做同一件事把“每次重新扫一遍”变成“查一下之前存好的表”。很多看似需要暴力的题一旦你意识到可以存历史信息复杂度立刻从O(n²)掉到O(n)。第三个是“区间信息合并”。E题几乎就是为了这个主题而生的。单点修改加区间查询这种组合一旦出现线段树就是标准答案但如何合并左右儿子的信息才是真正的考点。2. A题星期计算的取模陷阱2.1 题意还原题目输入两个数D和X。D表示当前是星期几用1到7表示1代表周一7代表周日。X表示距离下一场比赛还有多少天X的上限给到了1e18。要求输出X天之后是星期几同样用1到7表示。这题看起来就是一行公式的事但它埋了两个非常经典的坑一个是星期编号从1开始而不是从0开始另一个是X的范围大得离谱。2.2 从模拟循环到O(1)公式的推导最直觉的做法是for循环X次每次让星期数加1到7之后回到1。但看到X ≤ 1e18这个方案立刻作废。哪怕一秒钟跑一亿次循环也要跑三百多年才能读完整个X这显然不是出题人的意图。所以直接算模。星期数每过一天加1本质上就是对7取模。但这里有一个很隐蔽的问题编号是1到7而不是0到6。直接用(D X) % 7当结果落在星期天时算出来的是0不是7。解决办法是先把编号整体减1取模之后再加回来。公式写成ans (D X - 1) % 7 1验证一下假设当前是周六D 6X 1正确答案是周日也就是7。直接用(D X) % 7算出来是0而用上面的公式 (6 1 - 1) % 7 1 6 % 7 1 7正确。再试一个跨越一周的例子D 1X 7下周一(1 7 - 1) % 7 1 7 % 7 1 1正确。我敢说这个“减一加一”是很多人写日期类题目时翻车的点。它错得悄无声息如果样例刚好没覆盖周日你根本发现不了。这也是为什么AtCoder的A题经常给人“样例过、提交WA”的体验。2.3 参考实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long D, X; cin D X; long long ans (D X - 1) % 7 1; cout ans \n; return 0; }代码短到有点不像一场算法竞赛的第一题但注意这里用的是long long而不是int。X上限1e18D X虽然后果不大但如果你在比赛中习惯性写intWA就是一瞬间的事。2.4 两个容易忽略的点第一是long long。AtCoder的A题特别喜欢在那种“一秒能算完”的公式里埋伏数据范围让你以为很简单结果因为类型不够宽直接吃罚时。我之后学乖了读入任何变量先看一眼题目的数据范围约束再决定用int还是long long这个习惯能帮你省下大量无意义的WA。第二是输出别用endl。endl会强制刷新输出缓冲区在输出量大的题目里会明显拖慢速度。用\n就够了这是一个很小的习惯但对竞技编程来说很重要。3. B题不要见着两数之和就写两层for3.1 题意还原这题给定一个长度为n的整数数组a以及一个目标值K。要求统计有多少个下标对(i, j)满足两个条件i j并且a[i] a[j] K。n给到了2e5a[i]和K的范围都在1e9左右。“两数之和”这四个字一出来很多人的第一反应是写两层循环但这题这么做必死。3.2 双重循环为什么在这里是陷阱n 2e5时两层for循环的比较次数大约是4e10。C一秒钟大概能跑1e8到1e9次基础操作也就是说暴力要跑几十秒到几分钟这在线性递推题和哈希表题面前完全不可接受。而且这题的考察点不是“能不能写对暴力”而是“能不能想到用空间换时间”。你看题目给定的数组是无序的又不能排序后二分排序会破坏下标关系所以唯一合理的思路就是一边扫描数组一边用东西记录已经看过的数。3.3 哈希把查找变成O(1)与“先查后插”的顺序对于当前读到的数x能和它配对的另一个数一定是K - x。我们不需要关心未来会出现什么只需要知道在已经读过的所有数字里K - x出现了多少次。于是算法很自然用一个哈希表cnt记录每个数出现的次数每读到一个x先把cnt[K - x]累加到答案再把cnt[x]加1。这里有一个特别容易写错的细节为什么必须先查后插如果先插再查当K 2x时当前这个x会被自己和自己的配对算进去一次。举个例子数组里只有一个数5K 10正确答案应该是0但先插再查会得到1。更严重的是如果后面还有一个5先插再查会把(i, j)和(j, i)这种重复配对都算进去答案直接翻倍。先查后插的逻辑保证了一个数只和它左边已经出现过的数配对天然满足i j不会重复。3.4 参考实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long K; cin n K; unordered_maplong long, long long cnt; long long ans 0; for (int i 0; i n; i) { long long x; cin x; ans cnt[K - x]; cnt[x]; } cout ans \n; return 0; }复杂度是O(n)时间、O(n)空间。注意这里cnt的键值都用long long因为K - x完全可能是负数而且K本身给到了1e9加上a[i]之后运算结果可能超过int上限用long long是最稳妥的选择。3.5 一个关于unordered_map被卡的实战经验大多数情况下unordered_map能轻松AC但我印象很深的是在某次比赛里见过有人用unordered_map被精心构造的数据卡到超时。原因是C标准库的unordered_map默认哈希函数在特定整数序列上会产生大量冲突导致查找退化到接近O(n)。AtCoder的一般比赛不太会这么狠但如果想保险有两个替代方案一是直接用std::mapO(log n)的复杂度在2e5数据量下完全够用二是给unordered_map挂一个自定义的splitmix64哈希函数。我个人的习惯是只有在卡常严重的题目里才用第二种方案平时用map反而更省心毕竟wa比tle更容易让人烦躁。4. C题最长平衡子串前缀和的经典变式4.1 题意还原给定一个长度为n的01字符串sn不超过2e5。要求找出最长的连续子串使得子串中0和1的数量相等。如果不存在这样的子串输出0。这题直接的想法是枚举所有子串统计0和1的数量但那是O(n²)的复杂度2e5的数据量根本跑不动。所以需要换一个角度。4.2 关键一步把0改写成-1这个转化我觉得是整场比赛里最漂亮的一步。把0记成-11记成1那么一个区间里0和1数量相等就恰好等价于这个区间的累加和为0。两个变量的比较问题被压缩成一个标量的相等问题这比分别统计0的数量和1的数量要优雅得多。用生活化的话说就像记账时把支出记为负数、收入记为正数想知道一段时间是否收支平衡只要看余额是不是0就行。不用分别合计收入和支出这个“余额为0”的判断就是我们的目标。有了这个转化定义prefix[i]表示前i个字符的累加和。那么区间(l, r]的累加和为0等价于prefix[l] prefix[r]。题目于是变成了在所有满足prefix[i] prefix[j]的下标对中求最大的j - i。4.3 为什么哈希表里存的是“最早出现的下标”既然要最大距离那么对于同一个前缀和值我们只关心它第一次出现的位置。后续再遇到相同值时拿当前下标减去最早出现的下标一定比减去一个更晚的下标得到的长度更长。这个点特别容易想反有些新手会把最新位置不断覆盖进哈希表导致每个值只能配出长度为1的区间答案当然不对。另外千万别忘了把prefix[0] 0、位置0放进哈希表。比如s 10前缀和序列是0, 1, 0第一个整段[1,2]对应的就是prefix[2] prefix[0] 0。如果不初始化prefix[0]从字符串开头出发的合法子串会被全部漏掉。4.4 参考实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; string s; cin n s; unordered_mapint, int first; first[0] 0; int pref 0; int ans 0; for (int i 1; i n; i) { if (s[i - 1] 1) pref; else pref--; if (first.count(pref)) { ans max(ans, i - first[pref]); } else { first[pref] i; } } cout ans \n; return 0; }复杂度O(n)已经很优了。边界情况也简单如果字符串全是0或者全是1那么所有前缀和互不相同ans始终是0输出0符合题意。4.5 同一思路能推广到什么题目这套“前缀和加哈希表”的模板在LeetCode上有一大批亲戚题和为K的子数组个数、和至少为K的最短子数组、以及“最长子数组和为0”的加强版。处理一般的整数数组时只需要把前缀和改成按a[i]直接累加把s[i - 1] 1的判断改成a[i]即可核心逻辑完全不动。所以C题非常值得当模板题收藏。5. D题哈密顿回路的最短路状压DP标准模型5.1 题意还原这题给了一个n乘n的距离矩阵n不超过16。dist[i][j]表示从城市i到城市j的距离可能很大如果dist[i][j] -1表示没有办法直接走这条路。要求从城市0出发恰好经过每个城市一次最后回到城市0输出整个回路的最短距离。如果不存在这样的回路输出-1。这题本质上是一个带权完全图上找最短哈密顿回路的问题但不一定完全连通因为有-1的限制。5.2 为什么DFS剪枝也扛不住n16最简单的想法是DFS枚举全排列。16的阶乘大约是2.09e13即使剪枝能删掉大部分状态剩余搜索树仍然是指数级的规模。n 12的时候DFS或许还能碰碰运气n 16就必须上状态压缩DP了。状态压缩的核心思想是“已经访问过哪些城市”本身就是一个完整且精确的状态。我们用二进制mask来表示它每一位代表一座城市是否已经访问过这样就能把重复的搜索子树合并掉。n 16意味着有2^16 65536种不同的访问集合这个数量完全可以直接枚举。5.3 状态设计定义dp[mask][i]表示当前已经访问过的城市集合为mask并且当前停留在城市i时已经走过的最短路径长度。mask的第k位为1表示城市k已经被访问过。因为起点固定为城市0所以初始状态是dp[1][0] 0表示集合里只有0号城市当前在0号城市。为什么需要二维而不是只存mask因为下一步要去哪个城市取决于当前停在哪座城市。只知道mask不知道当前位置的话转移无从谈起。所以在状压DP里“当前在哪”这维信息几乎总是少不了的。5.4 状态转移与循环顺序从某个状态dp[mask][i]出发先要求i确实在mask中然后枚举一个不在mask中的城市j如果dist[i][j]不是-1就可以尝试用dp[mask][i] dist[i][j]去更新dp[mask | (1 j)][j]。循环顺序上外层按mask从小到大枚举即可。理由很直观每次转移都会让mask至少多一个二进制1位所以新状态对应的mask数值一定大于旧状态。从小到大枚举正好让所有前置状态在轮到它们时都已经被算好这也是状压DP天然的无后效性。如果你以后见过有的题需要按集合大小分层那是因为转移可能发生在mask大小相同的状态之间这道题不会出现那种情况。最后当mask变成全1的full时枚举最后停留的城市i用dp[full][i] dist[i][0]更新答案。如果dist[i][0]不可达就跳过。5.5 参考实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorvectorint dist(n, vectorint(n)); for (int i 0; i n; i) { for (int j 0; j n; j) { cin dist[i][j]; } } if (n 1) { cout 0 \n; return 0; } const int INF 1e9; int full (1 n) - 1; vectorvectorint dp(1 n, vectorint(n, INF)); dp[1][0] 0; for (int mask 1; mask full; mask) { if (!(mask 1)) continue; for (int i 0; i n; i) { if (!(mask (1 i))) continue; if (dp[mask][i] INF) continue; for (int j 0; j n; j) { if (mask (1 j)) continue; if (dist[i][j] -1) continue; int nmask mask | (1 j); dp[nmask][j] min(dp[nmask][j], dp[mask][i] dist[i][j]); } } } int ans INF; for (int i 0; i n; i) { if (dist[i][0] -1) continue; ans min(ans, dp[full][i] dist[i][0]); } cout (ans INF ? -1 : ans) \n; return 0; }很多选手关心这个DP到底算多少遍我实际算了一下n 16时把所有的mask、最后停留点、下一个点的枚举加起来完整转移次数大约只有两百万次。对比16!这个加速完全就是状态压缩的威力。5.6 我在这一题上交WA的两个真实坑第一次WA出在最后一步。我只写了ans min(ans, dp[full][i] dist[i][0])没有判断dist[i][0]是不是-1。当i回不到0时-1会参与加法得到一个比INF小得多但看起来完全正常的数。因为INF取1e9时INF (-1)约等于999999999然后被min当成“最优答案”取走了。这个Bug非常恶心因为结果看起来像是合法距离你很难怀疑它。后来我养成习惯凡是涉及-1代表不可达的题目在做加法之前一定先检查能不能走这条路。第二个坑是n 1的情况只有一座城市时从0出发经过它再回到0路程就是0。没加这个特判程序可能会去访问dp[0][...]或者直接越界。Beta赛里这种边界题很常见考的就是你读题时有没有注意到n的下界。6. E题区间最大子段和的线段树解法重点在四个信息6.1 题意还原给定一个长度为n的整数数组an和操作次数q都不超过2e5。a[i]可以是正数也可以是负数。操作有两种第一种操作是单点赋值把某个位置的数改成v第二种操作是查询区间[l, r]内最大子段和这里的子段必须非空。单点修改加区间查询的组合几乎就是线段树的出场信号。但这题的关键不在线段树本身而在于节点里到底要维护什么信息。6.2 为什么不能只存一个“区间最大值”线段树节点如果只存一个最大值mx合并左右儿子时只能取max(L.mx, R.mx)。但最大子段和还有可能横跨两个儿子从左儿子的右半部分一直延续到右儿子的左半部分。光有mx这个跨中点的子段根本算不出来。所以需要扩充分信息。任何一个区间都可以用四个值描述sum区间总和lmx必须包含区间左端点的最大前缀和rmx必须包含区间右端点的最大后缀和mx区间最大非空子段和记住lmx和rmx的理由很直观跨中点的子段起点一定在左区间终点一定在右区间所以它由左区间的某个后缀和右区间的某个前缀拼接而成。没有这两个信息跨中点的答案就是空中楼阁。6.3 合并公式的推导假设左儿子是L右儿子是R把两者合并成父节点P那么P的四个值分别这样算P.sum L.sum R.sumP.lmx max(L.lmx, L.sum R.lmx)P.rmx max(R.rmx, R.sum L.rmx)P.mx max(L.mx, R.mx, L.rmx R.lmx)lmx的两种可能要么最大前缀完全落在左儿子里也就是L.lmx要么从L的最左边一路延伸到R的某个位置这种情况下前半段是整个L后半段是R的lmx所以是L.sum R.lmx。rmx完全对称。mx的三种可能整个子段完全在左儿子、完全在右儿子、跨过中点。跨中点就是L.rmx R.lmx。用一个具体数组验证这个公式[−2, 1]和[3, 4]合并。L区间[−2, 1]的mx是1R区间[3, 4]的mx是7但L.rmx R.lmx 1 7 8对应子段[1, 3, 4]这才是真正的最大子段和。如果只存mx我们只会得到7丢掉正确答案。这个例子能很清楚地说明为什么四元组缺一不可。6.4 查询操作里最容易出错的合并逻辑标准线段树的查询函数返回值应该是Node而不是一个整数。为什么非要这样因为查询区间可能横跨多个线段树节点这些节点之间也要按相同的合并公式组合。如果你写成返回int、两边直接取max那等于完全无视跨中情况答案必错。查询里的边界分支条件要和build、update保持一致。我自己常用的写法是这样的Node query(int p, int l, int r, int ql, int qr) { if (ql l r qr) return seg[p]; int mid (l r) 1; if (qr mid) { return query(p 1, l, mid, ql, qr); } if (ql mid) { return query(p 1 | 1, mid 1, r, ql, qr); } return combine( query(p 1, l, mid, ql, qr), query(p 1 | 1, mid 1, r, ql, qr) ); }其中qr mid和ql mid两个直退分支必须写对。漏掉其中一个或者把等于号写反都会让递归多走一路并在合并时把不该包含进答案的区间也合进去最终得到错误结果。6.5 参考实现#include bits/stdc.h using namespace std; struct Node { long long sum; long long lmx; long long rmx; long long mx; }; int n, q; vectorlong long a; vectorNode seg; Node combine(const Node L, const Node R) { Node res; res.sum L.sum R.sum; res.lmx max(L.lmx, L.sum R.lmx); res.rmx max(R.rmx, R.sum L.rmx); res.mx max({L.mx, R.mx, L.rmx R.lmx}); return res; } void build(int p, int l, int r) { if (l r) { seg[p] {a[l], a[l], a[l], a[l]}; return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); seg[p] combine(seg[p 1], seg[p 1 | 1]); } void update(int p, int l, int r, int pos, long long v) { if (l r) { seg[p] {v, v, v, v}; return; } int mid (l r) 1; if (pos mid) { update(p 1, l, mid, pos, v); } else { update(p 1 | 1, mid 1, r, pos, v); } seg[p] combine(seg[p 1], seg[p 1 | 1]); } Node query(int p, int l, int r, int ql, int qr) { if (ql l r qr) { return seg[p]; } int mid (l r) 1; if (qr mid) { return query(p 1, l, mid, ql, qr); } if (ql mid) { return query(p 1 | 1, mid 1, r, ql, qr); } return combine( query(p 1, l, mid, ql, qr), query(p 1 | 1, mid 1, r, ql, qr) ); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n q; a.resize(n 1); seg.resize(4 * (n 1)); for (int i 1; i n; i) { cin a[i]; } build(1, 1, n); while (q--) { int op; cin op; if (op 1) { int x; long long v; cin x v; update(1, 1, n, x, v); } else { int l, r; cin l r; Node ans query(1, 1, n, l, r); cout ans.mx \n; } } return 0; }复杂度是每次操作O(log n)整体O((n q) log n)。注意Node里的四个值全部用long long因为a[i]可以到1e9多个负数相加、再跨区间合并之后答案很容易超过int范围。这个问题我在自己第一次写这类题时也吃过亏。6.6 一个关于空子段的延伸这道题要求最大子段必须非空所以即使数组全是负数答案也是最大的那个负数而不是0。LeetCode 53那类允许空子段的题目是另一个版本做法也不一样允许空子段时lmx和rmx可以为0mx至少是0sum仍然照常维护。这个改动可以作为课后练习把上面代码改上几行看它能否正确处理全负数的情况。能把这个改动想明白说明你对lmx和rmx的语义已经是真理解而不是背板子了。7. 赛后复盘我建议下一场AWC这样准备这场Beta赛打完我最大的感受是题本身不难但每个坑都藏在“理所当然”里。A题的星期模7、B题的哈希顺序、C题漏掉的prefix[0]、D题的-1回程、E题的查询合并五个看似独立的考点其实指向同一个能力——在会写代码之外能不能稳准地处理边界条件。对新手来说A到C是非常好的“想清楚再写”训练。建议在草稿纸上先把公式和边界列出来再敲代码不要急着提交。对想冲击D和E的朋友状压DP和线段树是AtCoder中段题的常客模板要练到能在一分钟内默写出来的程度尤其是线段树的Node合并函数那道query的分支判断值得反复默写几遍。最后分享一个我坚持了很久的小习惯每场周赛结束后不管AC没AC都把每道题的重写版本存到本地并在代码注释里写一句这题最容易错的地方。坚持十几场下来你会发现自己看题的第一反应明显变快因为很多坑你已经提前踩过了。下一场AWC正赛我准备拿这套复盘经验去试试尤其是这次WA过的两个点我不允许自己再交同样的学费。