今天学习bitset简单涉及到一些背包问题和动态规划因为之前没接触过所以理解起来有难度一.首先先学习一下什么是bitsetbitset 是 C 标准库提供的固定长度二进制位容器。每一位只存 0 或者 1 极度省空间。普通 bool 占1字节bitset 1个位只占 1 bit1/8字节。1.常规操作bitset10 s; s[3] 1; // 把第3位设为1 s.set(5); // 第5位 1 s.reset(5); // 第5位 0 s.flip(2); // 第2位翻转0变11变0 s.count(); // 返回里面 1 的总个数超级常用O(n/w)极快 s.any(); // 是否存在1 s.none(); // 是否全02.最强特性支持按位运算 | ~ ^位运算速度极快一次运算同时处理几十/几千位这是 bitset 的核心优势。bitset10 a,b; auto c a b; // 按位与 auto c a | b; // 按位或 auto c a ^ b; // 按位异或 auto c ~a; // 按位取反3.例子网络一行最多2000列bitset2001 line[2001]; // 2001行每行2001位 // 想要把第5行 [3,8] 区间全部置1 for(int c3;c8;c) line[5][c]1;4.bitset硬性限制(1)大小必须是常量int m 2000; bitsetm s; // ❌ 编译报错不能是变量(2)不能动态扩容长度写死。对比 vector 是动态位容器速度慢于bitset。相关题目牛客NC276144和NC17193 acwing998和164详细解答1.牛客NC276144题意概括一共有 n 场比赛每场比赛有 m 道题目。必须从每场比赛恰好选出1道题把选出题目的难度相加。给定目标值 target 求总和与 target 的差值的最小绝对值。数据范围n ≤ 100 , m ≤ 20 每题分数 ≤ 50 总和最大 100 × 50 5000 。 n\le100,m\le20每题分数≤50总和最大 100\times505000。n≤100,m≤20每题分数≤50总和最大100×505000。解题步骤(动态规划)状态定义dp[s] 布尔值表示能否选出若干题目凑出总和 s 。初始状态 dp[0]true 不选任何比赛时总和为0。逐场处理比赛每一场比赛新建临时状态数组 ndp 防止同一场重复选多题遍历上一轮所有可达总和 s 枚举本场每道题分数 c 新总和 sc 标记为可达存入 ndp 。处理完成后用 ndp 更新 dp 。统计答案全部场次处理完毕后遍历所有可行总和 s 计算 abs(s-target) 记录最小值输出。代码#includebits/stdc.h using namespace std; #define endl \n; void solve(){ int n,m; cinnm; // dp[s] true 代表可以凑出难度总和 s vectorbool dp(5005,false); dp[0]true; // 初始状态还未选任何比赛总和0可达 // 依次处理 n 场比赛 for(int i0;in;i){ int a[m]; for(int j0;jm;j){ cina[j]; } // ndp临时数组保存处理完当前场次后的新可达总和 vectorbool ndp(5005,false); // 遍历上一轮所有可行总和 for(int s0;s5005;s){ if(dp[s]){ // 如果总和s能够凑出来 // 枚举本场可选的每一道题目 for(int c:a){ // 防止数组越界总和不超过5000 if(cs5000) ndp[cs]true; } } } // 将dp更新为本轮所有新的可达状态 dp.swap(ndp); } int target; cintarget; int miINT_MAX; // 记录最小差值初始无穷大 // 遍历所有可能总和寻找距离target最近的值 for(int s0;s5005;s){ if(dp[s]){ mimin(mi,abs(s-target)); } } coutmiendl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int t1; //cint; while(t--)solve(); }bitset优化版本#includebits/stdc.h using namespace std; #define endl \n; void solve(){ int n,m; cinnm; bitset5005dp; dp.set(0);//初始状态总和为0为真 for(int i0;in;i){ vectorinta(m); for(int j0;jm;j)cina[j]; bitset5005ndp;//ndp保存本轮新产生的所有可达和 for(int x:a){ // dp x把上一轮所有可行总和统一加上x // | 按位或把各个选项得到的状态全部合并 ndp |dpx; } dpndp;//更新dp为本轮所有可达状态 } int target ; cintarget; int miINT_MAX; //遍历所有可能的总和 for(int s0;s5005;s){ if(dp[s]){ mimin(mi,abs(s-target));//更新最新值 } } coutmiendl; } int main(){ int t1; //cint; while(t--)solve(); }2.牛客NC17193题目描述给定 n 组区间 ([l,r])。每一组必须恰好选一个数字 j(ljr)计算 (xj^2)。把所有选出数字的平方累加问一共能凑出多少种不同的总和。数据范围1 ≤ n , l , r ≤ 100解题步骤本质多重选择 01 背包dp[s] 1代表总和s可以被凑出来初始状态dp[0]1总和 0还没选任何数依次处理每组区间 ([l,r])新建空ndp保存本轮选完后的可达和遍历区间内每个 j代价 (xj^2)dp x把旧所有可达和全部加上 xndp | dpx把所有选择方案合并只要任意一种选择可达就标记为 1处理完所有区间后dp.count()统计有多少位是 1也就是不同总和数量代码#includebits/stdc.h using namespace std; #define endl \n // 预设最大可达总和上限 const int INF1e65; void solve(){ // dp[s] 1 表示可以凑出总和s bitsetINFdp; dp.set(0); // 初始总和0可达还未选取任何数字 int n; cinn; for(int i0;in;i){ int l,r; cinlr; // ndp 保存本轮选完数字后新的可达总和 bitsetINFndp; // 当前区间任选一个 j for(int jl;jr;j){ int xj*j; // 选取j贡献的值为j² // dp x原有所有可行总和全部加上x // | 合并所有可选方案只要有一种选择可行就标记为1 ndp | dp x; } // 更新dp为当前所有可行总和 dpndp; } // count()统计bitset中1的个数 不同总和的数量 coutdp.count()endl; } int main(){ int t1; //cint; while(t--)solve(); return 0; }3.acwing 998这道题对我来说难度是相当的大题目很好理解也很容易想到暴力做法但暴力只能够过30%的数据这时就该犯难了然后我在哔站上找到了相关题目的视频也是听了不下两遍才差不多弄懂了那种做法和为什么要这样做。链接题意概括有 n 次位运算AND / OR / XOR每次运算附带参数 t。你选择初始整数 x满足 (0 ≤ x ≤ m \boldsymbol{0 \le x \le m}0≤x≤m)。把 x 依次执行全部 n 个运算得到最终数值。求能得到的最大最终数值。核心性质位运算是按位独立运算二进制每一位互不干扰可以逐位贪心。解题步骤贪心顺序从高位 bit30 向下枚举到 bit0高位权重更大优先决定高位才能保证结果最大。对当前第 bit 位假设初始 x 这一位 1单独模拟所有运算算出运算后这一位结果ans1假设初始 x 这一位 0单独模拟所有运算算出运算后这一位结果ans0尝试能不能让初始这一位填 1条件①ans1 ans0填 1 能让最终结果更大条件②now | (1LL bit) ≤ m把这一位设 1 后整体初始数字不能超过上限 m两个条件同时成立初始 x 这一位选 1更新now最终答案这一位填ans1否则初始 x 这一位只能选 0最终答案这一位填ans0所有二进制位处理完毕输出答案。#includebits/stdc.h using namespace std; #define endl \n; typedef long long ll; // 存储每一扇防御门运算 参数 struct Node{ string op; int t; }; Node np[100005]; int n,m; // bit当前处理的二进制位 // s初始数字这一位的值只能是0或1 // 返回经过全部n次运算后这一位最终结果 int get(int bit ,int s){ int x s; for(int j0;jn;j){ // 取出当前运算参数t的第bit位0或者1 int d (np[j].t bit) 1; if(np[j].op AND) x d; else if(np[j].op OR) x | d; else x ^ d; // XOR } return x; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cinnm; for(int i0;in;i){ cinnp[i].opnp[i].t; } int now 0; // 正在构造的【初始攻击力x】 int ans 0; // 最终能得到的最大伤害 // 从最高位向低位贪心2^30足够覆盖1e9范围 for(int bit30;bit0;bit--){ int ans1 get(bit,1); // 初始这一位填1运算结果 int ans0 get(bit,0); // 初始这一位填0运算结果 // 重点括号不能省略|优先级低于1LL防止移位溢出 if(ans1 ans0 ( (now | (1LL bit)) m ) ){ ans | ans1 bit; now | (1LL bit); // 初始x这一位确定选1 } else{ ans | ans0 bit; // 初始x这一位只能选0 } } coutansendl; return 0; }4.acwing 164题意总结给定N 个点、M 条边的有向无环图DAG对每个节点u求出从u出发能够到达的节点总数包含自身。数据范围( 1 ≤ N , M ≤ 30000 ) (1\le N,M\le 30000)(1≤N,M≤30000)。暴力对每个点 BFS/DFS 复杂度 (O(N(NM)))会超时采用拓扑排序 bitset 优化 DP解决。做题步骤1建图读取 n、m构建邻接表统计每个节点入度。2.拓扑排序Kahn 算法利用队列不断取出入度为 0 的节点生成 DAG 的拓扑序列。拓扑序列性质所有边u→v在序列中 u 一定出现在 v 前面。3.反转拓扑序列遍历顺序变为后继节点先被处理前驱节点后处理。保证计算 u 的时候u 所有能直达的 v 的可达集合已经全部算好。4.DP bitset 合并可达集合初始每个节点只能到达自己f[u].set(u)转移u→vf[u] | f[v]把 v 能到达的所有点全部继承给 u5.统计输出f[i].count()得到节点 i 能到达的节点总数逐行输出。AC 代码#includebits/stdc.h using namespace std; #define endl \n const int MAXN 30005; vectorint g[MAXN]; // 邻接表g[u]存放u所有直接相连的后继节点 int in[MAXN]; // in[u]节点u的入度用于Kahn拓扑排序 bitsetMAXN f[MAXN]; // f[u] 二进制位集合 // 若f[u][v] 1代表节点u可以到达节点v vectorint tp; // tp 保存拓扑排序序列 int n, m; // n点数m边数 int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for(int i 1; i m; i){ int x, y; cin x y; g[x].push_back(y); // 添加有向边 x - y in[y]; // y节点入度 1 } queueint q; // 将初始入度为0的节点送入队列启动Kahn拓扑排序 for(int i 1; i n; i){ if(!in[i]) q.push(i); } // Kahn算法生成拓扑序列 while(!q.empty()){ int u q.front(); q.pop(); tp.push_back(u); // 弹出节点存入拓扑序列 // 遍历u所有出边后继节点入度-1 for(int v : g[u]){ if(--in[v] 0){ // 入度变为0加入队列 q.push(v); } } } reverse(tp.begin(), tp.end()); // 反转拓扑序列从终点向起点计算 // 逆拓扑序动态规划计算每个节点可达集合 for(int u : tp){ f[u].set(u); // 规则1节点一定可以到达自己对应位置置1 // u能走到v则u可以继承v所有能到达的节点 for(int v : g[u]){ f[u] | f[v]; // 按位或合并v的全部可达节点集合 } } // 依次输出1~n每个节点可达点数量 for(int i 1; i n; i){ cout f[i].count() endl; // count()统计bitset中1的个数 } return 0; }
bitset的简单介绍和应用
今天学习bitset简单涉及到一些背包问题和动态规划因为之前没接触过所以理解起来有难度一.首先先学习一下什么是bitsetbitset 是 C 标准库提供的固定长度二进制位容器。每一位只存 0 或者 1 极度省空间。普通 bool 占1字节bitset 1个位只占 1 bit1/8字节。1.常规操作bitset10 s; s[3] 1; // 把第3位设为1 s.set(5); // 第5位 1 s.reset(5); // 第5位 0 s.flip(2); // 第2位翻转0变11变0 s.count(); // 返回里面 1 的总个数超级常用O(n/w)极快 s.any(); // 是否存在1 s.none(); // 是否全02.最强特性支持按位运算 | ~ ^位运算速度极快一次运算同时处理几十/几千位这是 bitset 的核心优势。bitset10 a,b; auto c a b; // 按位与 auto c a | b; // 按位或 auto c a ^ b; // 按位异或 auto c ~a; // 按位取反3.例子网络一行最多2000列bitset2001 line[2001]; // 2001行每行2001位 // 想要把第5行 [3,8] 区间全部置1 for(int c3;c8;c) line[5][c]1;4.bitset硬性限制(1)大小必须是常量int m 2000; bitsetm s; // ❌ 编译报错不能是变量(2)不能动态扩容长度写死。对比 vector 是动态位容器速度慢于bitset。相关题目牛客NC276144和NC17193 acwing998和164详细解答1.牛客NC276144题意概括一共有 n 场比赛每场比赛有 m 道题目。必须从每场比赛恰好选出1道题把选出题目的难度相加。给定目标值 target 求总和与 target 的差值的最小绝对值。数据范围n ≤ 100 , m ≤ 20 每题分数 ≤ 50 总和最大 100 × 50 5000 。 n\le100,m\le20每题分数≤50总和最大 100\times505000。n≤100,m≤20每题分数≤50总和最大100×505000。解题步骤(动态规划)状态定义dp[s] 布尔值表示能否选出若干题目凑出总和 s 。初始状态 dp[0]true 不选任何比赛时总和为0。逐场处理比赛每一场比赛新建临时状态数组 ndp 防止同一场重复选多题遍历上一轮所有可达总和 s 枚举本场每道题分数 c 新总和 sc 标记为可达存入 ndp 。处理完成后用 ndp 更新 dp 。统计答案全部场次处理完毕后遍历所有可行总和 s 计算 abs(s-target) 记录最小值输出。代码#includebits/stdc.h using namespace std; #define endl \n; void solve(){ int n,m; cinnm; // dp[s] true 代表可以凑出难度总和 s vectorbool dp(5005,false); dp[0]true; // 初始状态还未选任何比赛总和0可达 // 依次处理 n 场比赛 for(int i0;in;i){ int a[m]; for(int j0;jm;j){ cina[j]; } // ndp临时数组保存处理完当前场次后的新可达总和 vectorbool ndp(5005,false); // 遍历上一轮所有可行总和 for(int s0;s5005;s){ if(dp[s]){ // 如果总和s能够凑出来 // 枚举本场可选的每一道题目 for(int c:a){ // 防止数组越界总和不超过5000 if(cs5000) ndp[cs]true; } } } // 将dp更新为本轮所有新的可达状态 dp.swap(ndp); } int target; cintarget; int miINT_MAX; // 记录最小差值初始无穷大 // 遍历所有可能总和寻找距离target最近的值 for(int s0;s5005;s){ if(dp[s]){ mimin(mi,abs(s-target)); } } coutmiendl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int t1; //cint; while(t--)solve(); }bitset优化版本#includebits/stdc.h using namespace std; #define endl \n; void solve(){ int n,m; cinnm; bitset5005dp; dp.set(0);//初始状态总和为0为真 for(int i0;in;i){ vectorinta(m); for(int j0;jm;j)cina[j]; bitset5005ndp;//ndp保存本轮新产生的所有可达和 for(int x:a){ // dp x把上一轮所有可行总和统一加上x // | 按位或把各个选项得到的状态全部合并 ndp |dpx; } dpndp;//更新dp为本轮所有可达状态 } int target ; cintarget; int miINT_MAX; //遍历所有可能的总和 for(int s0;s5005;s){ if(dp[s]){ mimin(mi,abs(s-target));//更新最新值 } } coutmiendl; } int main(){ int t1; //cint; while(t--)solve(); }2.牛客NC17193题目描述给定 n 组区间 ([l,r])。每一组必须恰好选一个数字 j(ljr)计算 (xj^2)。把所有选出数字的平方累加问一共能凑出多少种不同的总和。数据范围1 ≤ n , l , r ≤ 100解题步骤本质多重选择 01 背包dp[s] 1代表总和s可以被凑出来初始状态dp[0]1总和 0还没选任何数依次处理每组区间 ([l,r])新建空ndp保存本轮选完后的可达和遍历区间内每个 j代价 (xj^2)dp x把旧所有可达和全部加上 xndp | dpx把所有选择方案合并只要任意一种选择可达就标记为 1处理完所有区间后dp.count()统计有多少位是 1也就是不同总和数量代码#includebits/stdc.h using namespace std; #define endl \n // 预设最大可达总和上限 const int INF1e65; void solve(){ // dp[s] 1 表示可以凑出总和s bitsetINFdp; dp.set(0); // 初始总和0可达还未选取任何数字 int n; cinn; for(int i0;in;i){ int l,r; cinlr; // ndp 保存本轮选完数字后新的可达总和 bitsetINFndp; // 当前区间任选一个 j for(int jl;jr;j){ int xj*j; // 选取j贡献的值为j² // dp x原有所有可行总和全部加上x // | 合并所有可选方案只要有一种选择可行就标记为1 ndp | dp x; } // 更新dp为当前所有可行总和 dpndp; } // count()统计bitset中1的个数 不同总和的数量 coutdp.count()endl; } int main(){ int t1; //cint; while(t--)solve(); return 0; }3.acwing 998这道题对我来说难度是相当的大题目很好理解也很容易想到暴力做法但暴力只能够过30%的数据这时就该犯难了然后我在哔站上找到了相关题目的视频也是听了不下两遍才差不多弄懂了那种做法和为什么要这样做。链接题意概括有 n 次位运算AND / OR / XOR每次运算附带参数 t。你选择初始整数 x满足 (0 ≤ x ≤ m \boldsymbol{0 \le x \le m}0≤x≤m)。把 x 依次执行全部 n 个运算得到最终数值。求能得到的最大最终数值。核心性质位运算是按位独立运算二进制每一位互不干扰可以逐位贪心。解题步骤贪心顺序从高位 bit30 向下枚举到 bit0高位权重更大优先决定高位才能保证结果最大。对当前第 bit 位假设初始 x 这一位 1单独模拟所有运算算出运算后这一位结果ans1假设初始 x 这一位 0单独模拟所有运算算出运算后这一位结果ans0尝试能不能让初始这一位填 1条件①ans1 ans0填 1 能让最终结果更大条件②now | (1LL bit) ≤ m把这一位设 1 后整体初始数字不能超过上限 m两个条件同时成立初始 x 这一位选 1更新now最终答案这一位填ans1否则初始 x 这一位只能选 0最终答案这一位填ans0所有二进制位处理完毕输出答案。#includebits/stdc.h using namespace std; #define endl \n; typedef long long ll; // 存储每一扇防御门运算 参数 struct Node{ string op; int t; }; Node np[100005]; int n,m; // bit当前处理的二进制位 // s初始数字这一位的值只能是0或1 // 返回经过全部n次运算后这一位最终结果 int get(int bit ,int s){ int x s; for(int j0;jn;j){ // 取出当前运算参数t的第bit位0或者1 int d (np[j].t bit) 1; if(np[j].op AND) x d; else if(np[j].op OR) x | d; else x ^ d; // XOR } return x; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cinnm; for(int i0;in;i){ cinnp[i].opnp[i].t; } int now 0; // 正在构造的【初始攻击力x】 int ans 0; // 最终能得到的最大伤害 // 从最高位向低位贪心2^30足够覆盖1e9范围 for(int bit30;bit0;bit--){ int ans1 get(bit,1); // 初始这一位填1运算结果 int ans0 get(bit,0); // 初始这一位填0运算结果 // 重点括号不能省略|优先级低于1LL防止移位溢出 if(ans1 ans0 ( (now | (1LL bit)) m ) ){ ans | ans1 bit; now | (1LL bit); // 初始x这一位确定选1 } else{ ans | ans0 bit; // 初始x这一位只能选0 } } coutansendl; return 0; }4.acwing 164题意总结给定N 个点、M 条边的有向无环图DAG对每个节点u求出从u出发能够到达的节点总数包含自身。数据范围( 1 ≤ N , M ≤ 30000 ) (1\le N,M\le 30000)(1≤N,M≤30000)。暴力对每个点 BFS/DFS 复杂度 (O(N(NM)))会超时采用拓扑排序 bitset 优化 DP解决。做题步骤1建图读取 n、m构建邻接表统计每个节点入度。2.拓扑排序Kahn 算法利用队列不断取出入度为 0 的节点生成 DAG 的拓扑序列。拓扑序列性质所有边u→v在序列中 u 一定出现在 v 前面。3.反转拓扑序列遍历顺序变为后继节点先被处理前驱节点后处理。保证计算 u 的时候u 所有能直达的 v 的可达集合已经全部算好。4.DP bitset 合并可达集合初始每个节点只能到达自己f[u].set(u)转移u→vf[u] | f[v]把 v 能到达的所有点全部继承给 u5.统计输出f[i].count()得到节点 i 能到达的节点总数逐行输出。AC 代码#includebits/stdc.h using namespace std; #define endl \n const int MAXN 30005; vectorint g[MAXN]; // 邻接表g[u]存放u所有直接相连的后继节点 int in[MAXN]; // in[u]节点u的入度用于Kahn拓扑排序 bitsetMAXN f[MAXN]; // f[u] 二进制位集合 // 若f[u][v] 1代表节点u可以到达节点v vectorint tp; // tp 保存拓扑排序序列 int n, m; // n点数m边数 int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for(int i 1; i m; i){ int x, y; cin x y; g[x].push_back(y); // 添加有向边 x - y in[y]; // y节点入度 1 } queueint q; // 将初始入度为0的节点送入队列启动Kahn拓扑排序 for(int i 1; i n; i){ if(!in[i]) q.push(i); } // Kahn算法生成拓扑序列 while(!q.empty()){ int u q.front(); q.pop(); tp.push_back(u); // 弹出节点存入拓扑序列 // 遍历u所有出边后继节点入度-1 for(int v : g[u]){ if(--in[v] 0){ // 入度变为0加入队列 q.push(v); } } } reverse(tp.begin(), tp.end()); // 反转拓扑序列从终点向起点计算 // 逆拓扑序动态规划计算每个节点可达集合 for(int u : tp){ f[u].set(u); // 规则1节点一定可以到达自己对应位置置1 // u能走到v则u可以继承v所有能到达的节点 for(int v : g[u]){ f[u] | f[v]; // 按位或合并v的全部可达节点集合 } } // 依次输出1~n每个节点可达点数量 for(int i 1; i n; i){ cout f[i].count() endl; // count()统计bitset中1的个数 } return 0; }
