bitset的基本操作以及运用(有拓扑排序模版)日日夜夜自转的行星到处遮满别人的背影让风吹散混乱的呼吸快快清醒 yeyeye静静照亮原来的自己天空撒满忽然的光明眼中只有绚烂的天际再飞行基础本质bitset就是二进制位的集合。每一位bit只能是 0 或 1。形象比喻它像一个“开关阵列”每个开关占用的空间只有 1 个 bit而bool数组一个元素占 1 个字节是它的 8 倍。核心优势极其节省内存且支持位运算并行操作这是它强大的根源。创建#include bitset #include iostream using namespace std; int main() { // 1. 默认构造长度为8全部为0 bitset8 b1; // 00000000 // 2. 用整数初始化会把10转成二进制 bitset8 b2(10); // 00001010 // 3. 用二进制字符串初始化 bitset8 b3(1010); // 00001010 // 注意里的数字必须在编译期确定比如 const int N 100; return 0; }关键点bitset的长度必须是编译期常量。如果长度不确定请用vectorbool或动态bitset如 Boost 库我也不会用。操作假设我们定义bitset8 bs;常用操作如下操作代码说明设置某位为1bs.set(3);第3位从0开始变为1设置某位为0bs.reset(3);第3位变为0翻转某位bs.flip(3);0变11变0全部置1bs.set();所有位变1全部置0bs.reset();所有位变0全部翻转bs.flip();所有位取反访问某位bs[3]或bs.test(3)test会检查越界[]不会转为整数bs.to_ulong()/bs.to_ullong()注意别溢出转为字符串bs.to_string()返回00001010统计1的个数bs.count()时间复杂度 O(位数/字长)判断是否全0bs.any()/bs.none()any有1none全0位运算这是bitset的杀手锏。你可以直接把两个bitset做与、或、异或、取反、左移、右移这些操作是按位并行的效率极高。bitset8 a(10101010); bitset8 b(11110000); bitset8 c a b; // 10100000 按位与 bitset8 d a | b; // 11111010 按位或 bitset8 e a ^ b; // 01011010 按位异或 bitset8 f ~a; // 01010101 按位取反 bitset8 g a 2; // 10101000 左移2位低位补0实战应用如果你想判断一个数是不是 2 的幂可以x!0(x (x-1)) 0这用bitset做会非常快。基本的已经搞定那么上点实战小红组比赛题意理解你有很多场比赛n场每场比赛里有若干道题m道。现在你要从每一场比赛里各选一道题把它们的难度分数加起来得到一个总分。题目最后会给一个目标分数target。你要让这个总分尽可能地接近 target也就是让|总分 - target|最小。输出这个最小的差值。思路常规三层循环暴力直接超时死翘翘但我发现target的最大值是5000以及a i j a_{ij}aij的最大值是50。通过组合数求出每一个最后的难度分数总和需要非常多的这样操作是指数级别的我们想能不能变为线性级别的然后我们通过一个超级牛逼但我还没学过的方法状态压缩dp我没学过但看题解却能看出端倪这就是这个算法思想。其实常规组合数暴力三层循环给我的感觉就是一个dfs有超级多的分支然后你也不管不顾有多少重复的就是无脑生枝但状压dp给我的感觉就是你改用bfs遇到了一样的就合并就好像有一个剪枝的思想在里边。我们把dp设为可达的状态再用一个new_dp去更新我们的可达状态并把前边的可达状态去除因为我们只需要最后的答案状态具体看我代码。代码const int MAX5000; void solve() { int n,m; cin n m; vectorvectorinta(n1,vectorint(m1,0)); for(int i1;in;i) { for(int j1;jm;j) { cin a[i][j]; } } int target; cin target; vectorintdp(MAX1,0); dp[0]1; for(int i1;in;i) { vectorintnew_dp(MAX1,0);//更新状态用的dp for(int j1;jm;j) { int ta[i][j]; for(int k0;ktMAX;k) { if(dp[k])//说明这个地方时可达的所以它就有新的可达 { new_dp[kt]1; } } } dpnew_dp;//我们只需要最新的状态旧的拿去转转回收了 } int ansLLONG_MAX; for(int i1;iMAX;i) { if(dp[i]) ansmin(ans,abs(i-target)); } cout ans endl; }有点像是我们把数分为n层没下一层把上一层删了再对这一层进行一层的bfs而遇到相同的可达状态则会合并跟我们的多路归并有点相像他们的核心都是减少重复的计算。这题通过传统暴力想法发现最终可达答案状态可能有很多路径是多余冗杂的所以我们想办法剪枝优化做法。优化说了半天我发现我们今天的重点是bitset怎么跑去dp了所以我现在要说的利用bitset加速。vectorintdp(MAX1,0); dp[0]1; for(int i1;in;i) { vectorintnew_dp(MAX1,0);//更新状态用的dp for(int j1;jm;j) { int ta[i][j]; for(int k0;ktMAX;k) { if(dp[k])//说明这个地方时可达的所以它就有新的可达 { new_dp[kt]1; } } } dpnew_dp;//我们只需要最新的状态旧的拿去转转回收了 }这是我们的核心源代码bitsetMAX1 dp; // 把 vectorint 改成 bitset dp[0] 1; // 这个不用改用法一样 for(int i1;in;i) { bitsetMAX1 new_dp; // 把 vectorint 改成 bitset for(int j1;jm;j) { int ta[i][j]; new_dp | (dp t); // 把整个 k 循环替换成这一行 } dp new_dp; // 这个不用改用法一样 }而这是我们改为bitset的代码。一看就知道与我们的源代码是一个原理都是用来体现状态的。但是为何用bitset更好呢操作bool[]版bitset版每个 x 要做循环 5000 次判断并赋值一次位运算CPU 一次性处理 64 位或更多时间复杂度O(n × m × 5000) ≈ 1000万次O(n × m × (5000/64)) ≈ 100 × 20 × 79 ≈ 15.8万次位运算实际速度还行也能过极快远超需要bitset的移位操作底层是用 CPU 指令同时移动多个字word不是逐位移动的。所以它把 5000 次循环压缩成了约 80 次 CPU 位运算。简单瞎搞题题意理解一共有 n个数第 i 个数是x i x_ixix i x_ixi可以取[ l i , r i ] [l_i , r_i][li,ri]中任意的一个值。设S ∑ x i 2 S\sum{x_i^2}S∑xi2求 S 种类数。思路与上题一致啊这题可作为学会后的练手题只是代码有所差异罢了。代码const int MAX1000000; bitsetMAX1dp; dp[0]1; for(int i1;in;i) { bitsetMAX1new_dp; for(int ja[i][1];ja[i][2];j) { int tj*j; new_dp|(dpt); } dpnew_dp; } int ans0; ansdp.count();这是核心代码依旧这个思想在说下一题之前我们先学一下拓扑排序所以先引入一个模版题F-闯关游戏_河南萌新联赛2026第一场河南工业大学题意理解小豫借助AI开发了一款单机闯关游戏游戏共有n个关卡。为引导玩家循序渐进体验内容部分关卡设置了前置解锁规则只有通关指定的前置关卡后才能解锁并进入当前关卡。请你根据给出的前置规则判断玩家是否能够解锁并通关全部关卡。思路其实也没啥思路就是模版题目需要注意的是拓扑排序针对的是有向无环图所以只有当答案数量与关卡数量一致时才有答案不一致就是成环了。我们直接从代码去学习模版。代码void solve() { int n,m; cin n m; vectorvectorintg(n1);//用来记录每个节点后是什么节点 vectorintin(n1,0);//这个节点的入度为多少 for(int i1;im;i) { int u,v;//入节点跟出节点 cin u v; g[u].push_back(v);//u节点是v节点的前置条件 in[v];//出节点的入度1 } priority_queueint,vectorint,greaterintq;//因为要字典序最小且这个容器方便取与去答案 for(int i1;in;i) { if(in[i]0) { q.push(i);//先将入度为0的关卡用队列存入因为他们没有前置条件了 } } vectorintans;//答案存储使用 while(!q.empty()) { auto uq.top(); q.pop(); ans.push_back(u); for(int v:g[u]) { in[v]--;//相当于删掉了前置的一个条件那么入度就减少了 if(in[v]0) { q.push(v);//入度为0时就可以解锁关卡了进入后会自动排序可以保证字典序大小 } } } if((int)ans.size()n) { cout No endl; } else { cout Yes endl; for(int i0;in;i) { cout ans[i] ; } cout endl; } }ok了老铁们学会之后直接跟bitset兄弟一起。164. 可达性统计 - AcWing题库题意理解给定一张 N 个点 M 条边的有向无环图分别统计从每个点出发能够到达的点的数量。思路常规想法就是对每个点都进行一个dfs但根据数据量来看明显超时所以我们换种考虑角度我们发现前驱跟后继明显有一个重复问题如果后继可达的点前驱也能到达就像是1-2-3,我们的2可以到达2跟3那1也可以到达2和3所以我们考虑从后往前推。因为路径冗杂我们肯定不能一个个表示所以我们用状态压缩dp也就是我们上边第一道题所学的用bitset的每一位来表示可达的点。状态压缩DP的通用定义是用“二进制位”来表示一个集合把“集合的运算”转化为“整数的位运算”。代码bitset30005a[30005];//最多有30000个点和30000条边 void solve() { int n,m; cin n m; vectorvectorintg(n1); vectorintin(n1,0); for(int i1;im;i) { int x,y; cin x y; g[x].push_back(y); in[y]; } queueintq; vectorintans; ans.push_back(0); for(int i1;in;i) { if(in[i]0)q.push(i); } while(!q.empty()) { auto tq.front(); q.pop(); ans.push_back(t); for(auto v:g[t]) { in[v]--; if(in[v]0) { q.push(v); } } } for(int ians.size()-1;i1;i--) { int uans[i]; a[u].set(u);//自己可达自己 for(auto v:g[u])//这个点的所有后继 { a[u]|a[v];//因为后继可达的点它也可达 } } for(int i1;in;i) { cout a[i].count() endl; } }998. 起床困难综合症 - AcWing题库题意理解在给定的初始攻击力上限m内选一个整数x0 ≤ x ≤ m让它依次经过n个位运算AND、OR、XOR后得到的最终伤害值最大。输出这个最大的伤害值。思路首先我们知道以二进制来看每位无非俩种状态0和1所以我们可以通过判断每一位的数是0还是1来确定最后的伤害值所以我们开俩个bitset分别用来存0和1的情况,然后是我们的初始攻击力有个上限m所以我们的贪心策略应该是这个位为0时最后的结果是1那么就能最大化伤害值也不会影响初始攻击力选0这个位为1时最后的结果是1可以最大化伤害值同时这个位为1如果在m内才可以选代码void solve() { int n,m; cin n m; bitset40none,one; none.reset();//全变为0 one.set();//全变为1 for(int i0;in;i) { string op; cin op; int x; cin x; if(opAND) { nonex; onex; } else if(opOR) { none|x; one|x; } else { none^x; one^x; } } int ans0;//答案 int val0;//用来计算初始值 for(int i30;i0;i--)//看答案的范围决定 { if(none[i]1)ans(1i); else if(one[i]1val(1i)m) { val(1i); ans(1i); } } cout ans endl; }总结简单来说在这篇文章里bitset干了俩件事一个是二进制的按位计算一个是可行状态我们可以用每个位的0/1来表示并且我们可以把它当成一个集合对其进行一个位运算。
bitset的基本操作以及运用(有拓扑排序模版)日日夜夜自转的行星到处遮满别人的背影让风吹散混乱的呼吸快快清醒 yeyeye静静照亮原来的自己天空撒满忽然的光明眼中只有绚烂的天际再飞行基础本质bitset就是二进制位的集合。每一位bit只能是 0 或 1。形象比喻它像一个“开关阵列”每个开关占用的空间只有 1 个 bit而bool数组一个元素占 1 个字节是它的 8 倍。核心优势极其节省内存且支持位运算并行操作这是它强大的根源。创建#include bitset #include iostream using namespace std; int main() { // 1. 默认构造长度为8全部为0 bitset8 b1; // 00000000 // 2. 用整数初始化会把10转成二进制 bitset8 b2(10); // 00001010 // 3. 用二进制字符串初始化 bitset8 b3(1010); // 00001010 // 注意里的数字必须在编译期确定比如 const int N 100; return 0; }关键点bitset的长度必须是编译期常量。如果长度不确定请用vectorbool或动态bitset如 Boost 库我也不会用。操作假设我们定义bitset8 bs;常用操作如下操作代码说明设置某位为1bs.set(3);第3位从0开始变为1设置某位为0bs.reset(3);第3位变为0翻转某位bs.flip(3);0变11变0全部置1bs.set();所有位变1全部置0bs.reset();所有位变0全部翻转bs.flip();所有位取反访问某位bs[3]或bs.test(3)test会检查越界[]不会转为整数bs.to_ulong()/bs.to_ullong()注意别溢出转为字符串bs.to_string()返回00001010统计1的个数bs.count()时间复杂度 O(位数/字长)判断是否全0bs.any()/bs.none()any有1none全0位运算这是bitset的杀手锏。你可以直接把两个bitset做与、或、异或、取反、左移、右移这些操作是按位并行的效率极高。bitset8 a(10101010); bitset8 b(11110000); bitset8 c a b; // 10100000 按位与 bitset8 d a | b; // 11111010 按位或 bitset8 e a ^ b; // 01011010 按位异或 bitset8 f ~a; // 01010101 按位取反 bitset8 g a 2; // 10101000 左移2位低位补0实战应用如果你想判断一个数是不是 2 的幂可以x!0(x (x-1)) 0这用bitset做会非常快。基本的已经搞定那么上点实战小红组比赛题意理解你有很多场比赛n场每场比赛里有若干道题m道。现在你要从每一场比赛里各选一道题把它们的难度分数加起来得到一个总分。题目最后会给一个目标分数target。你要让这个总分尽可能地接近 target也就是让|总分 - target|最小。输出这个最小的差值。思路常规三层循环暴力直接超时死翘翘但我发现target的最大值是5000以及a i j a_{ij}aij的最大值是50。通过组合数求出每一个最后的难度分数总和需要非常多的这样操作是指数级别的我们想能不能变为线性级别的然后我们通过一个超级牛逼但我还没学过的方法状态压缩dp我没学过但看题解却能看出端倪这就是这个算法思想。其实常规组合数暴力三层循环给我的感觉就是一个dfs有超级多的分支然后你也不管不顾有多少重复的就是无脑生枝但状压dp给我的感觉就是你改用bfs遇到了一样的就合并就好像有一个剪枝的思想在里边。我们把dp设为可达的状态再用一个new_dp去更新我们的可达状态并把前边的可达状态去除因为我们只需要最后的答案状态具体看我代码。代码const int MAX5000; void solve() { int n,m; cin n m; vectorvectorinta(n1,vectorint(m1,0)); for(int i1;in;i) { for(int j1;jm;j) { cin a[i][j]; } } int target; cin target; vectorintdp(MAX1,0); dp[0]1; for(int i1;in;i) { vectorintnew_dp(MAX1,0);//更新状态用的dp for(int j1;jm;j) { int ta[i][j]; for(int k0;ktMAX;k) { if(dp[k])//说明这个地方时可达的所以它就有新的可达 { new_dp[kt]1; } } } dpnew_dp;//我们只需要最新的状态旧的拿去转转回收了 } int ansLLONG_MAX; for(int i1;iMAX;i) { if(dp[i]) ansmin(ans,abs(i-target)); } cout ans endl; }有点像是我们把数分为n层没下一层把上一层删了再对这一层进行一层的bfs而遇到相同的可达状态则会合并跟我们的多路归并有点相像他们的核心都是减少重复的计算。这题通过传统暴力想法发现最终可达答案状态可能有很多路径是多余冗杂的所以我们想办法剪枝优化做法。优化说了半天我发现我们今天的重点是bitset怎么跑去dp了所以我现在要说的利用bitset加速。vectorintdp(MAX1,0); dp[0]1; for(int i1;in;i) { vectorintnew_dp(MAX1,0);//更新状态用的dp for(int j1;jm;j) { int ta[i][j]; for(int k0;ktMAX;k) { if(dp[k])//说明这个地方时可达的所以它就有新的可达 { new_dp[kt]1; } } } dpnew_dp;//我们只需要最新的状态旧的拿去转转回收了 }这是我们的核心源代码bitsetMAX1 dp; // 把 vectorint 改成 bitset dp[0] 1; // 这个不用改用法一样 for(int i1;in;i) { bitsetMAX1 new_dp; // 把 vectorint 改成 bitset for(int j1;jm;j) { int ta[i][j]; new_dp | (dp t); // 把整个 k 循环替换成这一行 } dp new_dp; // 这个不用改用法一样 }而这是我们改为bitset的代码。一看就知道与我们的源代码是一个原理都是用来体现状态的。但是为何用bitset更好呢操作bool[]版bitset版每个 x 要做循环 5000 次判断并赋值一次位运算CPU 一次性处理 64 位或更多时间复杂度O(n × m × 5000) ≈ 1000万次O(n × m × (5000/64)) ≈ 100 × 20 × 79 ≈ 15.8万次位运算实际速度还行也能过极快远超需要bitset的移位操作底层是用 CPU 指令同时移动多个字word不是逐位移动的。所以它把 5000 次循环压缩成了约 80 次 CPU 位运算。简单瞎搞题题意理解一共有 n个数第 i 个数是x i x_ixix i x_ixi可以取[ l i , r i ] [l_i , r_i][li,ri]中任意的一个值。设S ∑ x i 2 S\sum{x_i^2}S∑xi2求 S 种类数。思路与上题一致啊这题可作为学会后的练手题只是代码有所差异罢了。代码const int MAX1000000; bitsetMAX1dp; dp[0]1; for(int i1;in;i) { bitsetMAX1new_dp; for(int ja[i][1];ja[i][2];j) { int tj*j; new_dp|(dpt); } dpnew_dp; } int ans0; ansdp.count();这是核心代码依旧这个思想在说下一题之前我们先学一下拓扑排序所以先引入一个模版题F-闯关游戏_河南萌新联赛2026第一场河南工业大学题意理解小豫借助AI开发了一款单机闯关游戏游戏共有n个关卡。为引导玩家循序渐进体验内容部分关卡设置了前置解锁规则只有通关指定的前置关卡后才能解锁并进入当前关卡。请你根据给出的前置规则判断玩家是否能够解锁并通关全部关卡。思路其实也没啥思路就是模版题目需要注意的是拓扑排序针对的是有向无环图所以只有当答案数量与关卡数量一致时才有答案不一致就是成环了。我们直接从代码去学习模版。代码void solve() { int n,m; cin n m; vectorvectorintg(n1);//用来记录每个节点后是什么节点 vectorintin(n1,0);//这个节点的入度为多少 for(int i1;im;i) { int u,v;//入节点跟出节点 cin u v; g[u].push_back(v);//u节点是v节点的前置条件 in[v];//出节点的入度1 } priority_queueint,vectorint,greaterintq;//因为要字典序最小且这个容器方便取与去答案 for(int i1;in;i) { if(in[i]0) { q.push(i);//先将入度为0的关卡用队列存入因为他们没有前置条件了 } } vectorintans;//答案存储使用 while(!q.empty()) { auto uq.top(); q.pop(); ans.push_back(u); for(int v:g[u]) { in[v]--;//相当于删掉了前置的一个条件那么入度就减少了 if(in[v]0) { q.push(v);//入度为0时就可以解锁关卡了进入后会自动排序可以保证字典序大小 } } } if((int)ans.size()n) { cout No endl; } else { cout Yes endl; for(int i0;in;i) { cout ans[i] ; } cout endl; } }ok了老铁们学会之后直接跟bitset兄弟一起。164. 可达性统计 - AcWing题库题意理解给定一张 N 个点 M 条边的有向无环图分别统计从每个点出发能够到达的点的数量。思路常规想法就是对每个点都进行一个dfs但根据数据量来看明显超时所以我们换种考虑角度我们发现前驱跟后继明显有一个重复问题如果后继可达的点前驱也能到达就像是1-2-3,我们的2可以到达2跟3那1也可以到达2和3所以我们考虑从后往前推。因为路径冗杂我们肯定不能一个个表示所以我们用状态压缩dp也就是我们上边第一道题所学的用bitset的每一位来表示可达的点。状态压缩DP的通用定义是用“二进制位”来表示一个集合把“集合的运算”转化为“整数的位运算”。代码bitset30005a[30005];//最多有30000个点和30000条边 void solve() { int n,m; cin n m; vectorvectorintg(n1); vectorintin(n1,0); for(int i1;im;i) { int x,y; cin x y; g[x].push_back(y); in[y]; } queueintq; vectorintans; ans.push_back(0); for(int i1;in;i) { if(in[i]0)q.push(i); } while(!q.empty()) { auto tq.front(); q.pop(); ans.push_back(t); for(auto v:g[t]) { in[v]--; if(in[v]0) { q.push(v); } } } for(int ians.size()-1;i1;i--) { int uans[i]; a[u].set(u);//自己可达自己 for(auto v:g[u])//这个点的所有后继 { a[u]|a[v];//因为后继可达的点它也可达 } } for(int i1;in;i) { cout a[i].count() endl; } }998. 起床困难综合症 - AcWing题库题意理解在给定的初始攻击力上限m内选一个整数x0 ≤ x ≤ m让它依次经过n个位运算AND、OR、XOR后得到的最终伤害值最大。输出这个最大的伤害值。思路首先我们知道以二进制来看每位无非俩种状态0和1所以我们可以通过判断每一位的数是0还是1来确定最后的伤害值所以我们开俩个bitset分别用来存0和1的情况,然后是我们的初始攻击力有个上限m所以我们的贪心策略应该是这个位为0时最后的结果是1那么就能最大化伤害值也不会影响初始攻击力选0这个位为1时最后的结果是1可以最大化伤害值同时这个位为1如果在m内才可以选代码void solve() { int n,m; cin n m; bitset40none,one; none.reset();//全变为0 one.set();//全变为1 for(int i0;in;i) { string op; cin op; int x; cin x; if(opAND) { nonex; onex; } else if(opOR) { none|x; one|x; } else { none^x; one^x; } } int ans0;//答案 int val0;//用来计算初始值 for(int i30;i0;i--)//看答案的范围决定 { if(none[i]1)ans(1i); else if(one[i]1val(1i)m) { val(1i); ans(1i); } } cout ans endl; }总结简单来说在这篇文章里bitset干了俩件事一个是二进制的按位计算一个是可行状态我们可以用每个位的0/1来表示并且我们可以把它当成一个集合对其进行一个位运算。
