企业官网建设流程全解析

刚打完 ICPC 2024 成都区域赛，被 A 题 Arrow a Row 卡了接近半小时，赛后冷静下来发现这题其实不复杂，就是一道披着字符串外衣的固定长度区间翻转题。题面给了一行由 '<' 和 '>' 组成的箭头，每次可以选择连续 k 个箭头，把它们全部反向，问最少多少次能让所有箭头指向同一个方向。看到“区间翻转”四个字，第一反应往往会去写搜索或者暴力模拟，但 n 一上来就废了。这篇题解把完整思路写下来，从如何把箭头抽象成 0/1、为什么要用差分数组，到贪心正确性的证明、代码实现和现场踩过的坑，一次性讲透。

1. 题意重述与基本模型转换

1.1 题目到底要干什么

题面很短，核心操作只有一个：选择一个长度为 k 的连续区间，把区间内所有字符的箭头方向反过来。字符只有两种，<和>，所以翻转操作本质上就是一个“取反”操作。题目要求所有箭头方向一致，也就是最终字符串要么全是<，要么全是>。问的是最小操作次数，如果做不到就输出 -1。

数据范围我记得很清楚，n 可以到 3e5 级别，k 最小是 1，最大可以等于 n。这意味着 O(nk) 的暴力模拟肯定过不了，甚至 O(n^2) 都会被卡死。我们需要一个 O(n) 或者 O(n log n) 的算法。这道题里没有任何排序、二分、数据结构的需求，答案就是一遍线性扫描加贪心。

这里有个容易忽略的地方：最终方向可以任选，所以全变成<和全变成>这两种情况都要考虑。如果题目要求的是“所有箭头都指向右边”，那答案就只跟一种目标有关；但 Arrow a Row 原题里明确说的是“同向”，所以必须对两种目标分别求最小步数，再取更小的那个。

1.2 把箭头抽象成二进制数

在算法题里，字符只是障眼法。把<看成 0，>看成 1，问题就变成了经典的 01 串区间取反问题。每次操作选择一个长度为 k 的连续子数组，把所有位置异或 1。目标是让整个数组全部变成 0，或者全部变成 1。

异或 1 是一个非常特殊的操作：一个位置如果被翻转偶数次，它的值不变；如果被翻转为奇数次，它的值取反。所以我们不需要真的去修改数组的每一个位置，只需要知道每个位置到底被翻转了奇数次还是偶数次。这个“奇偶次数”可以用一个变量 cur 来维护，而区间覆盖关系用差分数组来记录。

这种模型其实大家都不陌生，比较有名的类似题目是灯泡开关问题：一排灯，每次按下一段连续 k 个开关，问最少按几次让灯全灭。把“按开关”换成“翻转箭头”，本质完全一样。所以第一步要做的不是急着写代码，而是把字符串转成数组，并且在心里明确目标值 target 到底是 0 还是 1。

1.3 两种目标分别处理

写一个函数 calc(target) 表示“把原串变成所有位置都等于 target 所需的最少操作次数”。target=0 表示全部变成<，target=1 表示全部变成>。最后答案就是 min(calc(0), calc(1))。

calc 函数内部要对原串做一次线性扫描。注意 target=1 的时候不需要把原数组先取反再求全 0，直接让判断条件变成“当前实际值是否等于 1”即可。这样避免复制一份数组，代码也更干净。

2. 贪心策略：为什么从左往右扫是唯一解

2.1 关键观察：每个位置只剩一次补救机会

这是整道题的核心。从左往右扫描到位置 i 时，我们需要考虑所有起点位置在[i-k+1, i]的区间可能会影响位置 i。但这里有个重要事实：起点小于 i 的区间早在扫描到它们左端点的时候就已经决定了做还是没做；起点大于 i 的区间左端点都在 i 右边，根本覆盖不到 i；真正还没决定、又能影响位置 i 的区间，左端点只能是 i 自己。

换句话说，当我站在位置 i 面前时，以后没有任何操作能再改变位置 i 了。如果位置 i 当前的实际值不等于目标值，我必须立刻选择以 i 为起点，翻转区间[i, i+k-1]。如果不做这一步，位置 i 将永远错下去，整个方案就不可能成功。所以这不是一个“可以选择”的贪心，而是“只能这样做”。

