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

本文主要是介绍Cowpatibility —— bitset找与某个数组有任何一个元素相交的所有数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

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;
}

这篇关于Cowpatibility —— bitset找与某个数组有任何一个元素相交的所有数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---