csp信奥赛c++之状压枚举

csp信奥赛c之状压枚举研究案例GEPPETTO题目描述Geppetto 开了一家披萨店他正在努力做出全市最好的披萨。Geppetto 用N NN种原材料做比萨每种原材料只有一个。原材料标号为1 11到N NN。做披萨很简单只要把原材料混合好然后放进烤箱里烤一烤就行了。但 Geppetto 发现一共有M MM对原材料是冲突的如果一对冲突的原材料混合在一份披萨里这份披萨就会变得十分难吃。这给他带来了额外的麻烦。Geppetto 想知道他最多能做多少种不同的比萨。如果一份比萨上有编号为i ii的原材料而另一份比萨上没有那么这两份比萨就是不同的。输入格式第一行两个整数N , M N,MN,M分别表示原材料总数和冲突总数。接下来M MM行每行两个整数x i , y i x_i,y_ixi​,yi​表示一对冲突中两种原材料的编号。输出格式一行一个整数表示 Geppetto 最多能做多少种披萨。输入输出样例 1输入 13 2 1 2 2 3输出 15输入输出样例 2输入 23 0输出 28输入输出样例 3输入 33 3 1 2 1 3 2 3输出 34说明/提示【样例 1 解释】Geppetto 可以做出以下4种披萨1231 3不过因为 Geppetto 可以不放原材料所以最多可以做出5种披萨。【样例 2 解释】没有原材料冲突所以一共可以做出2 3 8 2^38238种披萨。【样例 3 解释】由于所有原材料都互相冲突所以 Geppetto 只能放一种原材料或者不放原材料一共可以做出1 3 4 134134种披萨。【数据范围】对于100 % 100\%100%的数据1 ≤ N ≤ 20 0 ≤ M ≤ 400 1 ≤ x i , y i ≤ N 1\le N\le 200\le M\le 4001\le x_i,y_i\le N1≤N≤200≤M≤4001≤xi​,yi​≤N保证x i ≠ y i x_i\ne y_ixi​yi​。题目分析题目要求计算使用N NN种原材料制作披萨的方案数其中原材料编号1 ∼ N 1 \sim N1∼N每种原料最多用一次即选取一个子集。有M MM对冲突关系如果一个披萨中同时包含某一对冲突的原材料则该披萨不可行。需要统计所有可行的披萨种类包括空披萨即什么都不放。N ≤ 20 N \le 20N≤20因此总子集数为2 N 2^N2N直接枚举所有子集并检查冲突是可行的。思路分析将原材料编号映射为0 ∼ N − 1 0 \sim N-10∼N−1方便位运算处理。用一个整数s ss的二进制位表示子集第i ii位为1 11表示选取了原材料i ii。枚举s ss从0 00到2 N − 1 2^N - 12N−1。对于每个子集s ss检查所有M MM对冲突( x , y ) (x, y)(x,y)如果s ss中同时包含x xx和y yy即(sx 1) (sy 1)为真则该子集非法否则合法。统计合法子集个数即为答案。时间复杂度O ( 2 N ⋅ M ) O(2^N \cdot M)O(2N⋅M)最坏约4 × 10 8 4 \times 10^84×108次操作C 在极限数据下可能略慢但通常可接受。代码实现#includebits/stdc.h// 万能头文件usingnamespacestd;intn,m,a[410],b[410];// a,b 存储冲突对的两端数组大小根据 M≤400 开够intmain(){// 输入原材料数 n 和冲突对数 mcinnm;for(inti0;im;i){cina[i]b[i];// 将编号转换为 0~n-1方便位运算--a[i];--b[i];}intans0;// 答案计数// 枚举所有子集s 从 0 到 (1n)-1for(ints0;s(1n);s){booloktrue;// 标记当前子集是否合法// 检查所有冲突对for(inti0;im;i){// 如果子集中同时包含 a[i] 和 b[i] 这两个原料if((sa[i]1)(sb[i]1)){okfalse;// 非法退出检查break;}}if(ok)ans;// 合法则计数}coutansendl;return0;}功能分析算法原理暴力枚举 冲突检测。利用二进制位表示子集通过位运算快速判断某个元素是否在子集中。时间复杂度O ( 2 N ⋅ M ) O(2^N \cdot M)O(2N⋅M)当N 20 , M 400 N20, M400N20,M400时约为4 × 10 8 4 \times 10^84×108次检查实际运行在评测环境下可接受。空间复杂度O ( M ) O(M)O(M)仅存储冲突对。适用性N NN较小≤20时非常有效若N NN更大则需考虑其他方法如 DP、容斥等。边界情况M 0 M0M0无冲突答案为2 N 2^N2N。冲突对可能重复题目未说明但即使重复也不影响结果重复检查不影响正确性可优化去重但没必要。空集s 0 s0s0总是合法。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}