2026年3月15日顺丰春招的笔试里出了一道《黑白纸片》题目本身不算难但很有代表性。它表面上是棋盘翻面问题实际上考查的却是位运算、状态压缩和贪心这三板斧很多同学一看满屏黑白格子就条件反射地往DFS或者暴力模拟上想结果白白浪费了时间。这篇文章我按笔试现场的常见版本把题意补全把思考过程拆开讲清楚并给出Java、C、Python三套可以直接提交的代码最后还会附上本地自测和在线测试的完整方式。不管你是正在刷春招笔试题的应届生还是想把位运算用得更顺手的人这篇内容都能帮上忙。1. 题目还原与考察点分析春招笔试里的第二题通常承担的是“稳定拿分”的功能不会出得像竞赛那样刁钻但它特别爱考察“你能不能把一个看似二维的问题压缩成简单模型”。《黑白纸片》就是典型题目包装成一个棋盘翻转核心却是一个二进制枚举问题。1.1 完整题面与输入输出先说题面。我按常见笔试版本复述如下小C有一个 n 行 m 列的棋盘每个格子上都贴着一张纸片纸片一面是白色一面是黑色。初始时每张纸片的状态已知0 表示白色朝上1 表示黑色朝上。小C每次可以选择任意一行或者任意一列把这一整行或一整列的所有纸片翻面黑色变白色白色变黑色。操作次数不限也可以不操作问最终棋盘上最多能有多少张黑色纸片。输入格式第一行两个整数 n, m 接下来 n 行每行一个长度为 m 的 01 字符串输出格式一行一个整数表示最多黑色纸片数量数据范围这块我按笔试时比较常见的规模补充1 ≤ n ≤ 10001 ≤ m ≤ 15。如果你实际拿到的题面范围略有不同解法框架完全不变只需要把枚举的上限相应调整一下。有一点要提前确认这类题面的输入通常没有空格分隔字符是一整串01读的时候千万不要按char数组加到二维矩阵里再慢慢判断后面你会发现有更快的处理方式。1.2 这道题到底在考什么拆开看这道题的核心考点有四个观察力能否看出“操作次数无限”这句话背后的限制并及时做状态压缩。位运算能否用一行二进制整数表示棋盘的一行用一个异或完成整行翻转。状态压缩枚举能否枚举列翻转的所有情况而不是枚举整个棋盘。贪心能否在列翻转条件固定后对每一行独立取最大值并证明这种取法不会互相影响。这四点放在一起就已经把题目从“棋盘模拟”拉到了“二进制枚举”的层次。下面我从常规思路开始讲先说清楚为什么不能直接模拟。2. 常规思路为什么不可行组合爆炸很多人的第一反应是既然每次可以翻一行或者一列那我用DFS搜索每一步翻到最后找一个最大值。这个思路理论上没错但实际上一算复杂度就会被劝退。2.1 行列独立但组合多到爆炸如果老老实实考虑“每一行翻不翻、每一列翻不翻”那么行方向有 2^n 种选择列方向有 2^m 种选择总共是 2^(nm) 种组合。n 取 1000m 取 15 的时候这个数字已经不是程序能跑完的量级了。而且DFS 盲目搜索还要加上操作步数这个维度真正模拟出来的搜索空间更大。所以第一步要做的是压缩状态。2.2 翻转次数只有奇偶性重要这里有个很关键的观察每张纸片被翻转奇数次最终状态才发生变化被翻转偶数次等于没翻。而行和列的操作本质上都是全体取反所以操作顺序不影响最终结果。也就是说任意多次操作之后最终状态只取决于“哪些行被翻转了奇数次”和“哪些列被翻转了奇数次”。其他行、其他列翻多少次都没用。于是问题收缩为选一个行翻转集合和一个列翻转集合求黑色纸片的最大数量。2.3 为什么选列来枚举而不是选行状态虽然从 2^(nm) 缩小到了 2^n × 2^m但 n 和 m 仍然很大。不过题目给了 m ≤ 15 这样一个明显暗示列的规模很小列的翻转方案最多只有 2^15 32768 种。反观 n 可能有 1000行方向根本不能枚举。所以天然的方案是枚举列翻转的全部状态然后对每一行做贪心决策。这是本题最核心的算法骨架。3. 巧解状态压缩 逐行贪心一旦确定枚举列翻转剩下的问题就是在某个列翻转方案下每一行应该怎么处理这里用到的技巧是把整行看成一个二进制整数。3.1 固定列翻转后每行收益只取决于本行假设我选好了一个列翻转方案用 mask 表示mask 二进制第 k 位为 1表示第 k 列要翻转。那么对于第 i 行它收到的列翻转效果是固定的哪些列被翻面哪些列不变完全一样。此时这一行有两种选择不翻转这一行黑色数量就是当前状态下的 black翻转这一行整行颜色取反黑色数量变成 m - black。因为行与行之间没有任何制约关系所以每一行都可以独立选择对于自己更有利的那个方案取 max(black, m - black)。最后把所有行的贡献加起来就是当前列翻转方案对应的最优答案。3.2 为什么贪心是对的有人可能会担心一行翻多了会不会影响别的行不会。行翻转只改变本行列翻转已经被 mask 固定了行与行之间没有任何交互。于是每一行的局部最优解互不影响全局最优就等于每一行局部最优之和。这就像你给每个人发固定金额的优惠券每个人都可以独立决定自己用不用谁的选择都不会影响别人那么总收益自然是每个人单独最优收益的总和。这里也是一样的道理。3.3 位运算落地三步讲完了贪心再把它落到具体代码上其实就是三步第一步把一行01字符串压缩成一个整数。从左到右读字符串不断执行row (row 1) | (s[j] - 0)。这样一行纸片就变成了一个整数黑纸片对应二进制 1白纸片对应二进制 0。第二步用异或实现整行翻转。如果 mask 的第 k 位为 1表示第 k 列需要翻转那么row ^ mask的结果就是这一行在列翻转之后的新状态。因为异或运算中1 和 0 异或等于 11 和 1 异或等于 0天然就是翻转。举个例子某一行状态是二进制101列翻转 mask 是010只翻中间那一列异或结果是111。二进制里的 0 变成了 11 保持不变操作完全正确。第三步用 popcount 数出黑纸片数量。一个整数二进制中有多少个 1就是这一行当前有多少张黑色纸片。Java 可以用Integer.bitCountC 可以用__builtin_popcountPython 3.10 可以直接用int.bit_count()。这三步做完时间复杂度就是 O(2^m × n)m 取 15、n 取 1000 时运算量大约是 32768 × 1000 3.3 × 10^7三个语言都能轻松跑完。4. Java/C/Python 三版代码与细节思路确认后代码写起来就很快了。我直接给出三份完整可提交的代码同时把每份代码里容易踩的坑标出来。4.1 Java 版本推荐import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st new StringTokenizer(br.readLine()); int n Integer.parseInt(st.nextToken()); int m Integer.parseInt(st.nextToken()); int[] rows new int[n]; for (int i 0; i n; i) { String line br.readLine(); int row 0; for (int j 0; j m; j) { row (row 1) | (line.charAt(j) - 0); } rows[i] row; } int ans 0; int totalMasks 1 m; for (int mask 0; mask totalMasks; mask) { int blackCount 0; for (int i 0; i n; i) { int flipped rows[i] ^ mask; int black Integer.bitCount(flipped); blackCount Math.max(black, m - black); } ans Math.max(ans, blackCount); } System.out.println(ans); } }这里我用了BufferedReader而不是Scanner因为笔试数据量可能很大Scanner的 parse 开销在极限数据下会拖慢程序。另外要注意line.charAt(j) - 0这一步比Integer.parseInt(line.substring(j, j 1))快得多。4.2 C 版本跑得最稳#include iostream #include vector #include string #include algorithm using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint rows(n, 0); for (int i 0; i n; i) { string s; cin s; for (int j 0; j m; j) { rows[i] (rows[i] 1) | (s[j] - 0); } } int ans 0; int totalMasks 1 m; for (int mask 0; mask totalMasks; mask) { int cur 0; for (int i 0; i n; i) { int black __builtin_popcount(rows[i] ^ mask); cur max(black, m - black); } ans max(ans, cur); } cout ans \n; return 0; }C 版本里__builtin_popcount是 GCC 编译环境下的内置函数很多 OJ 都支持。如果你遇到不支持bits/stdc.h的环境用上面这几个标准头文件就够了。ios::sync_with_stdio(false);和cin.tie(nullptr);这两行是处理大量输入的关键忘了写很容易被卡 IO。4.3 Python 版本简洁但注意性能import sys def main(): data sys.stdin.read().strip().split() if not data: return n, m map(int, data[:2]) rows [] idx 2 for _ in range(n): s data[idx] idx 1 row 0 for ch in s: row (row 1) | (ord(ch) - 48) rows.append(row) ans 0 for mask in range(1 m): total 0 for row in rows: black (row ^ mask).bit_count() total max(black, m - black) ans max(ans, total) print(ans) main()Python 版本有两个细节要注意。第一是int.bit_count()需要 Python 3.10 及以上版本如果评测环境版本低可以改成bin(row ^ mask).count(1)但速度会慢一些。第二是读取方式我直接用sys.stdin.read().split()一次性读入比循环调用input().strip()更快在 n 到达 1000 时差距还能接受但养成用整段读入的习惯总没错。4.4 三版代码对比语言时间复杂度空间复杂度注意点JavaO(2^m × n)O(n)必须用 BufferedReader位计数用 Integer.bitCountCO(2^m × n)O(n)开启 IO 同步关闭用 __builtin_popcountPythonO(2^m × n)O(n)用 bit_count()用 sys.stdin.read() 整段读取从稳定性来说C 在极限数据下最不容易超时Java 只要 IO 处理得当同样没问题Python 在 m15、n1000 这个数据范围下也能跑完但如果你发现边界数据已经到 m20 附近Python 就会比较吃力建议优先做优化而不是硬跑。5. 在线测试与本地自测方式笔试里最怕的不是不会写是写完了不知道自己到底对不对。我习惯在提交前用几个样例在本地跑一遍确认逻辑和边界都正确后再上测评系统。5.1 用手写样例验证答案我准备了一个简单样例很适合快速验证输入2 3 101 010输出6简单验证一下第一行101有 2 个黑色若翻转整行最多可以变成 2 个黑色即 max(2, 1) 2第二行010只有 1 个黑色不翻行是 1翻行是 2取 2所以列翻转 mask 全 0 时总贡献是 2 2 4。如果选择列翻转 mask 010第一行变成111取 3第二行变成000不翻行是 0翻行是 3取 3总贡献是 6。这就是最优答案。再给一个能覆盖更多行情况的样例输入4 3 101 010 111 000输出10这个例子可以用来测试边界全黑行111取 3全白行000翻转后取 3普通行取 2 或 2最后能凑到 10。你可以在本地把这组输入跑一遍看看三个版本是不是都输出 10。5.2 本地运行三版代码本地验证时我习惯把所有输入放到input.txt文件里然后分别用下面的命令执行# C 编译运行 g -O2 -stdc17 black_white.cpp -o solve ./solve input.txt # Java 编译运行 javac Main.java java Main input.txt # Python 运行 python3 main.py input.txt这里有个小习惯把输入数据存成文件再重定向可以避免反复手动敲样例。尤其是笔试时时间很紧写一个input.txt比一次一次粘贴方便得多。5.3 在线测试与提交平台的注意点在线测试一般是你笔试时用的那个评测系统或者牛客网、LeetCode 之类的在线题库。提交时要注意几个点Java 的主类名必须是Main否则会编译失败。C 不要输出多余提示信息比如请输入n:这种东西OJ 只认标准结果。Python 代码里不要写if __name__ __main__:之外的顶层冗余代码保持main()入口清晰。如果你是在本地跑通过再提交到在线平台基本上除了 IO 方式不同其余逻辑不会变。6. 排坑与个人心得每次写完位运算相关的题我都会整理一份自己的“踩坑清单”这道题也不例外。6.1 几个必踩的坑第一个坑忘了重置计数变量。在枚举 mask 的循环里每一轮都要把blackCount重置为 0否则会把上一轮的答案叠加进去导致输出离谱地大。这个错误很隐蔽因为在小样例上可能看不出问题数据一大就全错。第二个坑行列翻转对象搞反。mask 枚举的是列翻转所以行数组是rows[i] ^ mask如果你不小心写成rows[i] mask或者其他运算整道题就废了。位运算里异或就是“对应位不同则结果为 1”这正是翻面的语义。第三个坑位运算优先级。在 Java 和 C 中^的优先级低于和算术运算符高于但低于、这种。所以如果你写rows[i] ^ mask 0实际运行结果会跟预期完全不同。稳妥的做法是给异或运算加括号例如(rows[i] ^ mask)。第四个坑输入字符串里可能有空格或换行残留。用BufferedReader或cin s处理 01 字符串时问题不大但如果你用Scanner或input()读取就要小心换行符带来的空串问题。我的建议是统一用整段读取再切分的方式避免这类问题。6.2 时间分配与心态这道题放在春招第二题的位置上理想状态下应该在 20 到 30 分钟内完成。我个人的建议是看到棋盘题不要急着写搜索先观察数据范围。一旦发现 m 很小而 n 很大就要立刻联想到状态压缩枚举。反过来如果 m 和 n 都很大那就不能用这个思路需要找别的性质。我第一次做这道题时也走了弯路先写了一个 DFS 版本结果自己用 20 行的样例一跑就卡死后来才想到枚举列翻转。所以强烈建议大家在平时刷题时就养成一个习惯题目读完后先把数据范围写在草稿纸上再决定算法方向。6.3 扩展如果 m 更大怎么办如果题目把 m 改成 20 以上比如 m25那么 2^25 约等于 3300 万再乘 n1000 就是 300 亿次三版代码都会超时。这时候就需要更高级的思路比如按行的等价类分组或者用类似 meet-in-the-middle 的技术。但如果是春招题m 通常不会给到这么大所以这道题的“标准答案”就是枚举列状态。我在实际笔试中还有一个体会代码写完不要急着提交先用极小的边界数据测试一下比如1 1、全 0 棋盘、全 1 棋盘。全 0 棋盘应该输出 n×m因为每一行翻转一次就能全变黑全 1 棋盘同样应该输出 n×m因为不翻就是全黑。这种边界测试花不了 30 秒但能救回很多不该丢的分。如果你能把这道题的思路讲清楚代码写完还能顺手验证几个边界那么顺丰春招笔试的这个环节基本就稳了。