文章目录C 位运算 bitset1.位运算1.1基础位运算符2. bitset2.1存储特点2.2常用函数2.2.1 01‑bitset 背包核心模板2.2.2 遍历所有为 1 的位3.例题3.1小红组比赛3.1.1 解题过程3.1.2 实现代码DP解法bitset优化3.2简单瞎搞题3.2.1 解题过程3.2.2 实现代码3.3 起床困难综合症3.3.1 解题过程3.3.2 实现代码直接暴力按位贪心最优解法3.4 可达性统计3.4.1 解题过程3.4.2 实现代码C 位运算 bitset1.位运算1.1基础位运算符运算符名称核心作用集合含义按位与全 1 才为 1筛选、清零交集按位或有 1 就为 1置 1^按位异或不同为 1相同为 0翻转对称差集~按位取反0、1 全部翻转取补多用于造掩码左移整体左移低位补 0等价×2k集合全部元素加上偏移量右移整体右移等价÷2k集合全部元素减去偏移量x y; x | y; x ^ y; x k; x k;// 第k位置1 x | 1LL k; // 第k位清零 x ~(1LL k); // 翻转第k位 x ^ 1LL k; // 判断第k位是否为1 if(x (1LL k)){} // lowbit拿到数字二进制最右边的那个 1 lb x (-x);2. bitsetbitset是 CSTL 提供的位集合容器把每一个布尔信息压缩到1 个 bit存储。普通int/long long最多只有 64 位而bitset可以开到上千、上万位完整支持全套位运算在竞赛中用来加速背包 DP、集合运算、状态压缩、传递闭包。bitset 本质把 vector换成位集合位运算一次性批量转移大幅提速基础定义与特性bitsetN bs;N总位数必须是编译期常量字面量 /const 常量绝对不能是普通 int 变量bitset1000 a; // 正确 const int M 2000; bitsetM b; // 正确 int n; cin n; bitsetn c; // 编译报错n是运行时变量2.1存储特点1 位 (bit) 保存 1 个布尔bitset1024只占用 128 字节。下标规则下标 0 代表最低位。bs[0]最低位bs[N‑1]最高位。2.2常用函数常用函数作用bs.set(pos)把第 pos 位置 1bs.reset(pos)把第 pos 位置 0bs.flip(pos)翻转第 pos 位0 变 11 变 0bs.test(pos)判断第 pos 位是否为 1返回 bool推荐用bs.set()全部位设为 1bs.reset()全部位清零bs.count()统计里面等于 1 的位的个数高频bs.any()是否至少有一个 1bs.none()是否全部是 0bs.to_string()转二进制字符串方便调试输出简单示例bitset10 bs; bs.set(2); //第2位变成1 bs.set(5); cout bs.count();//输出2 bs.reset(2); bs.flip(5); if(bs.test(5)){ //判断第5位是否为1 } cout bs.to_string();关于bitset与位运算a | b; //并集合并 a b; //交集 a ^ b; //对称差集 a w; //整体左移w位集合所有元素 w背包核心 a w; //整体右移w位 a | b;2.2.1 01‑bitset 背包核心模板const int MAX2005; bitsetMAX dp; dp.reset(); dp.set(0); for(每个物品体积w){ dp | dp w; } //dp.test(x) 判断体积x能否凑出2.2.2 遍历所有为 1 的位for(int i0;idp.size();i){ if(dp.test(i)){ //i为集合中的元素 } }3.例题3.1小红组比赛小红组比赛每组数字最多 20 个n 最多 100每个数字≤50总和最大 (100*505000)。3.1.1 解题过程状态定义dp[s]true代表可以选出若干组数字凑出总和 sfalse代表凑不出。初始状态还没有选任何一组的时候总和只能是 0所以dp[0] true其余全部 false转移逻辑我们一组一组处理。假设现在处理第 i组重点不能直接在原来的 dp 数组上修改我们创建一个全新数组 ndp用来存放处理完当前组之后新的可达总和。规则对于所有之前能凑出的总和 s遍历本组每一个数字 x那么新总和 s x一定可以凑出来 -- ndp[s x] true也就是说 之前选若干组凑出 s本组选数字 x合起来总和 sx。每组必须选一个旧的 s 不能直接保留全部要加上本组数字所以必须新开 ndp。处理完当前组后让dp ndp继续下一组全部 n 组处理完毕遍历所有s只要dp[s]true计算abs(s-target)找出最小值3.1.2 实现代码DP解法//原DP #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n; ll m; int main() { IOS cinnm; vectorvectorll a(n,vectorll(m)); for(ll i0;in;i) { for(ll j0;jm;j) { cina[i][j]; } } ll t; cint; vectorbool dp(5005,false); dp[0]true; for(ll i0;in;i) { vectorboolndp(5005,false); for(ll s0;s5000;s) { if(dp[s]) { for(ll x:a[i]) { if(sx5000) { ndp[sx]true; } } } } dp.swap(ndp); } ll ansLLONG_MAX; for(ll s0;s5000;s) { if(dp[s]) { ansmin(ans,abs(s-t)); } } coutansendl; // coutfixedsetprecision(x) ; return 0; }if(dp[s]) { for(ll x:a[i]) { if(sx5000) { ndp[sx]true; } } }bitset优化for(ll x:a[i]) { ndp|dpx; }bitset优化//bitset优化 #includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n; ll m; int main() { IOS cinnm; vectorvectorll a(n,vectorll(m)); for(ll i0;in;i) { for(ll j0;jm;j) { cina[i][j]; } } ll t; cint; bitset5001dp; dp.reset();//全部位清零初始所有总和都不可行 dp.set(0);//第0位置 1 for(ll i0;in;i) { bitset5001ndp; for(ll x:a[i]) { ndp|dpx; } dpndp; } ll ansLLONG_MAX; for(ll s0;s5000;s) { if(dp.test(s)) { ansmin(ans,abs(s-t)); } } coutansendl; // coutfixedsetprecision(x) ; return 0; }3.2简单瞎搞题简单瞎搞题3.2.1 解题过程与前一题类似 直接bitset优化更好 写每个 (x_i) 在给定区间任选一个数把每个数的平方累加问最终能得到多少种不一样的总和。属于可行性背包 DP只记录某个总和能不能凑出来不记录方案数。DP 状态定义使用bitset做状态压缩(dp[s]1)代表处理完前面若干组之后可以凑出平方和 s。(dp[s]0)代表平方和 s 无法凑出。初始状态dp.set(0)不选任何数平方和为 0。状态转移处理第 i 组可选 [l,r]每组可以选任意一个 j贡献值为 j2。dp (j*j)把所有已经可达的平方和全部加上 j2代表本组选择 j。ndp | dp (j*j)按位或做集合合并把区间内每一个 j 的所有新状态全部合并到ndp。本组处理完毕令dp ndp继续处理下一组。ndp用来保存处理完当前组之后所有可达的平方和。dp.count()统计 bitset 中值为 1 的位的个数就是不同 S 的总数量。核心 bitset 原理dp k集合内部所有元素统一加上 k。|集合合并把多种选择产生的全部状态合并在一起。3.2.2 实现代码#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; const int MAX1000005; using namespace std; ll n; int main() { IOS cinn; ll l,r; bitsetMAXdp,ndp; dp.set(0); for(ll i1;in;i) { cinlr; ndp.reset(); for(ll jl;jr;j) { ndp|dp(j*j); } dpndp; } coutdp.count()endl; // coutfixedsetprecision(x) ; return 0; }3.3 起床困难综合症998. 起床困难综合症 - AcWing题库3.3.1 解题过程本来 尝试了尝试 直接暴力 毫无疑问 超时了只能是按位贪心核心原理AND / OR / XOR属于按位运算各个二进制位之间互相独立。某一位最终结果只和初始数 v 的这一位是 0 还是 1 有关。因此可以逐位决策从高位到低位优先争取答案该位等于 1。calc (bit, now) 函数作用只模拟单独一个二进制 bit 位经过全部 n 次门运算之后输出的值。参数bit当前正在处理的二进制位编号now初始攻击力 v 在该 bit 上的值只能传入 0 或者 1返回值经过全部运算之后该位输出结果0 / 1ll calc(ll bit,ll now){ for(ll i 0; i n; i) { ll x a[i].second bit 1; //取出运算参数t的第bit位 if(a[i].first OR) now | x; else if(a[i].first XOR) now ^ x; else // AND now x; } return now; }r1 calc(i,0)若初始 v 的第 i 位填 0运算结束后该位得到的值r2 calc(i,1)若初始 v 的第 i 位填 1运算结束后该位得到的值v我们正在构造的初始攻击力全程满足 (v \le m)ans保存经过全部运算之后的最大伤害结果ll r1 calc(i, 0); ll r2 calc(i, 1); //条件1v把此位设1后不能超过m条件2填1比填0收益更大 if(v (1LL i) m r2 r1) { v (1LL i); //初始v这一位置1 ans r2 i; //答案累加该位贡献 } else { ans r1 i; //初始v这一位只能选0 }3.3.2 实现代码直接暴力直接暴力的方法 不行 会超 m 很小才能通过m 大直接 TLE#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; ll n; string op; ll m; ll t; int main() { IOS cinnm; vectorllh(m1); for(ll i0;im;i) { h[i]i; } for(ll i1;in;i) { cinopt; for(ll j0;jm;j) { if(opAND) { h[j]h[j]t; } if(opOR) { h[j]h[j]|t; } if(opXOR) { h[j]h[j]^t; } } } ll ans0; for(ll i0;im;i) { ansmax(ans,h[i]); } coutansendl; // coutfixedsetprecision(x) ; return 0; }按位贪心最优解法#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; const int N 1e510; pairstring, ll a[N]; ll n, m; ll calc(ll bit,ll now){ for(ll i 0; i n; i) { ll x a[i].second bit 1; if(a[i].first OR) now | x; else if(a[i].first XOR) now ^ x; else now x; } return now; } int main(){ cin n m; for(ll i 0; i n; i) cin a[i].first a[i].second; ll ans 0, v 0; for(ll i 60; i 0; i--){ ll r1 calc(i, 0); ll r2 calc(i, 1); if(v (1LLi) m r2 r1) v (1LL i), ans r2 i; else ans r1 i; } cout ans endl; return 0; }3.4 可达性统计164. 可达性统计 - AcWing题库给定一个有向无环图 (DAG)共 n 个点m 条边。对每个节点 u求从 u 出发可以到达多少个节点包含自己。普通 DFS每个点跑一遍 DFS会超时。利用拓扑序逆序 bitset做集合合并3.4.1 解题过程拓扑 反转 bitset 合并DAG 可以拓扑排序拓扑序反转 先算后继再算前驱bitset做集合合并a | b把 b 的所有可达点合并到 aDAG求可达性 直接用拓扑排序3.4.2 实现代码#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; const ll maxn30005; using namespace std; ll n,m; vectorllg[maxn]; ll deg[maxn]; vectorlltopo; bitsetmaxnreach[maxn]; void toposort() { queuellq; for(ll i1;in;i) { if(deg[i]0) { q.push(i); } } while(!q.empty()) { ll uq.front(); q.pop(); topo.push_back(u); for(ll v:g[u]) { deg[v]--; if(deg[v]0) { q.push(v); } } } } int main(){ IOS cinnm; for(ll i0;im;i) { ll x,y; cinxy; g[x].push_back(y); deg[y]; } toposort(); reverse(topo.begin(),topo.end()); for(ll u:topo) { reach[u].set(u); for(ll v:g[u]) { reach[u]|reach[v]; } } for(ll i1;in;i) { coutreach[i].count()endl; } return 0; }