题解：P11911 [PA 2025] 集合 1 / Zbiory 1

tuboshu666 · 2025-03-31 20:57:26 · 题解

思路

集合的并、交、取补集操作，容易想到使用 bitset 优化。由于 n 的范围较小，可以用一个 bitset 来代表一个集合。定义：一个 n 位的 bitset 第 i 位为 1 时，代表数字 i 在该集合中。

对于 1\le i\le n 的集合，直接暴力将 i 的倍数置 1 即可。

后 m 个集合，实际都是通过 3 个操作构造而来。

对于操作 1：由或运算的性质：对应的二进制位有 1 个为 1，那么该位在操作后为 1。将 A_x 和 A_y 进行或运算，得到的就是两个集合并后的结果。

对于操作 2：由与运算的性质：对应的二进制位同时为 1 时，该位操作后才为 1。于是将 A_x 和 A_y 进行与运算，就是集合交后的结果。

对于操作 3：其实就是在全集 U 取 A_x 的补集。想到异或的性质。将 U 和 A_x 进行异或，那么两集合同时存在的数，该位会置 0，剩下的置 1，符合补集要求。

Code

#include <iostream>
#include <bitset>
#include <vector>
using namespace std;

const int N = 5e4 + 10;
typedef bitset<N> bt; //n位的bitset模拟一个集合

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,m,q;
    cin >> n >> m >> q;
    vector<bt> a(n+m+1);
    for (int i = 1 ; i <= n ; i++)
    {
        for (int j = i ; j <= n ; j += i)
        {
            a[i][j] = 1; //1到n的集合初始化
        }
    }

    for (int i = 1 ; i <= m ; i++)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x,y;
            cin >> x >> y;
            a[i+n] = a[x] | a[y]; //或运算模拟集合并
        }
        else if (op == 2)
        {
            int x,y;
            cin >> x >> y;
            a[i+n] = a[x] & a[y]; //与运算模拟集合交
        }
        else
        {
            int x;
            cin >> x;
            a[i+n] = a[1] ^ a[x]; //异或运算模拟取补集
        }
    }

    for (int i = 1 ; i <= q ; i++)
    {
        int x,y;
        cin >> x >> y;
        if (a[x][y] == 1) cout << "TAK" << endl;
        else cout << "NIE" << endl;
    }

    return 0;
}

题外话

本篇并未详细介绍 bitset。如有需求，请移步扶苏的bitset浅谈。

另外，推荐一道类似的题目：

B3695 集合运算 3