自动搬运

查看原文

来自洛谷，原作者为

	simonG 去做你认为对的

搬运于2025-08-24 22:07:23，当前版本为作者最后更新于2022-03-12 13:25:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

题意：求两两集合间没有交集的对数。
一看涉及集合计数，考虑容斥原理。

详解

先把答案赋值为 $n(n-1)$，即总共的对数。
枚举 $S_i$ ，答案减去与 $S_j(j<i)$ 有交集的对数。
对于集合 $S_i=\{a,b,c\}$ ，（此处把 $m$ 设为3）
设 $cnt_i$ 数组为含有$i$元素的集合个数。 那么与$S_i$有交集的集合个数为（容斥原理）：
$cnt_{a}+cnt_{b}+cnt_{c}-cnt_{a,b}-cnt_{b,c}-cnt_{a,c}+cnt_{a,b,c}$ 。
用总答案减去上式即可。
$m=5$ 也同理：我们发现上面的 $cnt$ 中的下标对应的是每个元素的出现与不出现。
这样就可以使用二进制枚举的方法。
用二进制中的第 $i$ 位表示第 $i$ 个数的出现与否。
当出现了奇数个元素时，对贡献为正；否则为负。
但是如何存储 $cnt$ 数组呢？用哈希表或 STL map 即可。
这里使用字符串存储。

代码

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
long long n,ans;
string a[7];
map<string,long long> f;
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=5; j++) cin>>a[j];
		sort(a+1,a+6);
		for(int j=1; j<32; j++) {//利用二进制枚举哪些数被选
			int cnt=0;
			string s="";
			for(int k=1;k<=5;k++)
				if(j&(1<<(k-1))) {
					cnt++;
					s+=a[k]+" ";
				} //用字符串存储方案 
			if(cnt&1) ans+=f[s];
			else ans-=f[s];
			f[s]++; 
		}
	}
	printf("%lld\n",n*(n-1)/2-ans);
	return 0;
}

应该是较短的代码。