Arrow a Row题解：贪心与区间覆盖的建模技巧

ICPC 2024 Chengdu的R题Arrow a Row赛后我复盘了很久发现它表面是个模拟题实际考的是做区间覆盖时的建模能力。如果你在赛场上拿到这题最该做的不是急着写模拟而是先问一句一次操作到底在“传播”什么想明白这一点代码其实十几行就能写完。这篇题解我会从题面还原开始逐步拆解操作的本质给出一个可复现的贪心做法再把我调试过程中踩过的坑、写错的第一版思路一起放出来希望对你备战区域赛有帮助。1. 题目到底在问什么1.1 题面还原先把题面固定下来。给定一个长度为n的字符串s字符串只由和两种字符组成。每次操作可以选择一个长度恰好为k的连续子串如果这个子串最左边的字符当前是就可以把整个子串全部改成。目标是把整个字符串变成全求最少操作次数如果做不到输出-1。这和我印象中现场英文题面“Arrow a Row”对应得上一排箭头每次可以把一段连续且段首是右箭头的区间“刷”成右箭头。字符集和操作方式可能有细节出入但核心模型就是这个。这里输入格式按常见ICPC习惯处理第一行T为测试组数接下来每组先给n和k再给字符串s数据范围我不完全确定但下面做法的复杂度是O(n)只要能开到2e5、1e6量级都能直接过。很多人第一眼看到这题会以为是纯模拟每次扫描找到符合条件的一段改掉再扫描。但仔细想一下就能发现一次操作之后区间里的所有字符都变成可能会让原本不能作为左端点的位置变得可用这种状态变化和“感染”“扩散”很像暴力模拟很难保证步数最少。1.2 把操作翻译成“向右发射”我更喜欢把一次操作理解成一个“向右发射”的动作发射点当前已经是的位置l。发射方向只能向右。覆盖范围以l为左端点、长度为k的区间[l, lk-1]。发射效果区间内所有字符都变成。之所以强调“只能向右”是因为操作要求子串的最左端必须是而这个字符天然带有“指向右边”的语义。你没有办法把一个左箭头作为区间的左端点所以这个操作本质上是在把一个已经可靠的位置当作起点向右边“推进”k格。用生活化的类比来说就像你手里有一根火把火把本身必须已经点燃对应左端点是然后你才能用它点燃前面k个位置。火把点完之后不会熄灭你还可以在已经点燃的区域里重新选一个更靠右的位置作为下一次点燃的起点。这就是这道题最核心的直觉已经变成的区域是你后续所有操作的“根据地”。1.3 一个容易被带偏的直觉我在赛场上第一反应是从右往左做理由很简单如果我要把某个位置的变成那它一定是某次操作的右端点或者被某次操作覆盖从右往左扫能保证“我处理过的地方以后不会再被改动”。这个思路在普通区间染色问题里很常见但在这题会直接翻车。原因在于操作会改变左端点的状态。举例来说s k 2。从右往左看会发现位置3是想覆盖它必须让位置2成为左端点而位置2原本是看起来无解但实际从左边开始先操作[0,1]位置1变成再操作[1,2]位置2变成最后操作[2,3]整个串就能变全。也就是说从右往左会漏掉“左侧操作先激活右侧左端点”这条路径。这个反例直接告诉我这题必须从左往右看而且一定要维护好“当前已经全部变成的前缀”。2. 关键观察维护“已经全是的前缀”2.1 前缀是唯一的靠山先定义变量cnt表示当前下标[0, cnt-1]这一段已经是全。初始时cnt就是从0开始连续的长度。比如字符串前两个字符是那么cnt 2如果字符串开头就是cnt 0。为什么只关心前缀因为任何一次操作都必须选一个当前字符是的位置作为左端点。如果某个出现在最左边也就是cnt0且s[0]那么没有任何左端点可用因为能作为左端点的位置必须在前缀里而前缀为空所以直接无解。更一般地所有能用来“发射”的起点一定是已经在前缀里的位置或者被之前某次操作覆盖进去的位置。前缀越长你的选择余地越大能向右推进的空间也就越远。反过来如果字符串中间某个位置是但前面还有这并不影响你瞄准第一个。因为最终目标是把所有字符变成你迟早要处理这个而它是在所有更靠右的之前的所以必须先把它覆盖掉。这就是“从左往右处理”的合法性每次只关心第一个还没变成的。2.2 什么时候必须做一次操作假设当前cnt对应的位置s[cnt] 也就是说前缀到这里断了。设这个位置为p cnt。此时位置p是第一个还保持的位置在它左侧所有字符都已经变成。要让位置p变成它必须被某次操作覆盖。考虑这个操作的区间[l, lk-1]要覆盖p必须满足l p左端点在p左边或等于plk-1 p右端点至少到pl p-k1这是由前一条不等式推出来的l p-k1l必须是当前已经是的位置所以l cnt区间不能越界所以l n-k。把能选的l合起来就是一个闭区间[max(0, p-k1), min(cnt-1, n-k)]。只要这个区间里有任何一个整数l就存在一次可以覆盖p的操作如果这个区间是空的那没有任何合法操作能覆盖p整个问题无解。这里有个容易忽略的点l不需要等于p也不需要等于p-k1。l可以比p-k1更靠右只要它还在可行区间里。也就是说覆盖p的操作右端点可以比p更大。这一点正是很多错误贪心的坑。2.3 一个操作其实是在“跳”每次操作之后区间[l, lk-1]变成全。由于l本身在前缀里前缀[0, cnt-1]已经是新操作把前缀向右延伸到lk-1这一段所以更新后的cnt至少是lk。注意这里不一定要从p出发也不一定要用最左边的可行l。我们需要的是一个“跳得最远”的选择既然一次操作能让cnt变成lk而lk随l单调递增那么在可行区间里选择最大的l就能让前缀尽量向右延伸。这让我想到跳跃游戏你在一个一维坐标上手里有一个“可操作区间”每走一步都尽量跳到最远步数自然最少。只不过这里的“跳跃”不是走一步跳a[i]格而是“选一个已经激活的位置向右激活k格”并且你只能在已激活的位置里选起点。3. 正确贪心与实现3.1 贪心策略每次选最靠右的可用左端点于是我得到了一个很简洁的贪心维护cnt表示[0, cnt-1]已经全是。每次跳过连续已经是的位置即while cnt n且s[cnt] 时cnt。如果cnt n说明已经全结束。否则令p cnt位置p是第一个未被覆盖的。计算可行左端点区间[lower, upper]其中lower max(0, p-k1)upper min(cnt-1, n-k)。如果upper lower无解输出-1。否则取l upper做一次操作ans更新cnt max(cnt, l k)回到第2步。每次取upper也就是可行区间里最靠右的左端点。这样一次操作能覆盖到的最右位置lk-1是最大的前缀延长得最多。由于覆盖范围更大后续可选的起点不会变少所以步数不会比取其他左端点多。这里需要解释为什么取更大的l不会“漏掉”左侧的。因为在p左边前缀[0, cnt-1]已经是全这些位置本来就不需要再覆盖。而区间[l, lk-1]里左侧部分正好落在前缀内所以哪怕l更靠右也不会遗漏任何关键位置。本质上更靠右的l把一个长度固定的区间整体往右移损失的左侧部分本来就没有待处理内容赚到的是右侧覆盖得更远。3.2 为什么这是最小步数必要性部分当前p是第一个未覆盖的任何可行解都必须在这一步之后让p变成因此这一步操作必须落在可行区间[l, lk-1]里且左端点必须取可行区间中的某个值。如果可行区间为空任何方案都无法覆盖p只能无解。最优性部分用交换论证。假设某一步最优解选了左端点l1而贪心选了l2 upper l1两个l都能覆盖当前p。操作l1后新前缀变成l1k操作l2后新前缀变成l2k明显更靠右。更靠右的前缀意味着后续能作为左端点的位置集合不会更小同时已经覆盖的字符不会重新变回所以把最优解里的l1换成l2剩下的求解过程只会更容易不会需要更多操作。因此每一步贪心都是安全的总步数就是最小步数。这个证明虽然简短但足够说服我自己。比赛中不需要写得这么严格但心里得有这根弦。3.3 C 代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n, k; string s; cin n k s; if (k n) { bool all true; for (char c : s) if (c ! ) all false; cout (all ? 0 : -1) \n; continue; } int cnt 0; while (cnt n s[cnt] ) cnt; if (cnt n) { cout 0 \n; continue; } int ans 0; bool ok true; while (cnt n) { int p cnt; int lower max(0, p - k 1); int upper min(cnt - 1, n - k); if (upper lower) { ok false; break; } int l upper; ans; cnt max(cnt, l k); while (cnt n s[cnt] ) cnt; } cout (ok ? ans : -1) \n; } return 0; }复杂度是O(n)因为cnt单调递增每个位置最多被跳过两次一次是初始或操作后的while跳过一次是作为p被处理。空间O(1)。在实际比赛中这个代码非常快即使是n2e5、T很大也能轻松跑完。3.4 Python 版本如果你习惯用Python写题或者想在本地快速验证思路可以直接用下面这版。逻辑和C完全一样只是为了处理多组输入稍微包装了一下。import sys def solve(): data sys.stdin.read().strip().split() it iter(data) T int(next(it)) out [] for _ in range(T): n int(next(it)) k int(next(it)) s next(it) if k n: out.append(str(0 if all(c for c in s) else -1)) continue cnt 0 while cnt n and s[cnt] : cnt 1 if cnt n: out.append(0) continue ans 0 ok True while cnt n: p cnt lower max(0, p - k 1) upper min(cnt - 1, n - k) if upper lower: ok False break l upper ans 1 cnt max(cnt, l k) while cnt n and s[cnt] : cnt 1 out.append(str(ans if ok else -1)) print(\n.join(out)) if __name__ __main__: solve()两种代码的核心都只有那么几行关键就是第16到22行那个区间判断。如果你只记住了思路忘了代码细节也能很轻松地现场推出来。4. 边界条件与易错点4.1 整串已经是全的情况如果输入串本身全那一次操作都不用做答案直接是0。我的代码里第一个while就会把cnt推到n然后cnt n输出0。这个特判很自然但初学者容易漏掉尤其是k比较大的时候可能误以为必须做点什么才能变全。4.2 n k的情况如果k大于n任何长度恰好为k的连续子串都不存在那只要字符串里有任何一个就永远无法把它变成直接输出-1。如果字符串已经全输出0。这个特判最好单独写避免后面n-k变成负数导致upper/min的逻辑混乱。我在第一版代码里没有单独处理结果upper min(cnt-1, n-k)出现负数还和lower比较出了一个很隐蔽的错。后来加了这个特判代码立刻干净很多。4.3 第一个字符是的情况如果s[0] cnt初始为0。此时p 0lower max(0, 0-k1) 0upper min(-1, n-k) -1upper lower直接判无解。这是因为能作为操作左端点的位置必须本身是而位置0是没有任何办法覆盖它任何操作区间要覆盖位置0左端点只能是0但左端点0不满足的条件所以无解。这个结论也可以在脑内直接得到第一个字符如果是永远不可能变成。4.4 区间右边界 n-k当你计算upper时一定要记得限制l n-k否则操作区间会越界。这个限制很容易被漏掉。比如n5k3n-k2这意味着左端点最大只能是2因为l3时区间[3,5)会超出字符串末尾。我见过有的题解不限制这个而是把cnt推到n-k之间其实不够严谨。如果l取太大即使它在前缀里操作也会越界这会让程序在边界数据上出错。最稳妥的写法就是我上面代码里的upper min(cnt-1, n-k)。5. 常见错误与Debug实录5.1 我第一版贪心错在哪我最初写的贪心不是“取最靠右的可行左端点”而是“每个未覆盖的都必须作为某次操作的右端点”。具体来说看到p是我就强制让区间右端点为p左端点为p-k1然后检查这个左端点当前是不是。这个做法看起来很有道理因为覆盖p的所有区间中右端点最小的就是以p为右端点的那一个右端点越小越不会影响右边的状态。结果被s k 2这个反例干碎了。位置1是第一个强制以它为右端点左端点为0位置0是操作后串变成没问题接着位置2是强制以它为右端点左端点为1位置1已经被覆盖成操作后 也没问题再操作位置3也能行。这个例子我的第一版贪心其实能过。真正崩的是s k 3。位置1是强制右端点1左端点-1直接判无解。但实际有解先操作[0,2]把位置1覆盖掉再操作[2,4]两步搞定。也就是说为了覆盖p操作右端点可以比p更靠右不一定非要以p为右端点只要区间左端点是且区间覆盖到p即可。这个反例让我意识到这题不能把p当成“必须作为右端点”p只是“必须被覆盖”的目标。覆盖目标的区间可以向右延伸而为了后续扩展最优应该让左端点尽可能靠右也就是“用最右边的已激活位置作为发射点”。5.2 用对拍验证贪心因为贪心态类容易错我在本地写了一个暴力程序来验证小数据。暴力做法很简单用BFS枚举状态每个状态表示当前字符串只含和每次操作尝试所有可能的l只要s[l]是就生成下一个状态求到达全状态的最短步数。n不超过10时状态数最多2^10BFS完全跑得动。然后随机生成n和k把暴力和贪心的答案对比。跑了几万组发现唯一出问题的就是第一版“以p为右端点”的贪心修正成“每次选最右可行左端点”之后就再也没挂过。如果你在别的题上没信心强烈建议也写个对拍工程量不大但能省下大量debug时间。5.3 常见问题速查表症状原因处理办法全串输出-1忘记特判初始cntncntn时直接输出0s[0]输出错误答案左端点集合为空还继续算lower/upper判断或直接特判大k时数组越界没有限制ln-kupper取min(cnt-1, n-k)结果偏大强制以p为右端点改为取可行左端点区间的最右端结果偏小直接选最左可行左端点改成选最右可行左端点并证明不劣6. 赛后延伸这题的模型能迁移到哪6.1 本质是带限制的区间覆盖做完了回头看Arrow a Row的核心模型是“从已激活集合中选择一个起点向右覆盖定长区间”。这和很多经典贪心题是同一个骨架比如用最少的线段覆盖目标区间、跳跃游戏II、以及部分“感染”类问题。它们的共同点是每次行动的范围和起点有关而起点本身又是行动的结果所以必须维护一个“当前可达范围”每次都把可达范围推到最远。以后遇到这类题可以先问自己三个问题行动能覆盖多远本题是左端点k-1。从哪里可以出发本题是已经全是的前缀。怎样让后续选择最多本题是把前缀推到最远即取最靠右的出发左端点。三个问题想清楚代码自然就出来了。6.2 如果要输出操作序列题目如果只问次数那答案就是ans如果还要求输出每一步选的左端点只需要在循环里把每次的l记录下来最后按照顺序输出。因为贪心本身是构造性的每一步选的l都是合法操作所以不需要额外校验。例如前面s k 2最后记录的l序列是0、1、2对应的操作区间是[0,1]、[1,2]、[2,3]。现场模拟一下确实每一步都能执行。6.3 如果把目标改成全如果题目对称地换成“把区间变全要求左端点是”那整个做法完全镜像维护前缀全每次选最靠右的可行左端点所有逻辑反转即可。理解了这个模型做镜像版本基本是抄一遍的事。最后再分享一个小技巧这类“从左往右推进”的贪心写完代码后一定要用“开头是”、“末尾是”、“kn”、“k1”这几组边界数据自测。特别是k1时每个都必须自己作为左端点才能变等价于检查所有位置原本是否都是如果没处理好很容易在这一档翻车。我在这次复盘里就靠这些边界数据抓到了两个隐蔽的bug希望你看完这篇文章后也能少走这些弯路。