CF1475C Ball in Berland

题意

在毕业典礼上，有\(a\)个男孩和\(b\)个女孩准备跳舞，不是所有的男孩和女孩都准备结伴跳舞。

现在你知道\(k\)个可能的舞伴，你需要选择其中的两对，以便使没有人重复地出现在舞伴里，求可能的数量。

思路

暴力

最朴素，也是简单的方法，就是通过暴力组合进行配对。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6;
int a,b,k,boy[maxn],girl[maxn],ans;
int run()
{
	ans=0;
	cin>>a>>b>>k;
	for(int i=0;i<k;i++) cin>>boy[i];
	for(int i=0;i<k;i++) cin>>girl[i];
	for(int i=0;i<k;i++)
	{
		int t1=boy[i],t2=girl[i],flag=1,cnt=0;
		for(int j=i+1;j<k;j++)
		{
			if(t1==boy[j] || t2==girl[j]) flag=0;
			else
			{
				ans++;
			}
		}
	}
	cout<<ans;
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		run();
		cout<<endl;
	}
}

然而，会在第四个点超时，所以还得优化

利用桶进行优化

我们注意到，超时的原因就是这段代码：

for(int j=i+1;j<k;j++)
		{
			if(t1==boy[j] || t2==girl[j]) flag=0;
			else
			{
				ans++;
			}
		}

那么，该怎么进行优化，使其从\(O(k)\)变为\(O(1)\)呢？

这段代码的用途其实就是在\(t1，t2\)后面查找有没有重复出现的人。关注题目中的数据范围：\(1 \leq t \leq 10^4，1\leq a,b,k \leq 2\cdot 10^5\)，因此可以开一个桶来存储男生和女生各出现的次数，然后再与当前\(t1，t2\)作差即可

手玩一下样例：

最开始的桶是这样的：

boy	2	1	1
girl	0	2	1	1

随后，对\((1,2)\)进行判断，ans=剩余组数(\(3\))-重复数量(\(2-1+2-1\))，即\(ans=1\)

然后，桶变成了这样：

boy	1	1	1
girl	0	1	1	1

为了避免重复，每次计算完1组后都需要更新一下对应的男女生人数。进行完\((1,3)\)的操作后，\(ans=3\)

随后是这样：

boy	0	1	1
girl	0	1	0	1

继续进行如上操作，\(ans=4\)，更新桶

接着：

boy	0	0	1
girl	0	0	0	1

当只剩1组时，意味着枚举结束了，并输出\(ans\)为\(4\)

整个程序的时间复杂度是\(O(5tk)\)，~~CF的机子慢所以算精确点~~，不会超时

另：十年CF一场空，不开\(long\space long\)见祖宗

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+10;
int boy[MAXN],girl[MAXN],a,b,k,ans,bo[MAXN],g[MAXN];
void run()
{
	ans=0;
	memset(boy,0,sizeof(boy));
	memset(girl,0,sizeof(girl));
	cin>>a>>b>>k;
	for(int i=0;i<k;i++)
	{
		cin>>bo[i];
		boy[bo[i]]++;
	}
	for(int i=0;i<k;i++)
	{
		cin>>g[i];
		girl[g[i]]++;
	}
	for(int i=0;i<k;i++)
	{
		int t1=bo[i],t2=g[i];
		ans+=(k-i-1)-(boy[t1]+girl[t2]-2);
		boy[t1]--,girl[t2]--;
	}
	cout<<ans<<endl;
}
signed main()
{
	int t;
	cin>>t;
	while(t--) run();
}