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位为1

int 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;
}