bitset基本操作+运用（内含拓扑排序）

bitset的基本操作以及运用(有拓扑排序模版)

日日夜夜自转的行星
到处遮满别人的背影
让风吹散混乱的呼吸
快快清醒 yeyeye
静静照亮原来的自己
天空撒满忽然的光明
眼中只有绚烂的天际
再飞行

基础：

• 本质：bitset就是二进制位的集合。每一位（bit）只能是 0 或 1。
• 形象比喻：它像一个“开关阵列”，每个开关占用的空间只有 1 个 bit（而bool数组一个元素占 1 个字节，是它的 8 倍）。
• 核心优势：极其节省内存，且支持位运算并行操作（这是它强大的根源）。

创建：

#include <bitset> #include <iostream> using namespace std; int main() { // 1. 默认构造：长度为8，全部为0 bitset<8> b1; // 00000000 // 2. 用整数初始化：会把10转成二进制 bitset<8> b2(10); // 00001010 // 3. 用二进制字符串初始化 bitset<8> b3("1010"); // 00001010 // 注意：<>里的数字必须在编译期确定，比如 const int N = 100; return 0; }

关键点：bitset的长度必须是编译期常量。如果长度不确定，请用vector<bool>或动态bitset（如 Boost 库，我也不会用）。

操作：

假设我们定义bitset<8> bs;，常用操作如下：

位运算：

这是bitset的杀手锏。你可以直接把两个bitset做与、或、异或、取反、左移、右移，这些操作是按位并行的，效率极高。

bitset<8> a("10101010"); bitset<8> b("11110000"); bitset<8> c = a & b; // 10100000 （按位与） bitset<8> d = a | b; // 11111010 （按位或） bitset<8> e = a ^ b; // 01011010 （按位异或） bitset<8> f = ~a; // 01010101 （按位取反） bitset<8> 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 MAX=5000; void solve() { int n,m; cin >> n >> m; vector<vector<int>>a(n+1,vector<int>(m+1,0)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin >> a[i][j]; } } int target; cin >> target; vector<int>dp(MAX+1,0); dp[0]=1; for(int i=1;i<=n;i++) { vector<int>new_dp(MAX+1,0);//更新状态用的dp for(int j=1;j<=m;j++) { int t=a[i][j]; for(int k=0;k+t<=MAX;k++) { if(dp[k])//说明这个地方时可达的，所以它就有新的可达 { new_dp[k+t]=1; } } } dp=new_dp;//我们只需要最新的状态，旧的拿去转转回收了 } int ans=LLONG_MAX; for(int i=1;i<=MAX;i++) { if(dp[i]) ans=min(ans,abs(i-target)); } cout << ans << endl; }

有点像是我们把数分为n层，没下一层把上一层删了再对这一层进行一层的bfs，而遇到相同的可达状态则会合并，跟我们的多路归并有点相像，他们的核心都是减少重复的计算。

这题通过传统暴力想法，发现最终可达答案状态可能有很多路径是多余冗杂的，所以我们想办法剪枝优化做法。

优化：

说了半天我发现我们今天的重点是bitset怎么跑去dp了？

所以我现在要说的利用bitset加速。

