企业官网建设流程全解析

由于 std::bitset 仅支持编译期固定大小，无法动态确定长度，这使得某些 ∑�≤� 的多测题中使用 std::bitset 超时。于是我让 AI 生成了一份比赛中可用的动态bitset模版，并且测试了其在部分板题里的性能。

实现

cpp

#include <iostream> #include <vector> #include <cstdint> using namespace std; using u64 = uint64_t; struct dynamic_bitset { int n; std::vector<u64> b; dynamic_bitset(int _n = 0) : n(_n), b((_n + 63) >> 6, 0) {} void resize(int new_n) { if (new_n == n) return; b.resize((new_n + 63) >> 6, 0); // 新块自动置零 n = new_n; clean_tail(); } // 读取某一位（只读，不抛异常） bool operator[](int pos) const { return (b[pos >> 6] >> (pos & 63)) & 1; } // 设置某一位 void set(int pos, bool val = true) { if (val) b[pos >> 6] |= 1ULL << (pos & 63); else b[pos >> 6] &= ~(1ULL << (pos & 63)); } // 置零某一位 void reset(int pos) { b[pos >> 6] &= ~(1ULL << (pos & 63)); } // 翻转某一位 void flip(int pos) { b[pos >> 6] ^= 1ULL << (pos & 63); } // 位运算 dynamic_bitset& operator&=(const dynamic_bitset& rhs) { for (size_t i = 0; i < b.size(); ++i) b[i] &= rhs.b[i]; return *this; } dynamic_bitset& operator|=(const dynamic_bitset& rhs) { for (size_t i = 0; i < b.size(); ++i) b[i] |= rhs.b[i]; return *this; } dynamic_bitset& operator^=(const dynamic_bitset& rhs) { for (size_t i = 0; i < b.size(); ++i) b[i] ^= rhs.b[i]; return *this; } dynamic_bitset operator~() const { dynamic_bitset res = *this; for (auto& x : res.b) x = ~x; res.clean_tail(); return res; } // 1 的个数 int count() const { int ans = 0; for (auto x : b) ans += __builtin_popcountll(x); return ans; } // 清除尾部多余位 void clean_tail() { if (n == 0) return; int rem = n & 63; if (rem) b.back() &= (1ULL << rem) - 1; } }; // 非成员二元运算符（方便书写） inline dynamic_bitset operator&(dynamic_bitset a, const dynamic_bitset& b) { return a &= b; } inline dynamic_bitset operator|(dynamic_bitset a, const dynamic_bitset& b) { return a |= b; } inline dynamic_bitset operator^(dynamic_bitset a, const dynamic_bitset& b) { return a ^= b; }

使用范例

cpp

int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); dynamic_bitset a(10),b; b.resize(10); a.set(1), a.set(2); b.flip(0); dynamic_bitset c(a|b); cout << c.count() << endl; return 0; }

与 std::bitset 的区别

• 不支持左移/右移
• []只读，无法通过 bit[0] = 1 来置位。置位只能使用 set 和 reset 函数
• 不支持 any、all 等函数（这些也没什么必要）
• 输出不与 cout 兼容，只能逐位遍历
• 不支持转化整数和字符串

与 std::bitset 的性能对比

【模板】传递闭包

std::bitset

动态bitset

[PA 2025] 集合 1 / Zbiory 1

std::bitset

动态bitset

可以看到与 std::bitset 的性能差距还是比较明显。但是作为一种走投无路下的卡常手段，动态bitset已经足够了。如果再追求优化，可以考虑上 SIMD 指令集，由于比赛中不确定是否能够使用，这里不太推荐。