也许有人会问：能不能为了救 i，现在不翻，等到后面某个 j>i 位置再翻一个区间，让那个区间也覆盖 i？不可能。因为区间起点 j 大于 i，整个区间都在 i 的右边，无法覆盖到 i。所以这个观察是严格的。

2.2 贪心的具体步骤

从左往右扫描 i = 0..n-1。用一个变量 cur 表示当前位置之前累计的翻转次数奇偶性，diff 数组记录区间开始和结束的事件。

每一步：

1. 更新 cur ^= diff[i]。
2. 计算当前位置实际值 now = a[i] ^ cur。
3. 如果 now 等于 target，什么都不做。
4. 如果 now 不等于 target，那么必须以 i 为起点进行一次翻转。如果 i+k-1 >= n，说明这个区间装不下，直接返回无解；否则操作次数加一，cur ^= 1，同时标记 diff[i+k] ^= 1。

这里最容易写错的是 diff 的更新。一次翻转区间[i, i+k-1]，在差分数组里应该让左端点 i 位置发生一次翻转，让右端点之后的位置 i+k 也发生一次翻转。因为我们已经在当前轮直接对 cur 取了反，所以左端点的事件已经生效，不需要再改 diff[i]；只需要在 diff[i+k] 打上结束标记，让 cur 在 i+k 之后被抵消。

2.3 为什么贪心一定最优

用归纳法证明。假设我们已经处理完位置 0 到 i-1，并且这些位置都已经变成 target，而且它们不会再被后续操作改变。

当前扫到位置 i。如果 a[i] 异或上已经发生的翻转次数之后已经等于 target，那么最优方案显然不会选择以 i 为起点翻转，因为多翻一次反而会让位置 i 变错，还需要额外操作去纠正，增加了步数。

如果当前位置不等于 target，那么任何可行方案都必须让位置 i 被翻转为奇数次。由于所有起点小于 i 的区间都已确定，起点大于 i 的区间又覆盖不到 i，唯一能让位置 i 改变的操作就是以 i 为起点的区间。这个区间如果翻转两次等于不翻，所以至少需要翻转一次。贪心选择翻转一次，恰好达到这个下界。

因此贪心每一步的操作次数不仅合法，而且和任何最优解所需次数相同。如果某个位置需要翻转但区间越界，那说明连唯一的补救手段都不存在，整个问题无解。

3. 差分数组的细节与手把手模拟

3.1 diff 到底是什么

差分数组在这种“区间异或”问题里特别管用。普通数组的差分维护的是相邻两个位置的差值；这里维护的是相邻位置的翻转次数有没有发生变化。

举个例子，如果我们在位置 0 翻转了一次区间[0, k-1]，那么位置 0 的翻转次数从 0 变成 1，位置 1 到 k-1 的翻转次数也都是 1，但位置 k 的翻转次数又回到 0。所以翻转次数从位置 0 开始增加 1，从位置 k 开始减少 1。用异或的方式记录：diff[0] ^= 1，diff[k] ^= 1。

扫描过程中 cur 代表当前位置实际翻转次数的奇偶性。每到一个新位置，先把 diff[i] 异或进 cur，这一步相当于处理了那些“在这个位置开始”或“在这个位置结束”的翻转。如果我们自己决定从 i 开始一次翻转，那么当前位置的翻转次数立即增加一次，所以 cur ^= 1；同时为了让这个翻转在 i+k 位置失效，在 diff[i+k] 打一个结束标记。

不要用加法维护次数，因为我们只关心奇偶性，异或更快也更不容易溢出。每次操作都是异或，奇偶性天然满足。

3.2 一个完整的小例子

设 s =<<>>，n = 4，k = 2，目标是全部变成<，即 target = 0。

先把 s 映射成 a = [0, 0, 1, 1]。diff 全部初始为 0，cur = 0，ans = 0。

• i = 0：cur = cur ^ diff[0] = 0。now = a[0] ^ cur = 0。now == target，不操作。
• i = 1：cur = cur ^ diff[1] = 0。now = a[1] ^ cur = 0。不操作。
• i = 2：cur = cur ^ diff[2] = 0。now = a[2] ^ cur = 1，不等于 target。检查 i+k-1 = 2+2-1 = 3 < 4，可以翻转。ans = 1，cur ^= 1 变成 1，diff[4] ^= 1。
• i = 3：cur = cur ^ diff[3] = 1。注意 diff[3] 还是 0，所以 cur 保持 1。now = a[3] ^ cur = 1 ^ 1 = 0，等于 target。不操作。

