二进制枚举与算法优化实战指南

1. 项目概述

"二进制枚举与二进制算法"是算法竞赛入门阶段必须掌握的核心技能之一。作为NEFU算法训练系列的第一课，这个主题看似基础却暗藏玄机。我在ACM竞赛和算法教学中发现，80%的初学者在处理状态压缩问题时都会犯低级错误，而这些问题往往源于对二进制操作的理解偏差。

二进制技巧之所以重要，是因为它能将时间复杂度从O(n!)降到O(2^n)，再配合剪枝优化往往能解决n≤20的NP难问题。在LeetCode周赛中，至少有1-2道中等难度题目可以通过二进制枚举巧妙解决。掌握这些技巧后，你会发现很多看似复杂的排列组合问题，其实都可以用几行位运算代码优雅处理。

2. 二进制枚举基础

2.1 核心概念解析

二进制枚举本质是利用整数的二进制表示来模拟集合操作。假设有n个元素，每个元素对应二进制的一位：1表示选中，0表示不选。例如n=3时：

• 数字5（二进制101）表示选中第1、3个元素
• 数字3（二进制011）表示选中第2、3个元素

这种表示法的优势在于：

1. 内存占用极小：一个int就能表示32个元素的选择状态
2. 集合运算高效：并集用|，交集用&，差集用&~
3. 状态遍历方便：从0到(1<<n)-1的循环就能枚举所有子集

2.2 基本操作模板

cpp复制int n = 5; // 共5个元素
for(int mask = 0; mask < (1<<n); ++mask) {
    // 处理当前mask代表的子集
    for(int i = 0; i < n; ++i) {
        if(mask & (1<<i)) { // 检查第i位是否为1
            // 第i个元素被选中
        }
    }
}

关键点：1<<n 等同于2^n，表示所有可能子集数。内层循环通过1<<i获取第i位的掩码。

3. 二进制算法进阶技巧

3.1 状态压缩DP

当问题具有以下特征时适用：

• 每个决策只有两种状态（选/不选）
• 当前决策只与有限的前置状态相关
• 数据范围n≤25（2^25≈3千万）

典型例题：旅行商问题(TSP)的DP解法。用dp[mask][u]表示经过mask对应城市后停在u点的最短路径。

cpp复制int dp[1<<20]