常见算法题型之STL基础：bitset。附真题题解

bitset 用法详解与「跳石头」例题题解2024蓝桥杯国B一、bitset 基础与常用操作bitset是 C 标准库中固定大小的二进制位集合容器底层以机器字为单位压缩存储支持高效的位运算与集合操作。它的核心优势是将原本(O(n))(O(n))(O(n))的集合操作如并集、交集压缩为(O(n/w))(O(n/w))(O(n/w))其中www为机器字长64 位系统下(w64)(w64)(w64)在状态压缩、可达性统计、01 DP 优化中广泛使用。1. 定义与初始化bitset的大小必须是编译期常量常见初始化方式#includebitsetusingnamespacestd;bitset8bs1;// 8位全0bitset8bs2(0b1011);// 用二进制数初始化bitset8bs3(1100);// 用01字符串初始化bitset8bs4bs2;// 拷贝初始化2. 单点位操作操作功能bs.set(pos)将第pos位置为 1bs.reset(pos)将第pos位置为 0bs.flip(pos)将第pos位取反bs[pos] 1/0直接访问修改第pos位无边界检查bs.test(pos)检查第pos位是否为 1越界抛异常3. 整体状态统计操作功能bs.count()返回集合中 1 的个数即集合大小bs.size()返回 bitset 的总位数bs.any()判断是否存在至少一个 1bs.none()判断是否全为 0bs.all()判断是否全为 1bs.set()所有位置 1bs.reset()所有位置 0bs.flip()所有位取反4. 集合位运算bitset原生支持所有位运算符对应集合的交、并、对称差等操作bitset8a,b;ab;// 按位与 → 集合交集a|b;// 按位或 → 集合并集a^b;// 按位异或 → 集合对称差~a;// 按位取反ak;// 左移k位低位补0ak;// 右移k位高位补0// 对应赋值运算ab;a|b;a^b;5. 类型转换bs.to_string();// 转为01字符串二、例题精讲[蓝桥杯 2024 国 B] 跳石头题目链接https://www.luogu.com.cn/problem/P109141. 题目大意有nnn块石头排成一排第iii块石头权值为cicici。从第jjj块石头出发可以跳到jcjjcjjcj或2j2j2j不超过nnn。定义从xxx出发的得分为所有可能经过的石头的权值去重后的数量。求所有起点中的最大得分。2. 思路分析核心观察跳跃方向只能从小编号到大编号cicici为正整数故iciiici iicii2ii2i i2ii暴力思路枚举每个点当起点使用队列模拟两种跳跃情况使用unordered_set记录经过路径最终统计得分暴力代码过60%#includebits/stdc.husingnamespacestd;constintN40010;intn,c[N];intsolve(intstart){unordered_setintvis;// 记录访问过的石头编号queueintq;q.push(start);vis.insert(start);while(!q.empty()){intuq.front();q.pop();intv1uc[u];intv2u*2;if(v1n!vis.count(v1)){vis.insert(v1);q.push(v1);}if(v2n!vis.count(v2)){vis.insert(v2);q.push(v2);}}unordered_setintvals;// 收集权值自动去重for(intx:vis)vals.insert(c[x]);returnvals.size();}intmain(){cinn;for(inti1;in;i)cinc[i];intans0;for(inti1;in;i){ansmax(ans,solve(i));}coutansendl;return0;}正解 DP 定义设 dp[i] 表示从第iii块石头出发所有可能经过的权值构成的集合。根据跳跃规则转移方程为dp[i] {ci} ∪dp[ici] ∪ dp[2i]当icin时取dp[ici]; 当2*in时取dp[2i]为什么用 bitset 优化如果用普通数组或set维护集合每次合并集合的时间是(O(n))(O(n))(O(n))总时间复杂度O(n2)O(n^2)O(n2)(n40000)(n40000)(n40000)时会严重超时。使用bitset后每个 dp[i] 对应一个bitset第vvv位为 1 表示权值vvv在集合中集合并集等价于按位或运算单次合并时间(O(n/w))(O(n/w))(O(n/w))总时间复杂度降为O(n2/w)O(n^2/w)O(n2/w)(n4e4)(n4e4)(n4e4)时约 2.5e7 次运算可轻松通过处理顺序由于所有后继位置都大于iii我们倒序从nnn到111计算每个 dp[i]。3. 正解代码#includebits/stdc.husingnamespacestd;constintN4e45;intc[N],n,ans;bitsetNbs[N];// bs[i] 表示从i出发的权值集合intmain(){ios::sync_with_stdio(false);cin.tie(0);cinn;for(inti1;in;i)cinc[i];// 倒序DPfor(intin;i1;i--){bs[i].set(c[i]);// 加入当前石头的权值if(ic[i]n)bs[i]|bs[ic[i]];// 合并第一条跳跃路径的集合if(i*2n)bs[i]|bs[i*2];// 合并第二条跳跃路径的集合ansmax(ans,(int)bs[i].count());// 更新最大得分}coutansendl;return0;}4. 代码解析数组定义bitsetN bs[N]开了nnn个长度为NNN的位集合每个位集合对应一个起点的权值集合。倒序循环从最后一块石头向前处理保证计算 bs[i] 时bs[ici] 和 bs[2i] 已经计算完成。置位当前权值bs[i].set(c[i])将当前石头的权值加入集合对应集合中的ci{ci}ci。合并后继集合通过|按位或操作将后继位置的可达权值集合合并到当前集合对应集合并集。统计答案bs[i].count()返回当前集合中 1 的个数也就是去重后的权值数量取最大值即为答案。5. 复杂度分析时间复杂度O(n2/w)O(n^2/w)O(n2/w)(w64)(w64)(w64)(n4e4)(n4e4)(n4e4)时运算量约 2500 万完全在时间限制内。空间复杂度O(n2/w)O(n^2/w)O(n2/w)约 200MB符合常规评测机的内存限制。6. 样例模拟输入5 4 3 5 2 1倒序计算过程i5i5i5bs[5] 加入 1 →{1}得分 1i4i4i4bs[4] 加入 2 →{2}得分 1i3i3i3bs[3] 加入 5 →{5}得分 1i2i2i2加入 3合并 bs[5]{1} 和 bs[4]{2} →{1,2,3}得分 3i1i1i1加入 4合并 bs[5]{1} 和 bs[2]{1,2,3} →{1,2,3,4}得分 4最终最大得分为 4与样例输出一致。