题解：SP33299 ADAFUROW - Ada and Furrows

Lijiangjun4 · 2024-12-12 23:26:58 · 题解

SP33299 题解

题目传送门

洛谷地址

SPOJ 地址

解题思路

读题，可以发现题目需要对每个犁沟内的蔬菜种类进行并集（v），交集（^），补集（\）等集合操作。为了加速集合操作，考虑使用数据结构 std::bitset。

bitset

bitset 即位图，可以理解为每个元素只占 1bit 的 bool 数组，其支持下标访问和所有的位运算符号，常用成员函数如下：

函数名	作用
`count()`	返回 `true` 的数量。
`size()`	返回 `bitset` 的大小。
`any()`	返回是否全为真。
`none()`	返回是否都是假。
`set()`	全部设为真。
`set(pos,val=true)`	将第 `pos` 位设为 `val`。
`reset()`	全部设为假。
`reset(pos)`	将第 `pos` 位设为假。
`flip()`	全部翻转。

bitset 可以使时间复杂度和空间复杂度均优化 \frac{1}{32} 的常数。

更多内容见 OI-Wiki。

回到原题，定义 bitset<20005> a[20005]，其中 a[i][j] 表示第 i 个犁沟有没有种第 j 中蔬菜。对于每种操作：

+ 和 -：将对应位置进行修改即可。
v：只要在两个犁沟中出现过一次就计入答案，则使用按位或运算符。
^：只有在两个犁沟中都出现过才能计入答案，则使用按位与运算符。
!：只有恰好出现一次才能计入答案，则使用按位异或运算符。
\：这个比较麻烦，可以先用按位与求出交集，再异或上 a[x] 进行去重。

注意，'\' 为转义字符，如果要表示该符号本身，应写作 '\\' 。

AC Code

#include<iostream>
#include<bitset>
using namespace std;
bitset<20005> a[20005];
int main()
{
    int q;
    cin>>q;
    while(q--)
    {
        char op;
        int x,y;
        cin>>op>>x>>y;
        if(op=='+') a[x][y]=1;
        if(op=='-') a[x][y]=0;
        if(op=='v') cout<<(a[x]|a[y]).count()<<'\n';
        if(op=='^') cout<<(a[x]&a[y]).count()<<'\n';
        if(op=='!') cout<<(a[x]^a[y]).count()<<'\n';
        if(op=='\\') cout<<(a[x]^(a[x]&a[y])).count()<<'\n';
    }
    return 0;
}

AC 记录