1. 项目概述从“审美课”到算法实战看到“ALGO-194 审美课”这个标题很多刚接触蓝桥杯算法训练的同学可能会一愣这听起来像是一门艺术鉴赏课怎么跑到算法题库里来了这正是蓝桥杯题目设计的巧妙之处它常常用生活化、趣味化的场景包裹着核心的算法考点。这道题本质上是一个关于“状态压缩”和“位运算”的经典问题它考察的是你如何高效地处理和分析大量二进制状态对。我当年第一次做这道题时也被这个文艺的标题“骗”了深入分析后才发现它是一道锻炼思维和代码优化能力的绝佳题目。对于正在备赛的同学来说吃透这道题不仅能掌握一个重要的算法技巧更能提升你从实际问题中抽象出数学模型的能力。接下来我就结合自己的解题和教学经验带你一步步拆解这道“审美课”看看它到底在考什么以及如何漂亮地拿下它。2. 核心需求与问题抽象2.1 题目场景还原与理解我们先抛开代码想象一下题目描述的场景有一门“审美课”老师给每位学生发了一张有n道判断题的答卷。每道题只有“是”用1表示或“否”用0表示两种答案。因此每个学生的答卷就可以用一个长度为n的二进制串来表示我们称之为该学生的“审美状态”。老师的评判标准很特别他定义两位学生的答案“完全相反”指的是他们对于所有n道题每一题的答案都恰好相反。也就是说如果学生A的答案是1010那么只有答案是0101的学生B才与他完全相反。现在给定所有m位学生的答卷即m个n位的二进制状态我们的任务是统计出有多少对学生是“完全相反”的。举个例子假设n3有5个学生他们的答案如下 学生1: 0 1 0 学生2: 1 0 0 学生3: 0 1 0 学生4: 1 0 1 学生5: 0 1 0那么学生2100和学生4101并不完全相反因为第三位都是1。实际上学生2100的完全相反状态应该是011但这个状态在学生列表中并不存在。学生1、3、5的状态都是010其完全相反状态是101而学生4的状态正是101。因此010和101构成了3对完全相反的组合学生1-4 学生3-4 学生5-4。所以答案是3对。2.2 从暴力枚举到算法优化最直观的想法是暴力枚举遍历每一对学生(i, j)逐位比较他们的答案是否全部相反。这需要O(m^2 * n)的时间复杂度。当m和n增大时题目数据范围通常m可达数万n可达20这个计算量是无法接受的必然会导致超时。这就引出了核心的优化需求我们必须找到一种方法能够快速判断一个状态对应的“完全相反状态”是否存在以及存在多少个。关键在于n的最大值通常不大比如20。一个长度为n的二进制串总共只有2^n种可能的状态对于n20大约是100万。而学生的数量m可能很大但学生的状态却是在这2^n种可能性中取值。因此我们的思路需要发生转变状态压缩将一个学生的答案一个数组压缩成一个整数。例如010可以看作二进制数010也就是十进制2。这样一个整数就代表了一个完整的状态便于存储和计算。哈希映射我们不再关注“学生”这个个体而是关注“答案状态”这个类别。用一个数组count[state]来记录出现“状态state”的学生有多少个。快速求反对于一个状态state如何快速求出其完全相反的状态reverse_state这里就用到位运算。对于一个n位的状态其完全相反状态可以通过state ^ ((1 n) - 1)来获得。(1 n) - 1会得到一个低n位全是1高位全是0的掩码例如n3时得到111即十进制7。state与这个全1掩码进行异或操作效果就是每一位都取反。注意这里有一个非常重要的细节关于n的位数和整数表示范围。我们通常用int32位来存储状态当n20时是足够的。但计算掩码(1 n)时如果n等于31或32直接写1 n可能导致溢出或未定义行为。在竞赛中题目通常会保证n小于等于20但养成好习惯可以使用(1LL n)或确保使用足够宽的数据类型。2.3 算法设计思路基于以上分析算法步骤如下读入与压缩读入每个学生的答案将其转换为一个整数state。计数在count数组中将count[state]的值加1。配对计算遍历所有出现过的状态即count[state] 0的状态。对于每个状态state计算其完全相反的状态reverse_state。如果reverse_state也存在即count[reverse_state] 0那么它们可以配对。配对的对数为count[state] * count[reverse_state]。去重处理注意当我们遍历到state和reverse_state时会计算两次同一对组合例如遍历状态A时算了A-B对遍历状态B时又算了B-A对。因此最终结果需要除以2。一个更巧妙的遍历方法我们只需要遍历state从0到(1 n) - 1的一半范围即可。因为状态state和其相反状态reverse_state是成对出现的我们只计算其中一次。但实现时直接全遍历后除以2更不易出错。3. 核心细节解析与实操要点3.1 状态压缩的代码实现如何将一行输入例如0 1 0 1快速转换成一个整数这里有两种常见方法方法一位运算累加这是最直接和高效的方法。初始化state 0。每读入一个位bit就将state左移一位然后把新的位加到最低位。int state 0; for(int j 0; j n; j) { int bit; scanf(“%d”, bit); // 或者 cin bit; state (state 1) | bit; // 左移后与当前位进行或操作 }假设输入是0 1 0 1过程如下state0读入0:(01)|0 0。读入1:(01)|1 1。读入0:(11)|0 2(二进制10)。读入1:(21)|1 5(二进制101)。最终state 5正确表示了0101。方法二字符串读取有时输入可能没有空格是连续的字符串如“0101”。这时可以这样处理char str[25]; scanf(“%s”, str); int state 0; for(int j 0; j n; j) { state (state 1) | (str[j] - ‘0’); // 字符转数字 }实操心得在竞赛中输入格式一定要看清楚。蓝桥杯的题目有时是空格分隔有时是连续字符串。使用scanf(“%1d”, bit)可以每次只读入一个数字字符并转为整数对于连续无空格的数字串特别有用。但最通用的还是先读成字符串再处理容错性更高。3.2 哈希数组的选择与初始化我们需要一个数组来计数索引是状态最大为2^n - 1值是出现次数。数组大小必须至少为1 n。如果n20则需要2^20 1,048,576个元素。这是一个典型的内存换时间的策略。数据类型count数组的类型取决于学生数量m。m最大可能数万两个状态的学生数相乘可能达到10^8级别仍在int约21亿范围内。但最终结果对数可能超过int因为极端情况下所有学生状态相同且与相反状态配对结果约为m*(m-1)/2对于m10^5结果约5*10^9超过了int。因此count数组可以用int但最终结果和中间计算要用long long。初始化使用全局数组或vector并初始化为0。在C中全局数组会自动初始化为0这是最方便的做法。#include using namespace std; const int MAX_STATE 1 20; // 假设n最大为20 int cnt[MAX_STATE] {0}; // 全局数组自动初始化为03.3 相反状态的计算与配对逻辑这是算法的核心步骤代码简洁但内涵丰富。long long ans 0; int full (1 n) - 1; // 生成n位全1的掩码 for (int state 0; state full; state) { if (cnt[state] 0) { int reverse_state state ^ full; // 异或操作得到完全相反状态 if (cnt[reverse_state] 0) { // 注意这里如果state reverse_state意味着什么 // 这意味着state ^ full state即state的每一位取反后等于自身这只有全0和全1与full相同在异或full时才可能。 // 实际上对于一个状态其相反状态是唯一的。 // 当state和reverse_state不同时我们会计算两次所以需要除以2。 // 但当state和reverse_state相同时即状态为全0或全1自己和自己配对计算一次就是正确的不能除以2。 // 更安全的做法是只累计 state reverse_state 的情况或者最后统一除以2。 // 我们采用最后统一除以2的方法因为它逻辑简单且对全0/全1状态也适用因为自己配对自己会被算两次吗我们来验证一下。 // 假设只有全0状态cnt[0]k。遍历到state0时reverse_statefull。如果full状态cnt为0则不会累加。 // 所以全0状态无法和自己形成“完全相反”对因为相反状态是全1。同理全1也是。 // 因此不存在“自己和自己完全相反”的情况所以所有配对都是两个不同的状态。 // 那么在循环中state和reverse_state只要不同就会被计算两次。 ans (long long)cnt[state] * cnt[reverse_state]; } } } ans / 2; // 因为每一对都被计算了两次 cout ans endl;关键点剖析state ^ full这是求反操作的灵魂。异或运算的规则是“相同为0不同为1”。state的每一位与1异或结果就是该位取反。遍历范围我们遍历了所有可能的状态0到full而不是只遍历输入中出现的状态。这是因为我们需要检查每一个状态的相反状态是否存在。虽然多了一些循环但总次数是2^n最多约100万在现代计算机上完全可以接受且代码更清晰。去重与整除ans / 2是必须的。思考一下对于状态A和BA与B相反当state A时我们累加了cnt[A]*cnt[B]当state B时我们又累加了cnt[B]*cnt[A]这是同一对组合。所以总和是实际对数的两倍。3.4 边界条件与特殊案例思考n1 的情况只有两种状态0和1。如果输入中既有0也有1那么它们互为相反状态。算法能正确处理。所有学生答案相同例如所有学生都是状态5。那么状态5的相反状态是(5 ^ full)。如果这个相反状态没有学生则ans为0。符合预期因为没有完全相反的两个人。最大数据测试当n20, m100000时cnt数组大小约100万内存占用约4MBint型可以接受。循环2^20次约100万次每次是常数操作时间上也完全没问题。这是典型的用空间换时间将原本O(m^2)的复杂度降到了O(m 2^n)。4. 完整代码实现与逐行解读下面给出一个完整的C实现并附上详细注释。#include #include using namespace std; // 常量定义120 是 2^20用于确定数组大小。题目通常保证n20。 const int MAX_STATE 1 20; int main() { // n: 问题数/位数 m: 学生数 int n, m; scanf(“%d %d”, n, m); // cnt数组用于统计每个状态出现的次数。下标就是压缩后的状态值。 // 使用静态数组初始化为0。大小设为 120 是安全的因为n最大20。 static int cnt[MAX_STATE] {0}; // 读取m个学生的数据 for (int i 0; i m; i) { int state 0; for (int j 0; j n; j) { int bit; // 注意这里使用 %1d 可以方便地读取连续输入中的单个数字。 // 如果输入是空格分隔的用 %d 即可。 scanf(“%1d”, bit); // 状态压缩核心左移一位然后加上新的位。 state (state 1) | bit; } // 该状态出现次数加一 cnt[state]; } // full 是n位全1的掩码用于求反。 int full (1 n) - 1; long long ans 0; // 结果可能很大用long long // 遍历所有可能的状态 for (int state 0; state full; state) { // 只处理出现过的状态避免不必要的计算 if (cnt[state] 0) { // 计算当前状态的完全相反状态 int reverse_state state ^ full; // 如果相反状态也存在学生 if (cnt[reverse_state] 0) { // 累加配对数量。注意转换为long long防止乘法溢出。 ans (long long)cnt[state] * cnt[reverse_state]; } } } // 每一对都被计算了两次state和reverse_state各一次所以除以2。 ans / 2; printf(“%lld\n”, ans); // 输出结果 return 0; }逐行解读与优化点static int cnt[MAX_STATE] {0};使用static关键字将数组定义在全局区实际上是在函数内的静态存储区并初始化为0。这比在main函数内定义大型数组在栈上更安全避免了栈溢出的风险。这是处理大数组的一个常用技巧。scanf(“%1d”, bit);格式符%1d表示读取一个整数但宽度限制为1位。这非常适合题目输入是连续数字字符如0101的情况。如果题目明确是空格分隔用%d更简单。务必根据实际题目输入样例调整。state (state 1) | bit;这是状态压缩的经典一行代码。state 1将已有位左移腾出最低位。| bit将新的位放在最低位。请确保bit的值是0或1。int full (1 n) - 1;计算全1掩码。1 n得到第n位为1的数如n3得到1000即8减1后得到低n位全1111即7。循环中的if (cnt[state] 0)这是一个重要的优化。虽然遍历了所有状态但只对出现过的状态进行处理避免了大量无用的异或和乘法操作。(long long)cnt[state] * cnt[reverse_state];强制类型转换。因为cnt是int乘积可能超过int范围先转换为long long再相乘确保中间结果正确。ans / 2;去重的关键步骤。5. 常见问题与排查技巧实录在实际解题和调试过程中我遇到过不少坑。这里总结几个典型问题及其解决方法。5.1 错误答案整数溢出问题现象程序在小数据时运行正确但提交后部分测试点错误尤其是大数据点。排查思路首先检查ans的数据类型。如果用的是int当配对数量很大时例如m50000且两种状态各一半结果约为25000*25000625,000,000仍在int范围内。但若m更大就会溢出。安全起见一律使用long long。其次检查乘法运算cnt[state] * cnt[reverse_state]。即使ans是long long但两个int相乘的结果会先以int类型计算可能已经溢出然后再赋值给long long。这就是上面代码中(long long)cnt[state] * cnt[reverse_state]强制转换的原因。必须先将其中一个操作数转为long long。修正方法// 错误写法可能溢出 ans cnt[state] * cnt[reverse_state]; // 正确写法1强制转换 ans (long long)cnt[state] * cnt[reverse_state]; // 正确写法2使用1LL乘触发类型提升 ans 1LL * cnt[state] * cnt[reverse_state];5.2 运行超时算法复杂度问题问题现象程序运行时间过长无法通过所有测试点。排查思路确认是否使用了O(m^2)的双重循环暴力比较。这是最可能的原因。检查输入输出效率。如果m和n很大使用cin/cout而没有关闭同步流可能会导致超时。在竞赛中对于大量数据输入建议使用scanf/printf或使用ios::sync_with_stdio(false); cin.tie(0);加速cin/cout。检查数组访问是否在合理范围内。cnt数组的大小必须是1 n如果开小了可能导致访问越界引发未定义行为有时表现为程序卡死或超时。修正方法确保使用本文所述的“状态压缩哈希计数”算法复杂度为O(m*n 2^n)。对于C使用scanf/printf或加速后的cin/cout。仔细计算MAX_STATE常量确保足够大。5.3 答案偏小或为0状态压缩错误问题现象程序能运行但输出结果明显比预期小甚至为0。排查思路状态压缩逻辑错误最常见的是位运算顺序错误。例如先加位再左移或者读入的顺序与题目要求不符题目是从左到右读代码是从右到左处理。输入格式不匹配题目输入可能是空格分隔但代码用了%1d连续读或者反过来。这会导致state的值完全错误。求反操作错误错误地使用了按位取反运算符~。在C中~state是对state的所有位包括高位的0取反而不是只对低n位取反。例如对于一个8位整数实际int是32位state5(00000101)~state会是11111010高位补1这显然不是我们想要的。正确的做法是state ^ full。调试技巧在读取完第一个学生的数据后打印出其计算出的state值并手动验证是否正确。打印出full的值看是否为预期的2^n - 1。对于前几个状态手动计算其reverse_state并打印看是否正确。// 调试示例在读取循环后添加 // printf(“Student %d state: %d (binary: “, i, state); // for(int kn-1; k0; k--) printf(“%d”, (statek)1); // printf(“)\n”);5.4 内存超限数组开得过大或数据类型过大问题现象提交后反馈“内存超限”MLE。排查思路cnt数组开得太大。如果n的最大值是20120是约100万。如果错误地开成了125约3300万对于int数组就会占用约130MB内存很容易超限。使用了long long类型的cnt数组。100万个long long占用约8MB而100万个int占用约4MB。在内存限制严格的比赛中这可能成为压垮骆驼的最后一根稻草。只要学生数量m用int能存下cnt数组就用int。修正方法准确根据题目给出的n的最大范围定义数组大小。如果不确定可以稍微开大一点例如const int MAX_STATE 1 20 5;。除非必要否则cnt数组使用int类型。5.5 关于“遍历一半状态”的优化讨论在之前的分析中我们提到可以只遍历state从0到(1 n) - 1的一半以避免最后除以2。代码可以这样写long long ans 0; int full (1 n) - 1; for (int state 0; state (1 (n-1)); state) { // 只遍历前一半 if (cnt[state] 0) { int reverse_state state ^ full; if (cnt[reverse_state] 0) { ans (long long)cnt[state] * cnt[reverse_state]; } } } // 不需要 ans / 2;为什么可以这样因为状态是成对出现的state和reverse_state。当state遍历到一半时它的相反状态reverse_state必然在另一半中。这样每一对组合只被计算一次。注意事项这种方法要求state和reverse_state不能相同。前面我们已经论证过一个状态和自身完全相反的情况不存在除非n0这没有意义。所以是安全的。循环的终止条件是state (1 (n-1))。这是因为对于n位状态总共有2^n个前一半的数量就是2^(n-1)个。这种写法比state full/2更准确因为full是奇数时full/2是向下取整。个人建议对于初学者我推荐使用“全遍历后除以2”的方法。虽然多了一点点计算但逻辑更清晰更不容易出错。在竞赛中代码的清晰性和正确性比微小的性能优化更重要。只有当性能成为瓶颈时才考虑这种优化。6. 算法扩展与思维提升解决了基础问题我们可以思考一些变种和延伸这有助于在比赛中遇到类似问题时快速识别并解决。6.1 变种一求“恰好有k位相反”的对数如果问题不是“完全相反”而是“恰好有k位相反”该如何求解思路这时状态压缩依然有效但配对条件变了。对于状态A我们需要找到所有与A有k位不同的状态B。暴力法遍历所有状态B计算A ^ B的二进制中1的个数即汉明距离如果等于k则计数。复杂度O(m * 2^n)在n较大时不可行。组合枚举法对于状态A要得到恰好k位不同的状态我们可以枚举n个位置中选k个位置进行翻转0变11变0。这需要枚举C(n, k)种组合。对于每个组合计算翻转后的新状态B然后查看cnt[B]。复杂度O(m * C(n, k))。当k较小时比如1, 2, 3这种方法可行k接近n/2时组合数会爆炸。位运算技巧没有特别通用的高效算法。这类问题可能考察的是对位运算和枚举的掌握。6.2 变种二状态数量极大时的优化n较大如果n大到30甚至更多2^n的状态数量无法用数组直接存储10亿以上。此时该怎么办思路当状态空间太大无法直接哈希时需要转换思路。使用标准库容器用unordered_map或map来存储(state, count)对只存储实际出现过的状态。配对时遍历map中的每个状态计算其相反状态并在map中查找。复杂度O(m * logm)或O(m)平均取决于unordered_map。折半搜索/Meet in the Middle如果n非常大比如40且问题可以转化为寻找满足某种条件的两个状态组合有时可以将状态拆分成两半分别枚举并存储结果再组合起来。但这道题“完全相反”的条件是全局的不太适合直接折半。使用unordered_map的代码示例#include #include using namespace std; int main() { int n, m; scanf(“%d %d”, n, m); unordered_map cnt_map; for (int i 0; i m; i) { int state 0; for (int j 0; j n; j) { int bit; scanf(“%1d”, bit); state (state 1) | bit; } cnt_map[state]; } int full (1 n) - 1; long long ans 0; // 注意遍历map时不能直接在循环中修改map如erase可能使迭代器失效。 // 但我们只是读取是安全的。 for (auto kv : cnt_map) { int state kv.first; int reverse_state state ^ full; auto it cnt_map.find(reverse_state); if (it ! cnt_map.end()) { // 注意这里会计算两次和数组方法一样 ans (long long)kv.second * it-second; } } ans / 2; printf(“%lld\n”, ans); return 0; }注意使用unordered_map后内存占用取决于不同状态的数量而不是2^n。但查找操作虽然平均是O(1)常数比数组大可能会慢一些。在n20时数组法几乎总是更快。但当n较大时unordered_map是唯一可行的选择。6.3 思维提升位运算的实战意义“审美课”这道题是学习位运算应用的绝佳案例。它展示了位运算在状态表示、转换和比较上的高效与优雅。状态压缩将多维的、离散的布尔状态用一个整数表示极大地减少了存储和比较的开销。异或运算用于快速比较差异A ^ B的结果中1的位数即汉明距离或进行特定位翻转与1异或取反。移位与掩码用于提取、设置或清除特定位。在竞赛和实际开发中位运算常用于子集枚举用二进制位表示集合元素是否存在。棋盘类、网格类问题的状态表示。权限系统用位表示不同权限。高性能计算和底层优化。掌握这道题不仅仅是解决了一个问题更是获得了一把解决一大类“状态”相关问题的钥匙。在后续遇到类似“每个人的属性是一个二进制向量寻找满足某种位运算关系的配对”问题时你会立刻联想到“审美课”的解法。
1. 项目概述从“审美课”到算法实战看到“ALGO-194 审美课”这个标题很多刚接触蓝桥杯算法训练的同学可能会一愣这听起来像是一门艺术鉴赏课怎么跑到算法题库里来了这正是蓝桥杯题目设计的巧妙之处它常常用生活化、趣味化的场景包裹着核心的算法考点。这道题本质上是一个关于“状态压缩”和“位运算”的经典问题它考察的是你如何高效地处理和分析大量二进制状态对。我当年第一次做这道题时也被这个文艺的标题“骗”了深入分析后才发现它是一道锻炼思维和代码优化能力的绝佳题目。对于正在备赛的同学来说吃透这道题不仅能掌握一个重要的算法技巧更能提升你从实际问题中抽象出数学模型的能力。接下来我就结合自己的解题和教学经验带你一步步拆解这道“审美课”看看它到底在考什么以及如何漂亮地拿下它。2. 核心需求与问题抽象2.1 题目场景还原与理解我们先抛开代码想象一下题目描述的场景有一门“审美课”老师给每位学生发了一张有n道判断题的答卷。每道题只有“是”用1表示或“否”用0表示两种答案。因此每个学生的答卷就可以用一个长度为n的二进制串来表示我们称之为该学生的“审美状态”。老师的评判标准很特别他定义两位学生的答案“完全相反”指的是他们对于所有n道题每一题的答案都恰好相反。也就是说如果学生A的答案是1010那么只有答案是0101的学生B才与他完全相反。现在给定所有m位学生的答卷即m个n位的二进制状态我们的任务是统计出有多少对学生是“完全相反”的。举个例子假设n3有5个学生他们的答案如下 学生1: 0 1 0 学生2: 1 0 0 学生3: 0 1 0 学生4: 1 0 1 学生5: 0 1 0那么学生2100和学生4101并不完全相反因为第三位都是1。实际上学生2100的完全相反状态应该是011但这个状态在学生列表中并不存在。学生1、3、5的状态都是010其完全相反状态是101而学生4的状态正是101。因此010和101构成了3对完全相反的组合学生1-4 学生3-4 学生5-4。所以答案是3对。2.2 从暴力枚举到算法优化最直观的想法是暴力枚举遍历每一对学生(i, j)逐位比较他们的答案是否全部相反。这需要O(m^2 * n)的时间复杂度。当m和n增大时题目数据范围通常m可达数万n可达20这个计算量是无法接受的必然会导致超时。这就引出了核心的优化需求我们必须找到一种方法能够快速判断一个状态对应的“完全相反状态”是否存在以及存在多少个。关键在于n的最大值通常不大比如20。一个长度为n的二进制串总共只有2^n种可能的状态对于n20大约是100万。而学生的数量m可能很大但学生的状态却是在这2^n种可能性中取值。因此我们的思路需要发生转变状态压缩将一个学生的答案一个数组压缩成一个整数。例如010可以看作二进制数010也就是十进制2。这样一个整数就代表了一个完整的状态便于存储和计算。哈希映射我们不再关注“学生”这个个体而是关注“答案状态”这个类别。用一个数组count[state]来记录出现“状态state”的学生有多少个。快速求反对于一个状态state如何快速求出其完全相反的状态reverse_state这里就用到位运算。对于一个n位的状态其完全相反状态可以通过state ^ ((1 n) - 1)来获得。(1 n) - 1会得到一个低n位全是1高位全是0的掩码例如n3时得到111即十进制7。state与这个全1掩码进行异或操作效果就是每一位都取反。注意这里有一个非常重要的细节关于n的位数和整数表示范围。我们通常用int32位来存储状态当n20时是足够的。但计算掩码(1 n)时如果n等于31或32直接写1 n可能导致溢出或未定义行为。在竞赛中题目通常会保证n小于等于20但养成好习惯可以使用(1LL n)或确保使用足够宽的数据类型。2.3 算法设计思路基于以上分析算法步骤如下读入与压缩读入每个学生的答案将其转换为一个整数state。计数在count数组中将count[state]的值加1。配对计算遍历所有出现过的状态即count[state] 0的状态。对于每个状态state计算其完全相反的状态reverse_state。如果reverse_state也存在即count[reverse_state] 0那么它们可以配对。配对的对数为count[state] * count[reverse_state]。去重处理注意当我们遍历到state和reverse_state时会计算两次同一对组合例如遍历状态A时算了A-B对遍历状态B时又算了B-A对。因此最终结果需要除以2。一个更巧妙的遍历方法我们只需要遍历state从0到(1 n) - 1的一半范围即可。因为状态state和其相反状态reverse_state是成对出现的我们只计算其中一次。但实现时直接全遍历后除以2更不易出错。3. 核心细节解析与实操要点3.1 状态压缩的代码实现如何将一行输入例如0 1 0 1快速转换成一个整数这里有两种常见方法方法一位运算累加这是最直接和高效的方法。初始化state 0。每读入一个位bit就将state左移一位然后把新的位加到最低位。int state 0; for(int j 0; j n; j) { int bit; scanf(“%d”, bit); // 或者 cin bit; state (state 1) | bit; // 左移后与当前位进行或操作 }假设输入是0 1 0 1过程如下state0读入0:(01)|0 0。读入1:(01)|1 1。读入0:(11)|0 2(二进制10)。读入1:(21)|1 5(二进制101)。最终state 5正确表示了0101。方法二字符串读取有时输入可能没有空格是连续的字符串如“0101”。这时可以这样处理char str[25]; scanf(“%s”, str); int state 0; for(int j 0; j n; j) { state (state 1) | (str[j] - ‘0’); // 字符转数字 }实操心得在竞赛中输入格式一定要看清楚。蓝桥杯的题目有时是空格分隔有时是连续字符串。使用scanf(“%1d”, bit)可以每次只读入一个数字字符并转为整数对于连续无空格的数字串特别有用。但最通用的还是先读成字符串再处理容错性更高。3.2 哈希数组的选择与初始化我们需要一个数组来计数索引是状态最大为2^n - 1值是出现次数。数组大小必须至少为1 n。如果n20则需要2^20 1,048,576个元素。这是一个典型的内存换时间的策略。数据类型count数组的类型取决于学生数量m。m最大可能数万两个状态的学生数相乘可能达到10^8级别仍在int约21亿范围内。但最终结果对数可能超过int因为极端情况下所有学生状态相同且与相反状态配对结果约为m*(m-1)/2对于m10^5结果约5*10^9超过了int。因此count数组可以用int但最终结果和中间计算要用long long。初始化使用全局数组或vector并初始化为0。在C中全局数组会自动初始化为0这是最方便的做法。#include using namespace std; const int MAX_STATE 1 20; // 假设n最大为20 int cnt[MAX_STATE] {0}; // 全局数组自动初始化为03.3 相反状态的计算与配对逻辑这是算法的核心步骤代码简洁但内涵丰富。long long ans 0; int full (1 n) - 1; // 生成n位全1的掩码 for (int state 0; state full; state) { if (cnt[state] 0) { int reverse_state state ^ full; // 异或操作得到完全相反状态 if (cnt[reverse_state] 0) { // 注意这里如果state reverse_state意味着什么 // 这意味着state ^ full state即state的每一位取反后等于自身这只有全0和全1与full相同在异或full时才可能。 // 实际上对于一个状态其相反状态是唯一的。 // 当state和reverse_state不同时我们会计算两次所以需要除以2。 // 但当state和reverse_state相同时即状态为全0或全1自己和自己配对计算一次就是正确的不能除以2。 // 更安全的做法是只累计 state reverse_state 的情况或者最后统一除以2。 // 我们采用最后统一除以2的方法因为它逻辑简单且对全0/全1状态也适用因为自己配对自己会被算两次吗我们来验证一下。 // 假设只有全0状态cnt[0]k。遍历到state0时reverse_statefull。如果full状态cnt为0则不会累加。 // 所以全0状态无法和自己形成“完全相反”对因为相反状态是全1。同理全1也是。 // 因此不存在“自己和自己完全相反”的情况所以所有配对都是两个不同的状态。 // 那么在循环中state和reverse_state只要不同就会被计算两次。 ans (long long)cnt[state] * cnt[reverse_state]; } } } ans / 2; // 因为每一对都被计算了两次 cout ans endl;关键点剖析state ^ full这是求反操作的灵魂。异或运算的规则是“相同为0不同为1”。state的每一位与1异或结果就是该位取反。遍历范围我们遍历了所有可能的状态0到full而不是只遍历输入中出现的状态。这是因为我们需要检查每一个状态的相反状态是否存在。虽然多了一些循环但总次数是2^n最多约100万在现代计算机上完全可以接受且代码更清晰。去重与整除ans / 2是必须的。思考一下对于状态A和BA与B相反当state A时我们累加了cnt[A]*cnt[B]当state B时我们又累加了cnt[B]*cnt[A]这是同一对组合。所以总和是实际对数的两倍。3.4 边界条件与特殊案例思考n1 的情况只有两种状态0和1。如果输入中既有0也有1那么它们互为相反状态。算法能正确处理。所有学生答案相同例如所有学生都是状态5。那么状态5的相反状态是(5 ^ full)。如果这个相反状态没有学生则ans为0。符合预期因为没有完全相反的两个人。最大数据测试当n20, m100000时cnt数组大小约100万内存占用约4MBint型可以接受。循环2^20次约100万次每次是常数操作时间上也完全没问题。这是典型的用空间换时间将原本O(m^2)的复杂度降到了O(m 2^n)。4. 完整代码实现与逐行解读下面给出一个完整的C实现并附上详细注释。#include #include using namespace std; // 常量定义120 是 2^20用于确定数组大小。题目通常保证n20。 const int MAX_STATE 1 20; int main() { // n: 问题数/位数 m: 学生数 int n, m; scanf(“%d %d”, n, m); // cnt数组用于统计每个状态出现的次数。下标就是压缩后的状态值。 // 使用静态数组初始化为0。大小设为 120 是安全的因为n最大20。 static int cnt[MAX_STATE] {0}; // 读取m个学生的数据 for (int i 0; i m; i) { int state 0; for (int j 0; j n; j) { int bit; // 注意这里使用 %1d 可以方便地读取连续输入中的单个数字。 // 如果输入是空格分隔的用 %d 即可。 scanf(“%1d”, bit); // 状态压缩核心左移一位然后加上新的位。 state (state 1) | bit; } // 该状态出现次数加一 cnt[state]; } // full 是n位全1的掩码用于求反。 int full (1 n) - 1; long long ans 0; // 结果可能很大用long long // 遍历所有可能的状态 for (int state 0; state full; state) { // 只处理出现过的状态避免不必要的计算 if (cnt[state] 0) { // 计算当前状态的完全相反状态 int reverse_state state ^ full; // 如果相反状态也存在学生 if (cnt[reverse_state] 0) { // 累加配对数量。注意转换为long long防止乘法溢出。 ans (long long)cnt[state] * cnt[reverse_state]; } } } // 每一对都被计算了两次state和reverse_state各一次所以除以2。 ans / 2; printf(“%lld\n”, ans); // 输出结果 return 0; }逐行解读与优化点static int cnt[MAX_STATE] {0};使用static关键字将数组定义在全局区实际上是在函数内的静态存储区并初始化为0。这比在main函数内定义大型数组在栈上更安全避免了栈溢出的风险。这是处理大数组的一个常用技巧。scanf(“%1d”, bit);格式符%1d表示读取一个整数但宽度限制为1位。这非常适合题目输入是连续数字字符如0101的情况。如果题目明确是空格分隔用%d更简单。务必根据实际题目输入样例调整。state (state 1) | bit;这是状态压缩的经典一行代码。state 1将已有位左移腾出最低位。| bit将新的位放在最低位。请确保bit的值是0或1。int full (1 n) - 1;计算全1掩码。1 n得到第n位为1的数如n3得到1000即8减1后得到低n位全1111即7。循环中的if (cnt[state] 0)这是一个重要的优化。虽然遍历了所有状态但只对出现过的状态进行处理避免了大量无用的异或和乘法操作。(long long)cnt[state] * cnt[reverse_state];强制类型转换。因为cnt是int乘积可能超过int范围先转换为long long再相乘确保中间结果正确。ans / 2;去重的关键步骤。5. 常见问题与排查技巧实录在实际解题和调试过程中我遇到过不少坑。这里总结几个典型问题及其解决方法。5.1 错误答案整数溢出问题现象程序在小数据时运行正确但提交后部分测试点错误尤其是大数据点。排查思路首先检查ans的数据类型。如果用的是int当配对数量很大时例如m50000且两种状态各一半结果约为25000*25000625,000,000仍在int范围内。但若m更大就会溢出。安全起见一律使用long long。其次检查乘法运算cnt[state] * cnt[reverse_state]。即使ans是long long但两个int相乘的结果会先以int类型计算可能已经溢出然后再赋值给long long。这就是上面代码中(long long)cnt[state] * cnt[reverse_state]强制转换的原因。必须先将其中一个操作数转为long long。修正方法// 错误写法可能溢出 ans cnt[state] * cnt[reverse_state]; // 正确写法1强制转换 ans (long long)cnt[state] * cnt[reverse_state]; // 正确写法2使用1LL乘触发类型提升 ans 1LL * cnt[state] * cnt[reverse_state];5.2 运行超时算法复杂度问题问题现象程序运行时间过长无法通过所有测试点。排查思路确认是否使用了O(m^2)的双重循环暴力比较。这是最可能的原因。检查输入输出效率。如果m和n很大使用cin/cout而没有关闭同步流可能会导致超时。在竞赛中对于大量数据输入建议使用scanf/printf或使用ios::sync_with_stdio(false); cin.tie(0);加速cin/cout。检查数组访问是否在合理范围内。cnt数组的大小必须是1 n如果开小了可能导致访问越界引发未定义行为有时表现为程序卡死或超时。修正方法确保使用本文所述的“状态压缩哈希计数”算法复杂度为O(m*n 2^n)。对于C使用scanf/printf或加速后的cin/cout。仔细计算MAX_STATE常量确保足够大。5.3 答案偏小或为0状态压缩错误问题现象程序能运行但输出结果明显比预期小甚至为0。排查思路状态压缩逻辑错误最常见的是位运算顺序错误。例如先加位再左移或者读入的顺序与题目要求不符题目是从左到右读代码是从右到左处理。输入格式不匹配题目输入可能是空格分隔但代码用了%1d连续读或者反过来。这会导致state的值完全错误。求反操作错误错误地使用了按位取反运算符~。在C中~state是对state的所有位包括高位的0取反而不是只对低n位取反。例如对于一个8位整数实际int是32位state5(00000101)~state会是11111010高位补1这显然不是我们想要的。正确的做法是state ^ full。调试技巧在读取完第一个学生的数据后打印出其计算出的state值并手动验证是否正确。打印出full的值看是否为预期的2^n - 1。对于前几个状态手动计算其reverse_state并打印看是否正确。// 调试示例在读取循环后添加 // printf(“Student %d state: %d (binary: “, i, state); // for(int kn-1; k0; k--) printf(“%d”, (statek)1); // printf(“)\n”);5.4 内存超限数组开得过大或数据类型过大问题现象提交后反馈“内存超限”MLE。排查思路cnt数组开得太大。如果n的最大值是20120是约100万。如果错误地开成了125约3300万对于int数组就会占用约130MB内存很容易超限。使用了long long类型的cnt数组。100万个long long占用约8MB而100万个int占用约4MB。在内存限制严格的比赛中这可能成为压垮骆驼的最后一根稻草。只要学生数量m用int能存下cnt数组就用int。修正方法准确根据题目给出的n的最大范围定义数组大小。如果不确定可以稍微开大一点例如const int MAX_STATE 1 20 5;。除非必要否则cnt数组使用int类型。5.5 关于“遍历一半状态”的优化讨论在之前的分析中我们提到可以只遍历state从0到(1 n) - 1的一半以避免最后除以2。代码可以这样写long long ans 0; int full (1 n) - 1; for (int state 0; state (1 (n-1)); state) { // 只遍历前一半 if (cnt[state] 0) { int reverse_state state ^ full; if (cnt[reverse_state] 0) { ans (long long)cnt[state] * cnt[reverse_state]; } } } // 不需要 ans / 2;为什么可以这样因为状态是成对出现的state和reverse_state。当state遍历到一半时它的相反状态reverse_state必然在另一半中。这样每一对组合只被计算一次。注意事项这种方法要求state和reverse_state不能相同。前面我们已经论证过一个状态和自身完全相反的情况不存在除非n0这没有意义。所以是安全的。循环的终止条件是state (1 (n-1))。这是因为对于n位状态总共有2^n个前一半的数量就是2^(n-1)个。这种写法比state full/2更准确因为full是奇数时full/2是向下取整。个人建议对于初学者我推荐使用“全遍历后除以2”的方法。虽然多了一点点计算但逻辑更清晰更不容易出错。在竞赛中代码的清晰性和正确性比微小的性能优化更重要。只有当性能成为瓶颈时才考虑这种优化。6. 算法扩展与思维提升解决了基础问题我们可以思考一些变种和延伸这有助于在比赛中遇到类似问题时快速识别并解决。6.1 变种一求“恰好有k位相反”的对数如果问题不是“完全相反”而是“恰好有k位相反”该如何求解思路这时状态压缩依然有效但配对条件变了。对于状态A我们需要找到所有与A有k位不同的状态B。暴力法遍历所有状态B计算A ^ B的二进制中1的个数即汉明距离如果等于k则计数。复杂度O(m * 2^n)在n较大时不可行。组合枚举法对于状态A要得到恰好k位不同的状态我们可以枚举n个位置中选k个位置进行翻转0变11变0。这需要枚举C(n, k)种组合。对于每个组合计算翻转后的新状态B然后查看cnt[B]。复杂度O(m * C(n, k))。当k较小时比如1, 2, 3这种方法可行k接近n/2时组合数会爆炸。位运算技巧没有特别通用的高效算法。这类问题可能考察的是对位运算和枚举的掌握。6.2 变种二状态数量极大时的优化n较大如果n大到30甚至更多2^n的状态数量无法用数组直接存储10亿以上。此时该怎么办思路当状态空间太大无法直接哈希时需要转换思路。使用标准库容器用unordered_map或map来存储(state, count)对只存储实际出现过的状态。配对时遍历map中的每个状态计算其相反状态并在map中查找。复杂度O(m * logm)或O(m)平均取决于unordered_map。折半搜索/Meet in the Middle如果n非常大比如40且问题可以转化为寻找满足某种条件的两个状态组合有时可以将状态拆分成两半分别枚举并存储结果再组合起来。但这道题“完全相反”的条件是全局的不太适合直接折半。使用unordered_map的代码示例#include #include using namespace std; int main() { int n, m; scanf(“%d %d”, n, m); unordered_map cnt_map; for (int i 0; i m; i) { int state 0; for (int j 0; j n; j) { int bit; scanf(“%1d”, bit); state (state 1) | bit; } cnt_map[state]; } int full (1 n) - 1; long long ans 0; // 注意遍历map时不能直接在循环中修改map如erase可能使迭代器失效。 // 但我们只是读取是安全的。 for (auto kv : cnt_map) { int state kv.first; int reverse_state state ^ full; auto it cnt_map.find(reverse_state); if (it ! cnt_map.end()) { // 注意这里会计算两次和数组方法一样 ans (long long)kv.second * it-second; } } ans / 2; printf(“%lld\n”, ans); return 0; }注意使用unordered_map后内存占用取决于不同状态的数量而不是2^n。但查找操作虽然平均是O(1)常数比数组大可能会慢一些。在n20时数组法几乎总是更快。但当n较大时unordered_map是唯一可行的选择。6.3 思维提升位运算的实战意义“审美课”这道题是学习位运算应用的绝佳案例。它展示了位运算在状态表示、转换和比较上的高效与优雅。状态压缩将多维的、离散的布尔状态用一个整数表示极大地减少了存储和比较的开销。异或运算用于快速比较差异A ^ B的结果中1的位数即汉明距离或进行特定位翻转与1异或取反。移位与掩码用于提取、设置或清除特定位。在竞赛和实际开发中位运算常用于子集枚举用二进制位表示集合元素是否存在。棋盘类、网格类问题的状态表示。权限系统用位表示不同权限。高性能计算和底层优化。掌握这道题不仅仅是解决了一个问题更是获得了一把解决一大类“状态”相关问题的钥匙。在后续遇到类似“每个人的属性是一个二进制向量寻找满足某种位运算关系的配对”问题时你会立刻联想到“审美课”的解法。
算法精解与面试技巧)
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
