3月29号下午的蚂蚁暑期实习开发岗笔试第三题《位运算权值》卡了我挺久。说实话第一眼看过去我以为要上区间DP、字典树甚至线段树毕竟题干里横着重排任意子串这种操作怎么看都不像个善茬。但冷静下来仔细一推这道题真正的内核根本不是字符串操作而是三个环环相扣的小结论操作可达性、异或的popcount拆解、贪心放位。想通之后代码量少得可怜Java、C、Python都能十行以内解决。今天把整个复盘过程完整写出来正在准备暑期实习的同学可以参考一下尤其是位运算相关的公式变形思路比背模板有用得多。1. 题目模型还原别小看重排任意子串这句话1.1 我整理后的题目描述原题细节我记得不一定完全准确但核心考点和下面这个版本是一致的。这题本质上是一个自洽的模型只要把逻辑打通代码怎么写都能过输入一个长度 n1 ≤ n ≤ 10^5的 01 串 s以及一个长度同样为 n 的 01 串 K两个串都允许前导零。你可以对 s 执行任意多次操作每次选择一个连续子串将该子串内部的字符按任意顺序重新排列。设最终得到的 01 串为 t把 t 视为一个 n 位二进制数 X前导零不影响数值定义定义权值为 popcount(X xor K)也就是 X 和 K 按位异或后结果里 1 的个数。问在所有可达的 t 中这个权值的最大值是多少。输入样例5 00111 01010对应输出5这个样例大概什么感觉呢s 里有 3 个 1K 是 01010如果把 s 重排成 10101两者异或得到 11111popcount 就是 5达到满值。输出 5 是符合直觉的。1.2 第一反应为什么容易跑偏看到任意子串重排我一开始的思路是区间DP用 dp[l][r] 表示区间内部能重排出什么形态然后再想怎么和相邻区间合并。但很快就发现这个模型是撑不住的因为操作次数不受限制也没有代价你根本没法用 DP 去记录状态状态空间爆炸。还有人会往字典序、单调栈那边想觉得是不是要让 t 尽量大或者尽量小。这其实是被字符串题毒打了之后的肌肉记忆——看到重排就想到排序、贪心字典序。但本题目标函数是异或之后的 popcount跟字典序一点关系都没有。1.3 破题点任意连续子串重排等价于全局任意排列这是整道题最重要的一个结论。考虑一种最简单的操作选择长度为 2 的连续子串然后重排。这实际上就是交换相邻两个字符。比如 01 重排成 10或者反过来。那问题就变成了相邻交换能不能生成任意排列答案是肯定的。冒泡排序就是靠相邻交换让数组变成任意目标顺序的。也就是说只要我能模拟任意相邻交换我就能把整个字符串打乱成任何一种0 和 1 个数保持不变的排列。而选择长度为 2 的子串并重排正是题目允许的操作的子集。既然子集操作已经足够强大那完整的任意连续子串重排任意次就自然覆盖了所有可能的排列。反方向也成立任意子串重排本身也只是字符位置的一种置换它不会改变 1 的总数。所以最终可达到的 t 的集合就是所有恰好包含 cnt1 个 1 的长度为 n 的 01 串。这里的 cnt1 就是 s 里原本 1 的个数。这一步想通之后题目立刻变了味它不再是一个字符串操作题而是一个组合选择问题——我有 cnt1 个1要放到 n 个位置里每个位置放或不放怎么放能让某个目标函数最大。1.4 题目真正在问什么现在问题其实变成了所有拥有 cnt1 个 1 的 n 位二进制数 X 里寻找让 popcount(X xor K) 最大的那个。为什么说这是关键转折因为字符串长度 n 可以到 10^5任何 O(n^2) 的区间 DP 都活不下来。但经过等价性转换我们只需要考虑1 放在哪里这个纯位级问题。剩下的工作全部聚焦到 popcount 的公式变形上和字符串本身的长相无关了。在笔试现场我在这里停留了大概三分钟反复确认任意子串重排任意次是不是我真的理解的那个意思。确认无误后我立刻在草稿纸上写下了公式也就是下一节的内容。2. 权值函数变形的关键把 popcount(X xor K) 拆开2.1 从逐位异或到集合论视角位运算的题目尤其是异或和 popcount 结合起来的题最忌讳一个位一个位地去数。那样推不出任何全局规律。更好的视角是把1 的位置看成一个集合。设 A 是 X 中所有 1 的下标集合B 是 K 中所有 1 的下标集合。那么X xor K 中为 1 的位置恰好是A 和 B 的对称差也就是只属于其中一个集合的位置。X K 中为 1 的位置恰好是 A 和 B 的交集。这本是离散数学里集合的基本概念但做题时很少有人主动把位运算映射到集合上。一旦映射过来了问题就变得异常清晰。对称差的大小有一个经典恒等式|A △ B| |A| |B| - 2|A ∩ B|对应到位运算上就是popcount(X xor K) popcount(X) popcount(K) - 2 * popcount(X K)这个公式是所有后续推导的基石。2.2 公式推导的详细过程我们设几个记号cnt1 popcount(X)也就是 s 中 1 的个数。cntK1 popcount(K)。overlap popcount(X K)表示 X 和 K 共同为 1 的位置数。那么popcount(X xor K) (cnt1 - overlap) (cntK1 - overlap) cnt1 cntK1 - 2 * overlap为什么是对的因为异或结果中的 1 分两类X 是 1、K 是 0贡献了 cnt1 - overlap 个。X 是 0、K 是 1贡献了 cntK1 - overlap 个。两类互不重叠加起来就是最终答案。注意这个推导完全不依赖具体位值是纯代数变形所以不仅适用于长度为 n 的 01 串也适用于任意长度的整数异或。我在笔试时推导完这个公式整个人就放松了因为题目已经变成了一个找最小值的问题。2.3 为什么这个变形是决定性的看变形后的表达式cnt1 cntK1 - 2 * overlapcnt1 和 cntK1 都是固定值——s 里 1 的个数是死的K 也给定。唯一能影响答案的变量只有 overlap。所以我们要求 popcount(X xor K) 的最大值等价于求 overlap 的最小值。而 overlap 的含义是我选的 X 和 K 在多少个位置上同时为 1。想通这一点题目就从最大化一个位运算结果转化成了最小化两个集合的交集大小。这种转化在算法竞赛里太常见了目标函数本身不好优化就把常数项拆出去剩下的部分变成一个更简单的约束优化问题。2.4 用例子验证公式还是看样例 s 00111K 01010。cnt1 3cntK1 2如果我们构造 X 10101那么 X K 00000overlap 0答案 3 2 - 0 5。如果随便取一个 X 00111那 X K 00010 01010 00111 00010overlap 1答案 3 2 - 2 3。确实变小了。这个验证很重要能确保公式没有记反。在考场上如果你时间充裕可以先随便枚举几个小例子对一下公式再往下推避免公式变形后方向错了还浑然不知。3. 构造最优 X 的贪心原则K 的 0 位是免费位置3.1 贪心策略现在问题变成了要在 n 个位置里放 cnt1 个 1使得 X 和 K 同为 1 的位置数最少。直觉非常直接优先把 1 放到 K 为 0 的位置上。因为如果 X 的某一个 1 落在 K 为 0 的位置那么这一位对 overlap 没有任何贡献。只有 X 的 1 落在 K 为 1 的位置才会产生一次 overlap而每次 overlap 会让最终答案减少 2。所以 K 里的 0 位就是免费位置有多少个免费位置就可以白放多少个 1。K 中 0 的个数是 n - cntK1记为 cntK0。3.2 数量分析免费位置够不够用这里要分两种情况讨论。情况一cnt1 ≤ cntK0也就是说 s 里的 1 数量少于等于 K 里 0 的数量。那我完全可以把所有 1 都放到 K 为 0 的位置做到 overlap 0答案直接拉满ans cnt1 cntK1这是最理想的情况约束条件完全够用。情况二cnt1 cntK0免费位置不够了。我最多只能把 cntK0 个 1 放到 K 为 0 的位置剩下的 cnt1 - cntK0 个 1 没地方躲只能落到 K 为 1 的位置上。每放一个这样的 1overlap 就加 1。所以最小 overlap 是minOverlap cnt1 - cntK0代入公式ans cnt1 cntK1 - 2 * (cnt1 - cntK0)把 cntK0 n - cntK1 代进去化简ans cnt1 cntK1 - 2 * cnt1 2 * (n - cntK1) 2n - cnt1 - cntK1这里有一个不错的直觉当 1 的总数足够多、躲不开 K 的 1 时最终结果会变成近似取反的状态也就是尽量让 X 和 K 相反。取反后 1 的个数是 n - cntK1但 X 只有 cnt1 个 1两者不对等时结果就是上面这个公式。两种情况下可以统一写成minOverlap max(0, cnt1 - (n - cntK1)) ans cnt1 cntK1 - 2 * minOverlap这也是代码里最好实现的版本。3.3 位独立性为什么让我们可以贪心这套贪心能成立关键在于位与位之间是完全独立的。二进制数的位运算不像普通十进制加法那样有进位也不存在高位影响低位的依赖关系。每一位的异或结果只取决于当前位和其他位没有任何因果关系。所以优先把 1 放到 K 为 0 的位置这个局部决策不会破坏任何全局约束。这一点我特别想强调因为很多人做位运算题时习惯于把二进制数当作一个整体思考比如觉得数值大的数 popcount 也大或高位 1 更重要。但在纯 popcount 目标函数里位的位置权重完全不重要每一位对答案的贡献都是 1没有高低位之分。这也是为什么这题能把问题化简到数 1 个数就结束的原因。3.4 如果要输出构造方案虽然原题只问最大值不需要输出构造结果但理解怎么构造对验证思路很有帮助。构造 X 的过程可以分两步从左到右或从右到左扫描 K如果当前位置是 0且我手上还有剩余的 1 没用完就把 X 的这一位设为 1。如果扫描完所有 K 为 0 的位置手上还有多余的 1那就只能把剩下的 1 放到 K 为 1 的位置上每放一个就产生一次 overlap。比如 s 00111K 01010。cnt1 3cntK0 3免费位置刚好够。扫描 K第 0 位是 0放 1第 1 位是 1不放第 2 位是 0放 1第 3 位是 1不放第 4 位是 0放 1。得到 X 10101。可以看到构造过程本身也是 O(n) 的和统计答案完全兼容。如果你对构造出的数值有额外要求比如在满足 overlap 最小的前提下让 X 的整数值最大那只需要把第一步的扫描顺序改成从高位到低位优先把 1 放到高位上的 K0 位置即可。但原题没有这个要求所以怎么放都一样。3.5 化简公式的小技巧我在笔试现场为了方便检查把答案公式化简成了两个分支if cnt1 n - cntK1: ans cnt1 cntK1 else: ans 2 * n - cnt1 - cntK1这个写法其实比cnt1 cntK1 - 2 * max(0, cnt1 - (n - cntK1))更容易心算验证。比如样例里 cnt1 3, n - cntK1 3满足第一个分支ans 5。如果 cnt1 4, cntK1 2, n 5则 n - cntK1 3cnt1 3走第二个分支ans 10 - 4 - 2 4。代码里我更推荐用 max 版本因为逻辑统一不容易漏分支。这里的分支公式更多是给自己验证用的。4. Java / C / Python 三语言实现与关键细节4.1 核心算法流程先抽象出算法步骤这样无论用什么语言实现都心里有数读入 n、字符串 s、字符串 K。分别统计 s 中字符 1 的个数 cnt1K 中字符 1 的个数 cntK1。计算 K 中 0 的个数 cntK0 n - cntK1。计算最小交集 minOverlap max(0, cnt1 - cntK0)。输出 cnt1 cntK1 - 2 * minOverlap。如果想要附加构造方案就在统计完之后初始化一个长度为 n 的全 0 字符数组 t。让 remain cnt1。第一轮遍历 K遇到 0 就把 t 对应位置设 1同时 remain 减 1直到 remain 为 0。第二轮遍历 K遇到 1 就把 t 对应位置设 1直到 remain 为 0。输出 t 拼接成的字符串。4.2 Java 实现Java 在笔试中要注意输入输出效率尤其是 n 到 10^5 级别后用 Scanner 也能过但推荐直接上 BufferedReader。import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim()); String s br.readLine().trim(); String K br.readLine().trim(); int cnt1 0, cntK1 0; for (char c : s.toCharArray()) { if (c 1) cnt1; } for (char c : K.toCharArray()) { if (c 1) cntK1; } int cntK0 n - cntK1; int minOverlap Math.max(0, cnt1 - cntK0); int ans cnt1 cntK1 - 2 * minOverlap; System.out.println(ans); // 如需构造一个最优 t取消注释下面代码 /* char[] t new char[n]; Arrays.fill(t, 0); int remain cnt1; for (int i 0; i n remain 0; i) { if (K.charAt(i) 0) { t[i] 1; remain--; } } for (int i 0; i n remain 0; i) { if (K.charAt(i) 1) { t[i] 1; remain--; } } System.out.println(new String(t)); */ } }Java 的坑不多主要就是 BufferedReader 读空行时容易出问题所以记得 trim()。另一个细节是Math.max(0, cnt1 - cntK0)里的两个参数都要是 intn 是 10^5 级别不会溢出不用开 long。4.3 C 实现C 实现几乎是题解的标准形态用 string 就能搞定注意别把字符串遍历和字符比较写错就行。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; string s, K; cin n s K; int cnt1 0, cntK1 0; for (char c : s) if (c 1) cnt1; for (char c : K) if (c 1) cntK1; int cntK0 n - cntK1; int minOverlap max(0, cnt1 - cntK0); int ans cnt1 cntK1 - 2 * minOverlap; cout ans \n; // 构造一个最优串 t可选 string t(n, 0); int remain cnt1; for (int i 0; i n remain 0; i) { if (K[i] 0) { t[i] 1; remain--; } } for (int i 0; i n remain 0; i) { if (K[i] 1) { t[i] 1; remain--; } } cout t \n; return 0; }C 里最需要注意的是string t(n, 0)这个构造方式很多新手会写成string t 然后一个个 push_back那样也没问题但性能和简洁度都不如直接构造。4.4 Python 实现Python 的优势是str.count一句话就能统计字符个数非常省事。不过要注意input()只读一行如果有多余空格可以用sys.stdin.read().split()统一处理。import sys def main(): data sys.stdin.read().split() n int(data[0]) s data[1] K data[2] cnt1 s.count(1) cntK1 K.count(1) cntK0 n - cntK1 min_overlap max(0, cnt1 - cntK0) ans cnt1 cntK1 - 2 * min_overlap print(ans) # 构造一个最优串 t可选 t [0] * n remain cnt1 for i in range(n): if remain 0: break if K[i] 0: t[i] 1 remain - 1 for i in range(n): if remain 0: break if K[i] 1: t[i] 1 remain - 1 print(.join(t)) if __name__ __main__: main()Python 上机时最容易栽在输入输出上如果题目要求输出答案但不允许输出多余内容构造部分就要注释掉。这里我把构造部分放在答案输出后面方便本地验证。4.5 三语言实现对比维度JavaCPython时间复杂度O(n)O(n)O(n)空间复杂度O(n) 或 O(1)O(n) 或 O(1)O(n) 或 O(1)代码量中中短主要易错点BufferedReader 空行、char[] 转 Stringstring 构造、索引越界input() 多行读取、列表转字符串适合场景大厂笔试主语言追求极致性能快速验证思路实际笔试中我用 Java 写核心统计部分大概十几行。构造部分是我在本地自测时加的上线提交时把构造部分注释掉只输出答案避免画蛇添足。5. 测试用例、边界条件与笔试现场建议5.1 完整测试用例表我自测时用了下面这些用例每一个都值得手算一遍sK期望输出手算验证00111010105X10101 时异或为 111110001113X000 异或为 1111110003X111 异或为 1110101011010106X010101每一位都与 K 相反110010104X0101 时异或为 1111110n11 xor 1 0101n11 xor 0 1其中最后两个用例是 n1 的边界很多人会忽略。n1 时只有两种情况公式也能直接覆盖。5.2 边界一K 全 0 或全 1K 全 0 时cntK1 0cntK0 n。如果 cnt1 ≤ n那 minOverlap 0答案就是 cnt1。这个结果很符合直觉K 全是 0那 X xor K 等于 X 本身popcount 自然就是 X 里 1 的个数。K 全 1 时cntK1 ncntK0 0。这时所有 X 的 1 都会和 K 的 1 重叠minOverlap cnt1答案 cnt1 n - 2cnt1 n - cnt1。验证K 全 1X xor K 等于 X 按位取反取反后 1 的个数当然是 n - cnt1。这两个极端用例能快速测试代码里 max/min 逻辑有没有写反。5.3 边界二cnt1 0 或 cnt1 ncnt1 0 时X 只能全 0答案是 cntK1。这要求异或结果里 1 的个数等于 K 里 1 的个数合理。cnt1 n 时X 只能全 1答案是 n - cntK1。因为全 1 和 K 异或等价于 K 取反。我见过有人在这个 case 上翻车因为把全 1想成了全跟 K 相反忽略了 K 里也有 1 会互相抵消。5.4 笔试现场如何快速验证思路我很推荐一个做法先写一个小 n 的暴力枚举再和优化算法对拍。n ≤ 8 时可以枚举所有含 cnt1 个 1 的 01 串逐个计算 popcount(X xor K)取最大值。这个暴力代码三分钟就能写完但它能帮你验证公式和贪心方向是否正确。暴力枚举样例递归生成所有排列生成所有含 cnt1 个 1 的 01 串可以用 DFS 或 bitset 枚举。对每个候选串计算popcount(X xor K)。取最大值和优化算法的输出对比。如果对拍发现不一致先别急着改代码回到公式检查cnt1 cntK1 - 2 * minOverlap是否被错误地套用。我往往在这种检查里发现的是max(0, cnt1 - cntK0)的符号写反而不是贪心本身有问题。5.5 关于时间分配的真实感受蚂蚁这场笔试第三题的位置比较尴尬前面有简单题后面可能还有压轴题。我建议如果遇到这种操作题位运算的组合先花五分钟左右确认操作的可达性这是整道题的命门。如果操作等价于全局排列那基本就是组合计数或贪心题如果操作有限制再去考虑 DP 或图论建模。第二点不要把时间浪费在证明公式上。异或 popcount 的集合公式属于基础结论现场推一遍只要一分钟但前提是你要有意识地去用集合论视角而不是逐位模拟。逐位模拟在 n10^5 时也许也能过但会严重阻碍后续推导。第三点代码写完不要急着提交先把 K 全 0、全 1、n1 三个用例各测一遍。这类边界用例能拦住绝大多数隐藏 bug。我自己在这次笔试里最大的收获不是记住了这道题的解法而是意识到位运算题里固定项拆出去剩余项找最小/最大是一个非常通用的套路。不管是异或、与、或还是 popcount、按位取反多往集合和代数变形上靠很多看起来很唬人的题目最后都会变成简单的最值问题。如果后续你想再深挖一层可以想想如果操作改成恰好只能重排 k 个子串会怎样或者 K 的长度可以小于 n 怎么办这些变体都不是简单改几个参数的事但对理解操作可达性很有帮助。这次先聊到这儿希望这份复盘对你有用。