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