★ FEATURED ARTICLE 刚打完 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 所需的最少操作次数”。target0 表示全部变成target1 表示全部变成。最后答案就是 min(calc(0), calc(1))。calc 函数内部要对原串做一次线性扫描。注意 target1 的时候不需要把原数组先取反再求全 0直接让判断条件变成“当前实际值是否等于 1”即可。这样避免复制一份数组代码也更干净。2. 贪心策略为什么从左往右扫是唯一解2.1 关键观察每个位置只剩一次补救机会这是整道题的核心。从左往右扫描到位置 i 时我们需要考虑所有起点位置在[i-k1, i]的区间可能会影响位置 i。但这里有个重要事实起点小于 i 的区间早在扫描到它们左端点的时候就已经决定了做还是没做起点大于 i 的区间左端点都在 i 右边根本覆盖不到 i真正还没决定、又能影响位置 i 的区间左端点只能是 i 自己。换句话说当我站在位置 i 面前时以后没有任何操作能再改变位置 i 了。如果位置 i 当前的实际值不等于目标值我必须立刻选择以 i 为起点翻转区间[i, ik-1]。如果不做这一步位置 i 将永远错下去整个方案就不可能成功。所以这不是一个“可以选择”的贪心而是“只能这样做”。也许有人会问能不能为了救 i现在不翻等到后面某个 ji 位置再翻一个区间让那个区间也覆盖 i不可能。因为区间起点 j 大于 i整个区间都在 i 的右边无法覆盖到 i。所以这个观察是严格的。2.2 贪心的具体步骤从左往右扫描 i 0..n-1。用一个变量 cur 表示当前位置之前累计的翻转次数奇偶性diff 数组记录区间开始和结束的事件。每一步更新 cur ^ diff[i]。计算当前位置实际值 now a[i] ^ cur。如果 now 等于 target什么都不做。如果 now 不等于 target那么必须以 i 为起点进行一次翻转。如果 ik-1 n说明这个区间装不下直接返回无解否则操作次数加一cur ^ 1同时标记 diff[ik] ^ 1。这里最容易写错的是 diff 的更新。一次翻转区间[i, ik-1]在差分数组里应该让左端点 i 位置发生一次翻转让右端点之后的位置 ik 也发生一次翻转。因为我们已经在当前轮直接对 cur 取了反所以左端点的事件已经生效不需要再改 diff[i]只需要在 diff[ik] 打上结束标记让 cur 在 ik 之后被抵消。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] ^ 1diff[k] ^ 1。扫描过程中 cur 代表当前位置实际翻转次数的奇偶性。每到一个新位置先把 diff[i] 异或进 cur这一步相当于处理了那些“在这个位置开始”或“在这个位置结束”的翻转。如果我们自己决定从 i 开始一次翻转那么当前位置的翻转次数立即增加一次所以 cur ^ 1同时为了让这个翻转在 ik 位置失效在 diff[ik] 打一个结束标记。不要用加法维护次数因为我们只关心奇偶性异或更快也更不容易溢出。每次操作都是异或奇偶性天然满足。3.2 一个完整的小例子设 s n 4k 2目标是全部变成即 target 0。先把 s 映射成 a [0, 0, 1, 1]。diff 全部初始为 0cur 0ans 0。i 0cur cur ^ diff[0] 0。now a[0] ^ cur 0。now target不操作。i 1cur cur ^ diff[1] 0。now a[1] ^ cur 0。不操作。i 2cur cur ^ diff[2] 0。now a[2] ^ cur 1不等于 target。检查 ik-1 22-1 3 4可以翻转。ans 1cur ^ 1 变成 1diff[4] ^ 1。i 3cur cur ^ diff[3] 1。注意 diff[3] 还是 0所以 cur 保持 1。now a[3] ^ cur 1 ^ 1 0等于 target。不操作。最终 ans 1。实际手动模拟一下翻转 s 的[2,3]区间也就是两个变成整个串变成一步完成。如果目标全部变成也就是 target 1i 0cur 0now 0不等于 target。ik-1 1 4可以翻转。ans 1cur ^ 1diff[2] ^ 1。i 1cur cur ^ diff[1] 0cur 保持 1。now a[1] ^ 1 1等于 target不操作。i 2cur cur ^ diff[2] 1cur 变成 0。now a[2] ^ 0 1等于 target不操作。i 3cur cur ^ diff[3] 0now a[3] ^ 0 1等于 target不操作。ans 1翻转[0,1]也就是两个变成整个串变成。所以该样例两种目标都只需要 1 步答案就是 1。3.3 什么情况会无解无解的场景很典型某个位置必须翻转但以它为起点时区间右端越界了。比如 s 1001k 3目标是全 0。位置 0 是 1必须翻转翻转[0,2]后变成0111然后位置 1、2、3 都变成 1还得继续翻但位置 1 如果翻转[1,3]右端刚好等于 n-1可以翻得到0000所以这个例子其实有解。需要找真正越界的比如 s 11100k 3目标全 0。位置 0 翻[0,2]得到00000有解。再比如 s 111000k4目标全 0位置 0 翻[0,3]得到000100位置 3 需要翻但右端 6 越界无解。判断无解不要拖到最后再统一检查。只要在当前 i 需要翻转且 ik-1 n直接判定无解因为位置 i 已经不可能被后面的操作改正。继续扫描下去没有意义。4. 代码实现与复杂度分析4.1 C17 参考代码#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; } vectorint a(n); for (int i 0; i n; i) a[i] (s[i] ); vectorint 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 和 diffdiff 数组长度开 n5 是为了访问 diff[n] 时不越界因为 i 最大可能到 n-kik 最大等于 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的类型是 inttarget 也是 int比较是安全的。4.3 复杂度分析solve_one 只做了一次从 0 到 n-1 的循环每一步都是常数时间操作所以时间复杂度 O(n)。空间上开了一个长度为 n 的 a 数组和一个长度为 n5 的 diff 数组总空间 O(n)。调用 solve_one 两次总时间复杂度仍然是 O(n)只是常数乘以 2。对于 n3e5 的数据运行时间在 C 下通常小于 10msPython 下也毫无压力。答案的最大值不会超过 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;这样会把当前位置的翻转次数重复计算。因为下一轮循环 i1 时cur ^ diff[i1]不会再次读取 diff[i]但是当前轮里我们已经读了 diff[i]再改 diff[i] 不会影响本轮 cur影响的只是假设将来某个时刻会重新扫描到 i实际上不会。所以这种写法会让 diff[i] 的标记永远不被消费导致 cur 维护错误。正确的做法是当前操作直接修改 cur只把结束标记放在 diff[ik] 上。左端点的开始事件不需要写进 diff因为它已经通过 cur ^ 1 生效了。5.3 对边界测试数据要保持敏感几个值得手算的边界k 1每次只能翻转一个字符答案就是和 target 不同的字符个数。我们的算法会自然得到这个结果但也可以专门对拍验证。k n只能翻转整个串如果初始串和目标一样答案 0否则翻转一次后整个串取反。如果翻转一次后还不是目标就无解。n k一个区间都选不了只有当初始串已经满足目标时答案才是 0否则无解。代码里的 nk 特判可以不加因为越界判断会兜底但加上更直观也防止有些实现先访问 diff[ik] 导致越界。建议比赛前写一个暴力小数据对拍程序。数据范围 n 8k 4用 BFS 搜出真实答案和贪心结果对比。多跑几千组随机数据很快就能发现是不是漏了某种边界。5.4 从错误中调试的一个例子我这里有一个实际踩坑的测试s 10100k 3目标全 0。我当时代码先写成了从右往左扫样例能过但这个数据输出错误。原因是固定长度区间翻转必须从左往右扫从右往左时位置 i 可能会被后面右侧的区间覆盖但那些区间的左端点大于 i根本覆盖不到 i于是会漏判。只有从左往右扫才能保证“当前位置之后不会有别的操作改变它”。所以方向很重要不要想当然地反着扫。后来我把循环改成从 0 到 n-1并且每次在操作前检查ik-1 n这个数据就正确了。6. 个人比赛体验与一点建议这题在热身赛时我其实见过类似的“连续 k 个翻转”模型当时没有写题解赛后已经忘得差不多。成都现场遇到 Arrow a Row第一反应是字符哈希、区间异或、线段树绕了很大一圈才发现根本不需要这些。我的建议是以后看到“区间统一取反”或“统一翻转”的题先问自己三个问题。第一区间长度是固定的还是任意的第二操作顺序有没有限制第三目标状态有几种Arrow a Row 正好是区间长度固定、顺序不限、目标两种因此贪心加差分就是正解。如果区间长度任意最少操作次数通常和连续段数量有关如果目标固定成一种代码还可以再简化。最后分享一个小技巧把 calc(target) 单独写成函数调试时分别输出 ans0 和 ans1。我现场就是因为两个答案没分开看一直以为自己无解后来才发现只是 ans1 的返回值是 INFans0 其实有答案。分步打印比直接输出 min 更容易定位问题。希望这篇题解能帮你少走几个 ICPC 现场容易踩的坑。
阅读完成 · 觉得有帮助？