vector<int>dp(MAX+1,0); dp[0]=1; for(int i=1;i<=n;i++) { vector<int>new_dp(MAX+1,0);//更新状态用的dp for(int j=1;j<=m;j++) { int t=a[i][j]; for(int k=0;k+t<=MAX;k++) { if(dp[k])//说明这个地方时可达的，所以它就有新的可达 { new_dp[k+t]=1; } } } dp=new_dp;//我们只需要最新的状态，旧的拿去转转回收了 }

这是我们的核心源代码

bitset<MAX+1> dp; // 把 vector<int> 改成 bitset dp[0] = 1; // 这个不用改，用法一样 for(int i=1;i<=n;i++) { bitset<MAX+1> new_dp; // 把 vector<int> 改成 bitset for(int j=1;j<=m;j++) { int t=a[i][j]; new_dp |= (dp << t); // 把整个 k 循环替换成这一行 } dp = new_dp; // 这个不用改，用法一样 }

而这是我们改为bitset的代码。一看就知道与我们的源代码是一个原理都是用来体现状态的。但是为何用bitset更好呢？

bitset的移位操作，底层是用 CPU 指令同时移动多个字（word），不是逐位移动的。所以它把 5000 次循环，压缩成了约 80 次 CPU 位运算。

简单瞎搞题

题意理解：

一共有 n个数，第 i 个数是x i x_ixi​

x 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 MAX=1000000; bitset<MAX+1>dp; dp[0]=1; for(int i=1;i<=n;i++) { bitset<MAX+1>new_dp; for(int j=a[i][1];j<=a[i][2];j++) { int t=j*j; new_dp|=(dp<<t); } dp=new_dp; } int ans=0; ans=dp.count();

这是核心代码，依旧这个思想

在说下一题之前我们先学一下拓扑排序，所以先引入一个模版题

F-闯关游戏_河南萌新联赛2026第（一）场：河南工业大学

题意理解：

小豫借助AI开发了一款单机闯关游戏，游戏共有n个关卡。为引导玩家循序渐进体验内容，部分关卡设置了前置解锁规则：只有通关指定的前置关卡后，才能解锁并进入当前关卡。请你根据给出的前置规则，判断玩家是否能够解锁并通关全部关卡。

思路：

其实也没啥思路就是模版题目，需要注意的是拓扑排序针对的是有向无环图所以只有当答案数量与关卡数量一致时才有答案，不一致就是成环了。我们直接从代码去学习模版。

代码：

void solve() { int n,m; cin >> n >> m; vector<vector<int>>g(n+1);//用来记录每个节点后是什么节点 vector<int>in(n+1,0);//这个节点的入度为多少 for(int i=1;i<=m;i++) { int u,v;//入节点跟出节点 cin >> u >> v; g[u].push_back(v);//u节点是v节点的前置条件 in[v]++;//出节点的入度+1 } priority_queue<int,vector<int>,greater<int>>q;//因为要字典序最小，且这个容器方便取与去答案 for(int i=1;i<=n;i++) { if(in[i]==0) { q.push(i);//先将入度为0的关卡用队列存入，因为他们没有前置条件了 } } vector<int>ans;//答案存储使用 while(!q.empty()) { auto u=q.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 i=0;i<n;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的通用定义是用“二进制位”来表示一个集合，把“集合的运算”转化为“整数的位运算”。

代码：

bitset<30005>a[30005];//最多有30000个点和30000条边 void solve() { int n,m; cin >> n >> m; vector<vector<int>>g(n+1); vector<int>in(n+1,0); for(int i=1;i<=m;i++) { int x,y; cin >> x >> y; g[x].push_back(y); in[y]++; } queue<int>q; vector<int>ans; ans.push_back(0); for(int i=1;i<=n;i++) { if(in[i]==0)q.push(i); } while(!q.empty()) { auto t=q.front(); q.pop(); ans.push_back(t); for(auto v:g[t]) { in[v]--; if(in[v]==0) { q.push(v); } } } for(int i=ans.size()-1;i>=1;i--) { int u=ans[i]; a[u].set(u);//自己可达自己 for(auto v:g[u])//这个点的所有后继 { a[u]|=a[v];//因为后继可达的点它也可达 } } for(int i=1;i<=n;i++) { cout << a[i].count() << endl; } }

998. 起床困难综合症 - AcWing题库

题意理解：

在给定的初始攻击力上限m内，选一个整数x（0 ≤ 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; bitset<40>none,one; none.reset();//全变为0 one.set();//全变为1 for(int i=0;i<n;i++) { string op; cin >> op; int x; cin >> x; if(op=="AND") { none&=x; one&=x; } else if(op=="OR") { none|=x; one|=x; } else { none^=x; one^=x; } } int ans=0;//答案 int val=0;//用来计算初始值 for(int i=30;i>=0;i--)//看答案的范围决定 { if(none[i]==1)ans+=(1<<i); else if(one[i]==1&&val+(1<<i)<=m) { val+=(1<<i); ans+=(1<<i); } } cout << ans << endl; }

总结

简单来说在这篇文章里bitset干了俩件事一个是二进制的按位计算，一个是可行状态我们可以用每个位的0/1来表示，并且我们可以把它当成一个集合对其进行一个位运算。