邪修卡常：动态bitset _

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