B3695

MatchaNeko_nya · 2023-01-18 17:37:47 · 题解

建议先阅读扶苏的bitset浅谈

本文主要描述如何实现题目中所述操作。

我们用一个 bitset<30005> 的第 i 位是 0/1 表示存在/不存在。

那么我们一个一个操作来看：

操作 1:

我们观察一个序列 1 3 5 9 在一个 bitset<15> 中的映射：000000100010101

再观察这个序列所有元素都加上 6 之后的映射：100010101000000

你发现了什么？

对，就是左移，所以操作 1，就是左移这个 bitset。

你是不是以为，我们建一个 bitset<m>，然后左移之后超出去的部分就为自动删掉？

这里有一个坑点：bitset<N> 中的 N 必须为一个编译期常数，那么这里的 m 显然在输入了之后不是一个编译期常数，那么就不能 bitset<m>，怎么办？

我们可以给另一个 bitset<30005> 的 1\sim m 位都赋为 1，剩余的位 0，那么在左移之后，我们就用左移了的这个 bitset 与上后一个 bitset，就能起到将不在 [1,m] 内的元素删除的作用。

操作 2:

相对操作 1 就简单了，因为操作 2 中的右移出了 0 之后会自动删除，那么直接左移即可。

操作 3:

交集是由同时在两个集合中的元素构成的，那么这恰好符合哪种位运算？——与运算 &。

所以操作 3 就是 S[x]&S[y]。

操作 4:

同理可得，并集是由在任意一个集合中的元素构成的，那么这就是或运算 |，操作 4 便是 S[x]|S[y]。

操作 5:

对称差是由只在其中一个集合的元素构成的，那么这就是异或运算 ^，得操作 5 为 S[x]^S[y]。

Tip: 如果不知道异或是什么的，记住：若两个布尔值相等，则它们的异或值为 0，反之为 1。

至此，你就可以利用 STL AC 一道黄题了。

附代码：

#include <bitset>
#include <vector>
#include <iostream>

const int maxn=30005;
int n,m,q;
std::bitset<maxn> s[maxn];

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin>>n>>m>>q;
    for(int i = 1,c,x;i<=n; i++){
        for(std::cin>>c;c;--c){
            std::cin>>x;
            s[i].set(x-1,1);
        }
    }
    for(int i = 0; i<m; i++) s[0].set(i,1);
    for(int o,x,y;q;--q){
        std::cin>>o>>x>>y;
        if(o==1){
            s[x]<<=y;
            s[x]&=s[0];
        }else if(o==2){
            s[x]>>=y;
        }else if(o==3){
            std::cout<<(s[x]&s[y]).count()<<'\n';
        }else if(o==4){
            std::cout<<(s[x]|s[y]).count()<<'\n';
        }else if(o==5){
            std::cout<<(s[x]^s[y]).count()<<'\n';
        }
    }
    return 0;
}