最终 ans = 1。实际手动模拟一下：翻转 s 的[2,3]区间，也就是两个>>变成<<，整个串变成<<<<，一步完成。

如果目标全部变成>，也就是 target = 1：

• i = 0：cur = 0，now = 0，不等于 target。i+k-1 = 1 < 4，可以翻转。ans = 1，cur ^= 1，diff[2] ^= 1。
• i = 1：cur = cur ^ diff[1] = 0，cur 保持 1。now = a[1] ^ 1 = 1，等于 target，不操作。
• i = 2：cur = cur ^ diff[2] = 1，cur 变成 0。now = a[2] ^ 0 = 1，等于 target，不操作。
• i = 3：cur = cur ^ diff[3] = 0，now = a[3] ^ 0 = 1，等于 target，不操作。

ans = 1，翻转[0,1]，也就是两个<<变成>>，整个串变成>>>>。所以该样例两种目标都只需要 1 步，答案就是 1。

3.3 什么情况会无解

无解的场景很典型：某个位置必须翻转，但以它为起点时区间右端越界了。

比如 s =1001，k = 3，目标是全 0。位置 0 是 1，必须翻转，翻转[0,2]后变成0111，然后位置 1、2、3 都变成 1，还得继续翻，但位置 1 如果翻转[1,3]，右端刚好等于 n-1，可以翻，得到0000，所以这个例子其实有解。需要找真正越界的，比如 s =11100，k = 3，目标全 0。位置 0 翻[0,2]得到00000，有解。再比如 s =111000，k=4，目标全 0：位置 0 翻[0,3]得到000100，位置 3 需要翻但右端 6 越界，无解。

判断无解不要拖到最后再统一检查。只要在当前 i 需要翻转且 i+k-1 >= n，直接判定无解，因为位置 i 已经不可能被后面的操作改正。继续扫描下去没有意义。

4. 代码实现与复杂度分析

4.1 C++17 参考代码

#include <bits/stdc++.h> using namespace std; const int INF = 1e9; int solve_one(const string& s, int k, int target) { int n = (int)s.size(); if (n < k) { for (char c : s) { int v = (c == '>'); if (v != target) return INF; } return 0; } vector<int> a(n); for (int i = 0; i < n; i++) a[i] = (s[i] == '>'); vector<int> diff(n + 5, 0); int cur = 0, ans = 0; for (int i = 0; i < n; i++) { cur ^= diff[i]; int now = a[i] ^ cur; if (now != target) { if (i + k - 1 >= n) return INF; ans++; cur ^= 1; diff[i + k] ^= 1; } } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; string s; cin >> n >> k >> s; int ans0 = solve_one(s, k, 0); int ans1 = solve_one(s, k, 1); int ans = min(ans0, ans1); if (ans >= INF) cout << -1 << '\n'; else cout << ans << '\n'; return 0; }

代码不长，但有几个地方必须严格保持顺序。先更新 cur 再判断 now；先判断越界再更新 cur 和 diff；diff 数组长度开 n+5 是为了访问 diff[n] 时不越界，因为 i 最大可能到 n-k，i+k 最大等于 n。

4.2 Python 版本

如果平时用 Python 刷题，可以直接套这个版本：

INF = 10**9 def solve_one(s, k, target): n = len(s) if n < k: return INF if any((c == '>') != target for c in s) else 0 a = [c == '>' for c in s] diff = [0] * (n + 5) cur = 0 ans = 0 for i in range(n): cur ^= diff[i] now = a[i] ^ cur if now != target: if i + k - 1 >= n: return INF ans += 1 cur ^= 1 diff[i + k] ^= 1 return ans n, k = map(int, input().split()) s = input().strip() ans0 = solve_one(s, k, 0) ans1 = solve_one(s, k, 1) ans = min(ans0, ans1) print(-1 if ans >= INF else ans)

Python 里a[i]是布尔值，cur是整数，布尔值和整数做异或会得到整数 0 或 1，在判断now != target时没有问题。不过要注意now的类型是 int，target 也是 int，比较是安全的。

4.3 复杂度分析

solve_one 只做了一次从 0 到 n-1 的循环，每一步都是常数时间操作，所以时间复杂度 O(n)。空间上开了一个长度为 n 的 a 数组和一个长度为 n+5 的 diff 数组，总空间 O(n)。

