ACM模版

描述

题解

这个题真是鬼斧神工，让我再一次见识到了 bitset 的神奇威力……

利用并查集来处理集合并的问题，然后暴力手段合并两个集合的元素，并且用 bitset 来处理和的种类数，这里十分巧妙，首先将原本的所有和全部加上新加入的元素形成新的和，然后与原本的和种数合并在一起即可。很好玩的一个题，没想到 bitset 操作竟然如此清真（其实我并不知道清真啥子梗）……

代码

#include <cstdio>
#include <bitset>
#include <iostream>

using namespace std;

const int MAXN = 1005;
const int MAXM = 1e5 + 10;

int n, Q;
int cnt[MAXN];
int pre[MAXN];
int d[MAXN][MAXN];
bitset<MAXM> a[MAXN];
bitset<MAXM> b;

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int find(int x)
{
    return pre[x] == x ? x : pre[x] = find(pre[x]);
}

int main()
{
    scan_d(n);
    for (int i = 1; i <= n; i++)
    {
        cnt[i] = 1;
        pre[i] = i;
        scan_d(d[i][cnt[i]]);
        a[i][0] = a[i][d[i][cnt[i]]] = 1;
    }

    scan_d(Q);
    int A, i, j;
    while (Q--)
    {
        scan_d(A);
        if (A == 2)
        {
            scan_d(i);
            printf("%zu\n", a[find(i)].count());    // 输出 a 中 1 的个数
            continue;
        }

        scan_d(i);
        scan_d(j);
        // 合并 i 和 j 所在集合
        int x = find(i), y = find(j);
        if (cnt[y] > cnt[x])
        {
            swap(x, y);
        }
        pre[y] = x;

        for (i = cnt[y]; i; i--)
        {
            d[x][++cnt[x]] = d[y][i];
            a[x] |= a[x] << (d[x][cnt[x]]);         // 添加一个元素后与原来的元素组成的新和
        }
    }

    return 0;
}