企业官网建设流程全解析

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, l+k-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。

为什么只关心前缀？因为任何一次操作，都必须选一个当前字符是>的位置作为左端点。如果某个<出现在最左边，也就是cnt=0且s[0]='<'，那么没有任何左端点可用，因为能作为左端点的位置必须在前缀里，而前缀为空，所以直接无解。更一般地，所有能用来“发射”的起点，一定是已经在前缀里的位置，或者被之前某次操作覆盖进去的位置。前缀越长，你的选择余地越大，能向右推进的空间也就越远。

反过来，如果字符串中间某个位置是>但前面还有<，这并不影响你瞄准第一个<。因为最终目标是把所有字符变成>，你迟早要处理这个<，而它是在所有更靠右的>之前的，所以必须先把它覆盖掉。这就是“从左往右处理”的合法性：每次只关心第一个还没变成>的<。

2.2 什么时候必须做一次操作

假设当前cnt对应的位置s[cnt] = '<'，也就是说前缀到这里断了。设这个位置为p = cnt。此时位置p是第一个还保持<的位置，在它左侧，所有字符都已经变成>。

要让位置p变成>，它必须被某次操作覆盖。考虑这个操作的区间[l, l+k-1]，要覆盖p，必须满足：

• l <= p：左端点在p左边或等于p；
• l+k-1 >= p：右端点至少到p；
• l >= p-k+1：这是由前一条不等式推出来的，l >= p-k+1；
• l必须是当前已经是>的位置，所以l < cnt；
• 区间不能越界，所以l <= n-k。

把能选的l合起来，就是一个闭区间[max(0, p-k+1), min(cnt-1, n-k)]。只要这个区间里有任何一个整数l，就存在一次可以覆盖p的操作；如果这个区间是空的，那没有任何合法操作能覆盖p，整个问题无解。

这里有个容易忽略的点：l不需要等于p，也不需要等于p-k+1。l可以比p-k+1更靠右，只要它还在可行区间里。也就是说，覆盖p的操作，右端点可以比p更大。这一点正是很多错误贪心的坑。

2.3 一个操作其实是在“跳”

每次操作之后，区间[l, l+k-1]变成全>。由于l本身在前缀里，前缀[0, cnt-1]已经是>，新操作把前缀向右延伸到l+k-1这一段，所以更新后的cnt至少是l+k。

注意这里不一定要从p出发，也不一定要用最左边的可行l。我们需要的是一个“跳得最远”的选择：既然一次操作能让cnt变成l+k，而l+k随l单调递增，那么在可行区间里选择最大的l，就能让前缀尽量向右延伸。

这让我想到跳跃游戏：你在一个一维坐标上，手里有一个“可操作区间”，每走一步都尽量跳到最远，步数自然最少。只不过这里的“跳跃”不是走一步跳a[i]格，而是“选一个已经激活的位置，向右激活k格”，并且你只能在已激活的位置里选起点。

3. 正确贪心与实现

3.1 贪心策略：每次选最靠右的可用左端点

于是我得到了一个很简洁的贪心：

1. 维护cnt，表示[0, cnt-1]已经全是>。
2. 每次跳过连续已经是>的位置（即while cnt < n且s[cnt] == '>'时，cnt++）。
3. 如果cnt == n，说明已经全>，结束。
4. 否则令p = cnt，位置p是第一个未被覆盖的<。
5. 计算可行左端点区间：[lower, upper]，其中lower = max(0, p-k+1)，upper = min(cnt-1, n-k)。
6. 如果upper < lower，无解，输出-1。
7. 否则取l = upper，做一次操作，ans++，更新cnt = max(cnt, l + k)，回到第2步。

每次取upper，也就是可行区间里最靠右的左端点。这样一次操作能覆盖到的最右位置l+k-1是最大的，前缀延长得最多。由于覆盖范围更大，后续可选的起点不会变少，所以步数不会比取其他左端点多。

这里需要解释为什么取更大的l不会“漏掉”左侧的<。因为在p左边，前缀[0, cnt-1]已经是全>，这些位置本来就不需要再覆盖。而区间[l, l+k-1]里左侧部分正好落在前缀内，所以哪怕l更靠右，也不会遗漏任何关键位置。本质上，更靠右的l把一个长度固定的区间整体往右移，损失的左侧部分本来就没有待处理内容，赚到的是右侧覆盖得更远。

3.2 为什么这是最小步数

必要性部分：当前p是第一个未覆盖的<，任何可行解都必须在这一步之后让p变成>，因此这一步操作必须落在可行区间[l, l+k-1]里，且左端点必须取可行区间中的某个值。如果可行区间为空，任何方案都无法覆盖p，只能无解。

最优性部分用交换论证。假设某一步最优解选了左端点l1，而贪心选了l2 = upper > l1，两个l都能覆盖当前p。操作l1后，新前缀变成l1+k；操作l2后，新前缀变成l2+k，明显更靠右。更靠右的前缀意味着后续能作为左端点的位置集合不会更小，同时已经覆盖的字符不会重新变回<，所以把最优解里的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)。在实际比赛中，这个代码非常快，即使是n=2e5、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 = 0，lower = max(0, 0-k+1) = 0，upper = min(-1, n-k) = -1，upper < lower，直接判无解。这是因为能作为操作左端点的位置必须本身是>，而位置0是<，没有任何办法覆盖它；任何操作区间要覆盖位置0，左端点只能是0，但左端点0不满足>的条件，所以无解。

这个结论也可以在脑内直接得到：第一个字符如果是<，永远不可能变成>。

4.4 区间右边界 n-k

当你计算upper时，一定要记得限制l <= n-k，否则操作区间会越界。这个限制很容易被漏掉。比如n=5，k=3，n-k=2，这意味着左端点最大只能是2，因为l=3时区间[3,5)会超出字符串末尾。

我见过有的题解不限制这个，而是把cnt推到n-k之间，其实不够严谨。如果l取太大，即使它在前缀里，操作也会越界，这会让程序在边界数据上出错。最稳妥的写法就是我上面代码里的upper = min(cnt-1, n-k)。

5. 常见错误与Debug实录

5.1 我第一版贪心错在哪

我最初写的贪心不是“取最靠右的可行左端点”，而是“每个未覆盖的<都必须作为某次操作的右端点”。具体来说，看到p是<，我就强制让区间右端点为p，左端点为p-k+1，然后检查这个左端点当前是不是>。这个做法看起来很有道理，因为覆盖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^10，BFS完全跑得动。

然后随机生成n和k，把暴力和贪心的答案对比。跑了几万组，发现唯一出问题的就是第一版“以p为右端点”的贪心，修正成“每次选最右可行左端点”之后就再也没挂过。如果你在别的题上没信心，强烈建议也写个对拍，工程量不大，但能省下大量debug时间。

5.3 常见问题速查表

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 如果把目标改成全<

如果题目对称地换成“把区间变全<，要求左端点是<”，那整个做法完全镜像：维护前缀全<，每次选最靠右的可行左端点，所有逻辑反转即可。理解了这个模型，做镜像版本基本是抄一遍的事。

最后再分享一个小技巧：这类“从左往右推进”的贪心，写完代码后一定要用“开头是<”、“末尾是<”、“k=n”、“k=1”这几组边界数据自测。特别是k=1时，每个<都必须自己作为左端点才能变，等价于检查所有位置原本是否都是>；如果没处理好，很容易在这一档翻车。我在这次复盘里就靠这些边界数据抓到了两个隐蔽的bug，希望你看完这篇文章后，也能少走这些弯路。