位运算枚举题解与源码剖析:LeetCode 5992「基于陈述统计最多好人数」的二进制状态校验(codeforces-go)
位运算枚举题解与源码剖析:LeetCode 5992「基于陈述统计最多好人数」的二进制状态校验(codeforces-go)
本篇技术指南围绕 LeetCode 周赛第 277 场第 4 题(「基于陈述统计最多好人数」/ Maximum Good People Based on Statements)展开,以 d.md 官方题解为骨架,结合 codeforces-go 仓库中该题的 Go 实现、测试用例 以及 copypasta 位运算与搜索模板,完整讲解「二进制枚举好人子集 + 陈述一致性校验」的解法原理、四种语言实现、复杂度分析与测试验证方法。读完本文,你将掌握 n≤15 规模下用位掩码暴力枚举状态的通用思路,以及如何在本仓库的 LeetCode 测试框架下验证这类函数题解。
题目背景与问题定义
这是一道典型的「小数据规模 + 逻辑一致性判断」问题,出自 LeetCode 第 277 场周赛(题目编号 LC5992)。题面给出了 n 个人(n ≤ 15)以及一张 n × n 的陈述矩阵 statements:
statements[i][j] = 1:第i个人认为第j个人是好人;statements[i][j] = 0:第i个人认为第j个人是坏人;statements[i][j] = 2:第i个人没有对第j个人表态。
假设好人一定说真话,坏人可能说真话也可能说假话,要求找出在所有与陈述不矛盾的「好人/坏人」分配方案中,好人个数的最大值。
仓库中本题的测试文件 d_test.go 给出了两个可直接验证的示例:
输入:[[2,1,2],[1,2,2],[2,0,2]] 输出:2
输入:[[2,0],[0,2]] 输出:1
第一个例子中,若把第 0、1 号人视为好人、第 2 号人视为坏人,好人说真话(statements[0][1]=1 与「第 1 号是好人」一致,statements[1][0]=1 与「第 0 号是好人」一致),坏人的任何说法都不受约束,因此合法且好人最多为 2。第二个例子中两人互相指控对方是坏人,二者只能取其一,故答案为 1。
核心思路:从集合论到位运算的二进制枚举
本题的关键突破口在于数据规模:至多有 n = 15 个人,因此可以枚举这 n 个人「谁是好人、谁是坏人」的全部情况,共 2^n 种,完全在可枚举范围内。
题解文档 d.md 指出,枚举好人子集时可以直接借用位运算中的「枚举子集」技巧(原文引用了「从集合论到位运算,常见位运算技巧分类总结」这一资料)。具体编码约定如下:
- 用一个二进制数
i表示 n 个人的好坏状态; - 二进制位为
1表示对应的人是好人,为0表示是坏人; - 于是
i ∈ [0, 2^n - 1]就一一对应了全部2^n种分配方案。
随后逐一判断:枚举出的每个「好人」的每条陈述是否与当前状态矛盾。若所有好人的陈述都与状态一致,则该状态为一种合法情况;所有合法情况中好人个数的最大值即为答案。这就是题目解法完整的「枚举 + 校验」框架。
从仓库的位运算模板 bits.go 可以看到,这类「集合关系」在位运算下都有非常自然的表达:
isSubset := func(x, y int) bool { return x|y == y } // x 和 y 的并集是 y
isSubset = func(x, y int) bool { return x&y == x } // x 和 y 的交集是 x
这与本题「用位表示集合成员关系」的思路一脉相承:i >> j & 1 本质上就是判断「元素 j 是否属于集合 i」的集合论操作,只是被压缩到了一个 int 的位运算上。位运算枚举在此类小规模组合问题中的优势是:状态转移、成员判定、子集遍历都只需要常数级机器指令,配合循环展开即可获得极佳的常数性能。
枚举与校验的算法过程
把上述思路展开为可执行步骤,可得到如下流程:
- 令
n = len(statements),枚举掩码i从1到2^n - 1(题解明确从i = 1开始,因为全 0 的「全员坏人」方案中没有任何好人,不可能产生更优答案,无需检查)。 - 对每个掩码
i,统计其中好人个数cnt。 - 遍历每个人
j,若i >> j & 1 == 1说明j是当前状态下的好人:- 遍历
j的所有陈述k,对statements[j][k](记为st)进行校验; - 若
st < 2(即j确实表态了)且st != i >> k & 1(即j的说法与「第 k 个人当前是好是坏」的实际状态不一致),则说明好人在说谎,整个状态i非法,直接跳到下一个掩码; - 若所有陈述都通过,
cnt++。
- 遍历
- 用
ans = max(ans, cnt)更新全局最优。 - 循环结束后
ans即为答案。
这里的矛盾判定条件 st < 2 && st != i >> k & 1 是整个算法的核心:st < 2 把「未表态(值为 2)」的情况排除在一致性约束之外(坏人未表态不会暴露矛盾,好人未表态也不构成指控),st != i >> k & 1 则直接比较「陈述值」与「当前掩码中第 k 位的真实状态」。由于坏人可以随便说,只有好人的话才需要被校验——这正对应了代码中 if i>>j&1 == 1 的外层门控。
四种语言的完整实现
原题解文档 d.md 给出了 Python3、Java、C++、Go 四种语言的完整实现,以下逐一展开,并附上仓库中对应的 Go 源码 d.go。
Python3
class Solution:
def maximumGood(self, statements: List[List[int]]) -> int:
def check(i: int) -> int:
cnt = 0 # i 中好人个数
for j, row in enumerate(statements): # 枚举 i 中的好人 j
if i >> j & 1:
if any(st < 2 and st != i >> k & 1 for k, st in enumerate(row)):
return 0 # 好人 j 的某个陈述 st 与实际情况矛盾
cnt += 1
return cnt
return max(check(i) for i in range(1, 1 << len(statements)))
Python 版利用 any(...) 生成器表达式,把「好人的某条陈述与状态矛盾」压缩成单行判定,简洁直观;1 << len(statements) 即 2^n。
Java
class Solution {
public int maximumGood(int[][] statements) {
int n = statements.length;
int ans = 0;
next:
for (int i = 1; i < 1 << n; i++) {
int cnt = 0; // i 中好人个数
for (int j = 0; j < n; j++) {
if ((i >> j & 1) > 0) { // 枚举 i 中的好人 j
for (int k = 0; k < n; k++) { // 枚举 j 的所有陈述
if (statements[j][k] < 2 && statements[j][k] != (i >> k & 1)) { // 该陈述与实际情况矛盾
continue next;
}
}
cnt++;
}
}
ans = Math.max(ans, cnt);
}
return ans;
}
}
Java 版使用带标签的 next: 循环与 continue next;,一旦发现矛盾立即放弃当前掩码,避免无谓的后续校验。
C++
class Solution {
public:
int maximumGood(vector<vector<int>>& statements) {
int ans = 0, n = statements.size();
for (int i = 1; i < 1 << n; i++) {
int cnt = 0; // i 中好人个数
for (int j = 0; j < n; j++) {
if (i >> j & 1) { // 枚举 i 中的好人 j
for (int k = 0; k < n; k++) { // 枚举 j 的所有陈述
if (statements[j][k] < 2 && statements[j][k] != (i >> k & 1)) { // 该陈述与实际情况矛盾
goto next;
}
}
++cnt;
}
}
ans = max(ans, cnt);
next:;
}
return ans;
}
};
C++ 版用 goto next; 实现同等的「提前退出当前掩码」语义,next: 标签位于每次外层迭代的末尾,是这类「带标签跳过」写法的经典范式。
Go(仓库源码)
leetcode/weekly/277/d/d.go 中保存的正是与题解一致的 Go 实现,命名返回值 ans 配合 return 直接返回结果,函数体不依赖任何第三方库:
func maximumGood(statements [][]int) (ans int) {
next:
for i := 1; i < 1<<len(statements); i++ {
cnt := 0 // i 中好人个数
for j, row := range statements {
if i>>j&1 == 1 { // 枚举 i 中的好人 j
for k, st := range row { // 枚举 j 的所有陈述 st
if st < 2 && st != i>>k&1 { // 该陈述与实际情况矛盾
continue next
}
}
cnt++
}
}
ans = max(ans, cnt)
}
return
}
需要留意的是,这里的 max 是 Go 1.21+ 内置的泛型函数,仓库的 go.mod 使用了较新的 Go 版本才能直接编译。四份代码的循环结构与判定逻辑完全等价,均严格遵守「只校验好人的陈述、st < 2 才纳入约束、矛盾即整体作废」这三条规则。
复杂度分析
题解文档 d.md 给出的复杂度结论为:
- 时间复杂度:
O(n² · 2^n),其中 n 是statements的长度。理由是最外层枚举2^n个掩码,内层对每个掩码最多遍历 n 个「好人候选人」、每个候选人又遍历 n 条陈述,故相乘得O(n² · 2^n)。当 n = 15 时约为225 × 32768 ≈ 7.4 × 10^6次基本操作,在主流评测环境下完全可行。 - 空间复杂度:
O(1)。整个算法只使用常数个整数变量(掩码i、计数器cnt、答案ans),不申请任何与输入规模相关的额外存储,故为常数空间。
这里再补充一点细节:O(n² · 2^n) 是上界估计,实际运行中「好人子集」只占全部掩码的一部分,且一旦发现矛盾会立即跳过剩余校验,所以真实执行量通常低于上界;但为了严谨,分析中仍取最坏情况。
仓库测试框架下的验证方法
leetcode/weekly/277/d/d_test.go 是仓库 LeetCode 题解的通用测试模板(由 copypasta/template/leetcode/generator_test.go 生成),它通过 testutil.RunLeetCodeFuncWithExamples 把「输入 + 期望输出」的字符串样例批量喂给 maximumGood:
func Test_d(t *testing.T) {
examples := [][]string{
{
`[[2,1,2],[1,2,2],[2,0,2]]`,
`2`,
},
{
`[[2,0],[0,2]]`,
`1`,
},
}
targetCaseNum := 0 // -1
if err := testutil.RunLeetCodeFuncWithExamples(t, maximumGood, examples, targetCaseNum); err != nil {
t.Fatal(err)
}
}
该测试框架的实现位于 leetcode/testutil/leetcode.go:RunLeetCodeFuncWithExamples 先通过反射(reflect.TypeOf、reflect.NumIn、reflect.NumOut)校验传入函数签名的合法性,再对每组样例做「输入个数 = 参数个数、输出个数 = 返回值个数」的校验,随后用 parseRawArg 把字符串形式的样例按参数类型递归解析为真实值——例如 reflect.Slice 分支会先调用 parseRawArray 切分数组元素,再对元素类型递归解析。targetCaseNum 为 0 时执行全部样例,为负数(如 -1)时定位到最后一个样例,便于单点调试。这意味着在仓库根目录执行 go test ./leetcode/weekly/277/d/ 即可自动验证本题两种示例,无需手工构造输入。
这种「字符串样例 + 反射驱动」的测试方式,让 LeetCode 题解文件的维护者可以把精力集中在算法本身,用例数据的增删改都只涉及 examples 数组,是仓库内数百道周赛题统一采用的回归保障手段。
位运算细节与边界情况
结合源码与题解,以下三个实现细节值得展开:
- 从
i = 1开始枚举:题解明确建议从i = 1而非i = 0开始。i = 0代表全员坏人,此时没有任何好人的陈述需要校验,任何矩阵都「合法」,但好人数恒为 0,绝不可能是最大值,跳过它只是纯粹的常数优化。 st < 2的语义:陈述值只有0/1/2三种。st < 2等价于「该陈述不是未表态」,即第j个人确实对第k个人下了结论。只有这种陈述才可能揭示矛盾;值为2时无论对方实际身份如何,都不影响一致性。continue next/goto next的剪枝效果:矛盾一旦出现,整个掩码即被判定非法,无需再检查其余陈述或累计cnt。这种「提前短路」不仅写法紧凑,在实际数据下也能显著减少内层循环的执行次数。
另外从仓库位运算模板 bits.go 可以看到,lowbit、isSubset、isPow2 等常用位运算工具都被统一整理并注入到编辑器片段中,供快速调用;而 search.go 在讲解「任意子集」时也特意注明「位运算写法见 loopCollection」,说明二进制枚举正是本仓库在处理指数级枚举类题目时的首选实现方式。本题 1 << n 枚举 + 位测试的思路,与该模板家族的风格完全一致。
思考题与题解延伸
题解文档在正文末尾提出了一个值得继续推导的思考题(d.md):
如果坏人一定说假话呢?
这意味着原题中的「坏人随意说」假设被收紧为「坏人必须说假话」,校验逻辑将从「只查好人」变为「好人全部陈述必须为真、坏人全部陈述必须为假」,两边的陈述都要与掩码状态严格一致。本题正是 Codeforces 上的 CF1594D The Number of Imposters(题解文档中已注明出处),这类「身份 + 陈述一致性」问题在 OI/ACM 中非常常见,通常配合并查集或图论建模求解;而当规模缩小到可枚举时,二进制枚举同样是最直接可靠的暴力手段。
从方法论上看,本题的价值在于展示了「位掩码 + 状态校验」这一通用模式:当问题输入规模极小时(如 n ≤ 15、n ≤ 20),与其设计精巧的贪心或 DP,不如直接枚举全部 2^n 种状态并逐一验证约束,代码短、易证明、不易出错。该模式可以迁移到大量类似的「逻辑身份」「条件指派」「子集可行性」题目中,而 copypasta/search.go 中整理的「回溯/子集/组合」题单正是这些思路的延伸练习素材。
总结
本文以 codeforces-go 仓库中的 d.md 题解为主体,系统讲解了 LeetCode 5992「基于陈述统计最多好人数」的二进制枚举解法:用掩码 i ∈ [1, 2^n) 枚举好人子集,用 st < 2 && st != i >> k & 1 完成陈述一致性校验,最终取所有合法方案中好人数的最大值。解法时间复杂度 O(n² · 2^n)、空间复杂度 O(1),在 n ≤ 15 的限制下是既高效又稳妥的方案。通过仓库中的 Go 实现、示例测试 与 反射驱动的测试框架,你可以直接复现、验证并进一步改造这一经典位运算枚举模型。