Cowpatibility —— bitset找与某个数组有任何一个元素相交的所有数组

Description

Cowpatibility —— bitset找与某个数组有任何一个元素相交的所有数组

Input

Cowpatibility —— bitset找与某个数组有任何一个元素相交的所有数组

Output

Please output the number of pairs of cows that are not compatible.

Sample Input

4
1 2 3 4 5
1 2 3 10 8
10 9 8 7 6
50 60 70 80 90
Sample Output

4
Hint

题意:

给你n个含有5个数字的数组,两个数组有任意一个数相同就是相交的,问你不相交的数组有多少

题解:

刚开始想用string来着,但是开不下,bitset开1e65e4的空间好像也不行,但是他最多只有25e4个数,25e45e4就开的下了,那我们离散化一下,之后第i个数组含有j,那么就在第j个bitset里面将i标1,最后for一遍将每个数组或起来,找有多少个1即可,由于不相交的数组,两边都会找过,那么要/2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5;
bitset<50005>bs[250005],sum;
int a[50005][10],b[250005];
int main()
{
    ll n;
    scanf("%lld",&n);
        int cnt=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=5;j++)
            scanf("%d",&a[i][j]),b[++cnt]=a[i][j];
    sort(b+1,b+1+cnt);
    int all=unique(b+1,b+1+cnt)-b-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=5;j++)
            a[i][j]=lower_bound(b+1,b+all,a[i][j])-b,bs[a[i][j]].set(i);
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        sum.reset();
        for(int j=1;j<=5;j++)
        {
            sum|=bs[a[i][j]];
        }
        ans+=n-sum.count();
    }
    printf("%lld\n",ans/2);
    return 0;
}
上一篇:BZOJ 4939: [Ynoi2016]掉进兔子洞(莫队+bitset)


下一篇:JSOI2010 连通数