企业官网建设流程全解析

今天学习bitset，简单涉及到一些背包问题和动态规划，因为之前没接触过，所以理解起来有难度

一.首先先学习一下什么是bitset

bitset 是 C++ 标准库提供的固定长度二进制位容器。每一位只存 0 或者 1 ，极度省空间。普通 bool 占1字节；bitset 1个位只占 1 bit（1/8字节）。

1.常规操作

bitset<10> s; s[3] = 1; // 把第3位设为1 s.set(5); // 第5位 = 1 s.reset(5); // 第5位 = 0 s.flip(2); // 第2位翻转（0变1，1变0） s.count(); // 返回里面 1 的总个数（超级常用！O(n/w)极快） s.any(); // 是否存在1 s.none(); // 是否全0

2.最强特性：支持按位运算（& | ~ ^）

位运算速度极快，一次运算同时处理几十/几千位，这是 bitset 的核心优势。

bitset<10> a,b; auto c = a & b; // 按位与 auto c = a | b; // 按位或 auto c = a ^ b; // 按位异或 auto c = ~a; // 按位取反

3.例子：

网络一行最多2000列

bitset<2001> line[2001]; // 2001行，每行2001位 // 想要把第5行 [3,8] 区间全部置1 for(int c=3;c<=8;c++) line[5][c]=1;

4.bitset硬性限制

(1)大小必须是常量

int m = 2000; bitset<m> 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\times50=5000。n≤100,m≤20，每题分数≤50，总和最大100×50=5000。

解题步骤(动态规划)：

1. 状态定义

   dp[s] ：布尔值，表示能否选出若干题目凑出总和 s 。

   初始状态： dp[0]=true ，不选任何比赛时总和为0。

2. 逐场处理比赛

每一场比赛新建临时状态数组 ndp （防止同一场重复选多题）：

• 遍历上一轮所有可达总和 s ；

• 枚举本场每道题分数 c ；

• 新总和 s+c 标记为可达，存入 ndp 。

  处理完成后，用 ndp 更新 dp 。

3. 统计答案

全部场次处理完毕后，遍历所有可行总和 s ，计算 abs(s-target) ，记录最小值输出。

代码：

#include<bits/stdc++.h> using namespace std; #define endl '\n'; void solve(){ int n,m; cin>>n>>m; // dp[s] = true 代表可以凑出难度总和 s vector<bool> dp(5005,false); dp[0]=true; // 初始状态：还未选任何比赛，总和0可达 // 依次处理 n 场比赛 for(int i=0;i<n;i++){ int a[m]; for(int j=0;j<m;j++){ cin>>a[j]; } // ndp：临时数组，保存处理完当前场次后的新可达总和 vector<bool> ndp(5005,false); // 遍历上一轮所有可行总和 for(int s=0;s<5005;s++){ if(dp[s]){ // 如果总和s能够凑出来 // 枚举本场可选的每一道题目 for(int c:a){ // 防止数组越界，总和不超过5000 if(c+s<=5000) ndp[c+s]=true; } } } // 将dp更新为本轮所有新的可达状态 dp.swap(ndp); } int target; cin>>target; int mi=INT_MAX; // 记录最小差值，初始无穷大 // 遍历所有可能总和，寻找距离target最近的值 for(int s=0;s<5005;s++){ if(dp[s]){ mi=min(mi,abs(s-target)); } } cout<<mi<<endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int t=1; //cin>>t; while(t--)solve(); }

bitset优化版本：

#include<bits/stdc++.h> using namespace std; #define endl '\n'; void solve(){ int n,m; cin>>n>>m; bitset<5005>dp; dp.set(0);//初始状态，总和为0为真 for(int i=0;i<n;i++){ vector<int>a(m); for(int j=0;j<m;j++)cin>>a[j]; bitset<5005>ndp;//ndp保存本轮新产生的所有可达和 for(int x:a){ // dp << x：把上一轮所有可行总和统一加上x // |= 按位或，把各个选项得到的状态全部合并 ndp |=dp<<x; } dp=ndp;//更新dp为本轮所有可达状态 } int target ; cin>>target; int mi=INT_MAX; //遍历所有可能的总和 for(int s=0;s<5005;s++){ if(dp[s]){ mi=min(mi,abs(s-target));//更新最新值 } } cout<<mi<<endl; } int main(){ int t=1; //cin>>t; while(t--)solve(); }