调用 solve_one 两次，总时间复杂度仍然是 O(n)，只是常数乘以 2。对于 n=3e5 的数据，运行时间在 C++ 下通常小于 10ms，Python 下也毫无压力。答案的最大值不会超过 n，因为每个位置最多只会以它为起点翻转一次，所以用 int 就足够了，但为了返回值标记无解，INF 设置成 1e9 更安全。

5. 常见坑点与实测调试

5.1 只求一种目标会漏答案

这题最阴间的坑就是“所有箭头同向”意味着全<和全>都算成功。我只写了全<的贪心，样例过了，但自己构造了一个全>的测试数据，结果程序输出了一大串操作而不是 0。后来改成 min(calc(0), calc(1))，一下子就正常了。

如果原题要求必须变成某一个方向，比如全部变成<，那就不需要取 min，直接把 solve_one 的 target 固定成 0 即可。但题目说的是“同向”，所以一定要算两遍。

5.2 diff 更新写成 diff[i] ^= 1

很多初学者会在需要翻转时写：

diff[i] ^= 1; diff[i + k] ^= 1; cur ^= 1;

这样会把当前位置的翻转次数重复计算。因为下一轮循环 i+1 时，cur ^= diff[i+1]不会再次读取 diff[i]，但是当前轮里我们已经读了 diff[i]，再改 diff[i] 不会影响本轮 cur，影响的只是假设将来某个时刻会重新扫描到 i？实际上不会。所以这种写法会让 diff[i] 的标记永远不被消费，导致 cur 维护错误。

正确的做法是：当前操作直接修改 cur，只把结束标记放在 diff[i+k] 上。左端点的开始事件不需要写进 diff，因为它已经通过 cur ^= 1 生效了。

5.3 对边界测试数据要保持敏感

几个值得手算的边界：

• k = 1：每次只能翻转一个字符，答案就是和 target 不同的字符个数。我们的算法会自然得到这个结果，但也可以专门对拍验证。
• k = n：只能翻转整个串，如果初始串和目标一样答案 0，否则翻转一次后整个串取反。如果翻转一次后还不是目标，就无解。
• n < k：一个区间都选不了，只有当初始串已经满足目标时答案才是 0，否则无解。代码里的 n<k 特判可以不加，因为越界判断会兜底，但加上更直观，也防止有些实现先访问 diff[i+k] 导致越界。

建议比赛前写一个暴力小数据对拍程序。数据范围 n <= 8，k <= 4，用 BFS 搜出真实答案，和贪心结果对比。多跑几千组随机数据，很快就能发现是不是漏了某种边界。

5.4 从错误中调试的一个例子

我这里有一个实际踩坑的测试：s =10100，k = 3，目标全 0。我当时代码先写成了从右往左扫，样例能过，但这个数据输出错误。原因是固定长度区间翻转必须从左往右扫，从右往左时位置 i 可能会被后面（右侧）的区间覆盖，但那些区间的左端点大于 i，根本覆盖不到 i，于是会漏判。只有从左往右扫才能保证“当前位置之后不会有别的操作改变它”。所以方向很重要，不要想当然地反着扫。

后来我把循环改成从 0 到 n-1，并且每次在操作前检查i+k-1 >= n，这个数据就正确了。

6. 个人比赛体验与一点建议

这题在热身赛时我其实见过类似的“连续 k 个翻转”模型，当时没有写题解，赛后已经忘得差不多。成都现场遇到 Arrow a Row，第一反应是字符哈希、区间异或、线段树，绕了很大一圈才发现根本不需要这些。

我的建议是：以后看到“区间统一取反”或“统一翻转”的题，先问自己三个问题。第一，区间长度是固定的还是任意的？第二，操作顺序有没有限制？第三，目标状态有几种？Arrow a Row 正好是区间长度固定、顺序不限、目标两种，因此贪心加差分就是正解。如果区间长度任意，最少操作次数通常和连续段数量有关；如果目标固定成一种，代码还可以再简化。

最后分享一个小技巧：把 calc(target) 单独写成函数，调试时分别输出 ans0 和 ans1。我现场就是因为两个答案没分开看，一直以为自己无解，后来才发现只是 ans1 的返回值是 INF，ans0 其实有答案。分步打印比直接输出 min 更容易定位问题。希望这篇题解能帮你少走几个 ICPC 现场容易踩的坑。