自动搬运

查看原文

来自洛谷，原作者为

	tuboshu666 **

搬运于2025-08-24 23:11:18，当前版本为作者最后更新于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