2.牛客NC17193

题目描述：

给定 n 组区间 ([l,r])。

每一组必须恰好选一个数字 j(l<=j<=r)，计算 (x=j^2)。

把所有选出数字的平方累加，问：一共能凑出多少种不同的总和。

数据范围：1 ≤ n , l , r ≤ 100

解题步骤：

本质：多重选择 01 背包

1. dp[s] = 1：代表总和s可以被凑出来

2. 初始状态：dp[0]=1，总和 0（还没选任何数）

3. 依次处理每组区间 ([l,r])：

   • 新建空ndp，保存本轮选完后的可达和
   • 遍历区间内每个 j，代价 (x=j^2)
   • dp << x：把旧所有可达和全部加上 x
   • ndp |= dp<<x：把所有选择方案合并（只要任意一种选择可达，就标记为 1）

4. 处理完所有区间后，dp.count()统计有多少位是 1，也就是不同总和数量

   代码：

#include<bits/stdc++.h> using namespace std; #define endl '\n' // 预设最大可达总和上限 const int INF=1e6+5; void solve(){ // dp[s] = 1 表示可以凑出总和s bitset<INF>dp; dp.set(0); // 初始：总和0可达（还未选取任何数字） int n; cin>>n; for(int i=0;i<n;i++){ int l,r; cin>>l>>r; // ndp 保存本轮选完数字后新的可达总和 bitset<INF>ndp; // 当前区间任选一个 j for(int j=l;j<=r;j++){ int x=j*j; // 选取j，贡献的值为j² // dp << x：原有所有可行总和全部加上x // |= 合并所有可选方案（只要有一种选择可行，就标记为1） ndp |= dp << x; } // 更新dp为当前所有可行总和 dp=ndp; } // count()统计bitset中1的个数 = 不同总和的数量 cout<<dp.count()<<endl; } int main(){ int t=1; //cin>>t; 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 个运算，得到最终数值。

求：能得到的最大最终数值。

核心性质：位运算是按位独立运算，二进制每一位互不干扰，可以逐位贪心。

解题步骤

1. 贪心顺序：从高位 bit=30 向下枚举到 bit=0

   高位权重更大，优先决定高位才能保证结果最大。

2. 对当前第 bit 位：

   • 假设初始 x 这一位 = 1，单独模拟所有运算，算出运算后这一位结果ans1
   • 假设初始 x 这一位 = 0，单独模拟所有运算，算出运算后这一位结果ans0

3. 尝试能不能让初始这一位填 1：

   条件①：ans1 > ans0：填 1 能让最终结果更大

   条件②：now | (1LL << bit) ≤ m：把这一位设 1 后，整体初始数字不能超过上限 m

4. 两个条件同时成立：初始 x 这一位选 1，更新now，最终答案这一位填ans1

5. 否则：初始 x 这一位只能选 0，最终答案这一位填ans0

6. 所有二进制位处理完毕，输出答案。

#include<bits/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 j=0;j<n;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); cin>>n>>m; for(int i=0;i<n;i++){ cin>>np[i].op>>np[i].t; } int now = 0; // 正在构造的【初始攻击力x】 int ans = 0; // 最终能得到的最大伤害 // 从最高位向低位贪心，2^30足够覆盖1e9范围 for(int bit=30;bit>=0;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 } } cout<<ans<<endl; 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(N+M)))，会超时；采用拓扑排序 + 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→v，f[u] |= f[v]，把 v 能到达的所有点全部继承给 u

5.统计输出
f[i].count()得到节点 i 能到达的节点总数，逐行输出。

AC 代码

#include<bits/stdc++.h> using namespace std; #define endl '\n' const int MAXN = 30005; vector<int> g[MAXN]; // 邻接表：g[u]存放u所有直接相连的后继节点 int in[MAXN]; // in[u]：节点u的入度，用于Kahn拓扑排序 bitset<MAXN> f[MAXN]; // f[u] 二进制位集合 // 若f[u][v] = 1，代表节点u可以到达节点v vector<int> 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 } queue<int> 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; }