B3695 集合运算 3题解
代码由博主编写，文章由deepseek-R1:官网编写
博客食用更佳
题目解析
本题要求处理多个集合的修改和查询操作。每个集合包含1到m之间的整数，支持加减元素值并调整范围，以及查询两个集合的交集、并集和对称差的元素个数。使用位运算（bitset）高效处理集合操作是关键。
思路分析
- 集合表示：每个集合用一个bitset存储，其中第i位为1表示元素i存在于集合中。
- 操作处理：
- 加减操作：通过bitset的位移实现元素的整体加减，并结合掩码（mask）清除超出范围的元素。
- 查询操作：利用bitset的位运算（与、或、异或）直接计算交集、并集、对称差。
- 掩码作用：确保操作后的元素始终在1到m范围内，通过按位与操作过滤无效元素。
代码解析
-
初始化：
- 读取集合初始元素，设置对应bitset位。
- 创建掩码
none，其1到m位为1，用于后续过滤。
-
操作处理：
- 操作1：左移y位（加y），并用掩码清除超限元素。
- 操作2：右移y位（减y），同样用掩码处理。
- 查询操作3-5：直接使用位运算计算结果并统计1的个数。
示例演示
以样例输入为例，初始集合s1={1,2,3}，s2={1,2,4,5}：
- 操作1将s2每个元素加1，得到{2,3,5}。
- 操作2将s1每个元素减1，得到{1,2}。
- 查询交集得到{2}，并集得到{1,2,3,5}，对称差得到{1,3,5}。
核心代码逻辑
#include <bitset>
#include <cstdint>
#include <iostream>
using namespace std;const int maxn = 3e4;
int n, m, q;
bitset<maxn + 5> bs[maxn + 5]; // 每个集合的bitset表示
bitset<maxn + 5> none; // 掩码，1~m位为1int main() {cin >> n >> m >> q;for (int i = 1; i <= m; ++i)none[i] = 1; // 初始化掩码for (int i = 1; i <= n; ++i) {int cnt, num;cin >> cnt;while (cnt--) {cin >> num;bs[i][num] = 1; // 设置初始元素}}while (q--) {int op, x, y;cin >> op >> x >> y;if (op == 1) {bs[x] <<= y; // 左移y位（加y）bs[x] &= none; // 清除超限元素} else if (op == 2) {bs[x] >>= y; // 右移y位（减y）bs[x] &= none;} else if (op == 3)cout << (bs[x] & bs[y]).count() << endl; // 交集元素个数else if (op == 4)cout << (bs[x] | bs[y]).count() << endl; // 并集元素个数else if (op == 5)cout << (bs[x] ^ bs[y]).count() << endl; // 对称差元素个数}return 0;
}
总结
通过bitset的位操作高效处理集合运算，位移结合掩码快速完成元素加减和范围调整。查询操作直接利用位运算特性，时间复杂度低，适用于大规模数据处理。理解bitset的位操作与集合运算的对应关系是解题关键。
