F. A Bit Odd — 从零开始的博弈题解 题目回顾问题给定一个二进制字符串sss只含0和1Alice 和 Bob 轮流操作Alice 先手。每轮操作玩家必须选择一个子序列subsequence该子序列的逆序对数为奇数然后将其从原字符串中删除。胜负判定无法操作的人输。双方都采取最优策略问谁赢。补充概念术语解释例子二进制串只由0和1组成的字符串10101子序列删除若干字符可以不删后剩下的序列保持原有相对顺序10101的一个子序列111取第 1,3,5 位逆序对一对下标(i,j)(i,j)(i,j)满足ijijij且si1, sj0s_i1,\ s_j0si​1,sj​0在10中这对(1,0)就是一个逆序对 思考过程踩坑记录阶段一错误的方向 ❌一开始我的思路是统计整个字符串的逆序对总数如果是奇数 → Alice 直接取走整串获胜如果是 0 → 先手无法操作Bob 获胜如果是偶数且000→ 分析活跃区域从第一个 1 到最后一个 0 的部分如果活跃区域不全是一堆 1 后跟一堆 0 → 认为 Alice 必胜但没有严格证明如果活跃区域是1...10...0→ 用Grundy 数判断胜负这个解法有什么问题问题说明❌ 过度复杂引入活跃区域、Grundy 表等概念把简单问题搞复杂❌ 漏洞“非纯1^p0^q→ Alice 胜” 只靠观察 n≤6 的规律缺少严谨证明❌ 不优雅没有抓住问题的本质绕了很大圈子阶段二发现正确思路 ✅正确的思路是不要管逆序对总数也不要管什么活跃区域而是思考Alice 能不能一次操作就让剩下的字符串变成有序的没有逆序对如果能Bob 就无法操作Alice 直接获胜。如果不能Bob 有应对策略。那 Alice 怎样一次操作就结束游戏呢她可以这样选子序列取走左侧所有的 1再加上右侧所有的 0。原始串 ...1...1...1... | ...0...0...0... ← 左侧所有 1 → ← 右侧所有 0 → ←—— 删除这个子序列 ——→ 剩下的 ...0...0...0... | ...1...1...1... ← 左侧所有 0 → ← 右侧所有 1 → 这个序列是有序的没有逆序对这个子序列形如111...000...它的逆序对数量 左侧 1 的个数×右侧 0 的个数。要让它合法我们需要逆序对数为奇数 → 左侧 1 的个数为奇数且右侧 0 的个数为奇数。✅ 最终结论一句话Alice 获胜⇔ 存在一个切口cut使得切口左侧有奇数个 1且切口右侧有奇数个 0。否则Bob 获胜。就这么简单接下来我们分别证明充分性和必要性。 充分性证明存在这样切口 → Alice 胜假设我们在某个位置切一刀左半部分 | 右半部分Alice 执行以下操作选择子序列取走左半部分所有的1右半部分所有的0这个子序列的逆序对数量 (左半 1 的数量) × (右半 0 的数量) 奇数 × 奇数 奇数✅ 合法操作删除后剩下左半部分所有的0 右半部分所有的1剩下的序列形如000...111...已排序没有逆序对Bob 无法操作 →Alice 获胜举例s 10101 尝试切口在 10|101 左半 10 → 1 的数量 1奇数✅ 右半 101 → 0 的数量 1奇数✅ Alice 删除左半的 1位置 1 右半的 0位置 3 删除子序列 101 个逆序对奇数 ✅ 剩下 011没有逆序对Bob 无法操作 → Alice 获胜 必要性证明没有这样切口 → Bob 胜这部分的证明稍微复杂一些但可以通俗地理解。核心区的概念先去掉字符串开头的所有0和结尾的所有1这些字符不参与任何逆序对对游戏没有影响剩下的部分称为核心区。例子 0011001 ↑ ↑ 去掉前导0 去掉后缀1 核心区 1100核心区的结构如果没有满足条件的切口可以证明核心区的每一段连续相同字符的长度都是偶数。核心区例子没有切口的情况 11 00 ← 每段长度都是偶数 11 00 11 00 ← 同上 1111 0000 ← 同上Bob 的配对策略 Bob 把核心区中相邻且相同的字符两两配对核心区 11 00 11 00 ... 配对 ^^ ^^ ^^ ^^Bob 的策略非常简单Alice 删掉某个配对中的一个字符Bob 就删掉这个配对中的另一个。为什么这样有效Alice 的行为对配对的影响Bob 的回应删掉配对中的 1 个该配对被拆散Bob 删掉另一个删掉完整的一对2 个该配对被完整删除无需回应不动某个配对配对完整保留无需回应关键观察Alice 删除的子序列中只有那些被拆散的配对才真正贡献了逆序对。因为完整删除的配对内部两个字符相同不产生逆序对完整保留的配对也不影响完整删除的配对与其他被删除字符形成的逆序对数量总是偶数对称性所以 Alice 的合法操作等价于她拆散的半对按原序组成的子序列有奇数个逆序对。Bob 删除这些半对中剩下的另一半得到的子序列与 Alice 删除的完全相同 → 也有奇数个逆序对 → Bob 的操作也合法Bob 操作后每个配对要么完整保留、要么完整删除核心区仍然可以继续两两配对。游戏长度有限Bob 总能这样回应直至 Alice 无法操作 →Bob 获胜。 算法实现判定方法从左到右枚举所有n1n1n1个切口位置维护两个变量onesLeft切口左侧1的个数的奇偶性0偶数1奇数zerosRight切口右侧0的个数的奇偶性初始状态切口在最左端第一个字符之前onesLeft 0 ← 左侧还没有字符 zerosRight 总0的个数 % 2 ← 右侧是整个字符串每次检查如果 onesLeft 1 且 zerosRight 1 → Alice 胜然后移动切口把当前字符从右侧移到左侧如果是1→onesLeft翻转奇数变偶数偶数变奇数如果是0→zerosRight翻转核心代码C17#includebits/stdc.husingnamespacestd;voidsolve(){intn;string s;cinns;// zerosRight: 当前切口右侧 0 的数量的奇偶性intzerosRight0;for(charc:s)if(c0)zerosRight^1;intonesLeft0;boolaliceWinsfalse;// 枚举 n1 个切口位置for(intcut0;cutn;cut){if(onesLeft1zerosRight1){aliceWinstrue;break;}if(cutn)break;// 把 s[cut] 从右侧移到左侧if(s[cut]1)onesLeft^1;elsezerosRight^1;}cout(aliceWins?Alice:Bob)\n;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--)solve();return0;}复杂度指标值时间复杂度O(n)O(n)O(n)空间复杂度O(1)O(1)O(1)n 总上限2×1052 \times 10^52×105 样例手算过程样例 110101cut左侧onesLeft右侧zerosRight(1,1)?0(空)01010102个0→偶✗11101010✗210110111个0→奇✅找到切口 →Alice 胜✓样例 20100cut左侧onesLeft右侧zerosRight(1,1)?0(空)0010013个0→奇✗10010002个0→偶✗2011000✗3010101✅→Alice 胜✓样例 3011001核心区分析去掉前导0位置1和后缀1位置6核心区 1100。核心区 11 00 ^^ ^^ 每段长度都是2偶数没有满足条件的切口 →Bob 胜✓ 快速检查表对于每个测试用例按以下顺序判断初始化zerosRight 总0个数 % 2onesLeft 0从cut 0到n依次检查如果onesLeft 1 zerosRight 1→Alice把s[cut]从右侧移到左侧更新奇偶遍历完都没找到 →Bob❓ 常见疑问 FAQQ1为什么要用奇偶性不用具体数量因为只需要知道左侧 1 的个数和右侧 0 的个数是奇数还是偶数。奇偶性决定了乘积的奇偶而乘积的奇偶决定了这个子序列能否被选中。Q2Alice 为什么一定要取左侧所有 1 右侧所有 0这是最直接的获胜方式——一次操作就让剩下的字符串有序。如果存在这样的切口Alice 就用这个策略必胜。如果不存在Bob 有配对策略应对。Q3Bob 的配对策略会不会被破坏不会。Bob 每次回应后核心区的配对状态会恢复原状——所有配对要么完整保留、要么完整删除。核心区仍然可以继续两两配对。Q4为什么之前用 Grundy 数是绕弯路Grundy 数适用于分析所有可能的操作但这个游戏中 Alice 只需要一种获胜操作取左侧所有 1 右侧所有 0。不需要分析全部可能——只需要判断是否存在这样一个切口即可。 总结项目内容核心结论Alice 胜 ⇔ 存在切口使左侧有奇数个 1 且右侧有奇数个 0时间复杂度O(n)O(n)O(n)一次扫描空间复杂度O(1)O(1)O(1)只需两个变量代码量约 30 行难度评级Codeforces 上的 1600~1700 分题目解题的关键是跳出统计逆序对的思维定势思考能否一次操作就终结游戏——这比分析全部游戏状态要简单得多。