1475C Ball in Berland (思维)-蒲公英云

1475C Ball in Berland (思维)

题目

思路：看N为2e5可知复杂度为O(n)或O(nlogn)，在这我用两个map分别记录每个男和女各自可以和多少匹配，首先选好一组匹配，那么还可以找出多少组匹配与之组成两组呢？答案为：k - 此组匹配中男生可以匹配女生数 - 此组匹配中女生可以匹配男生数+1（他们自身匹配那条线多匹配了一次）。

在这里插入图片描述 Code:

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 5e5 + 5;
int Mod = 1e9 + 7;
int lst[Max];
int men[Max], women[Max];
int main()
{ 
    FAST;
    int t;
    cin >> t;
    while (t--)
    { 
        map<int, int> nan, nv;
        int a, b, k;cin >> a >> b >> k;
        for (int i = 1;i <= k;i++)
        { 
            int j;cin >> j;
            nan[j]++;
            men[i] = j;
        }
        for (int i = 1;i <= k;i++)
        { 
            int j;cin >> j;
            nv[j]++;
            women[i] = j;
        }
        ll ans = 0;
        for (int i = 1;i <= k;i++)
        { 
            ans += k - nan[men[i]] - nv[women[i]] + 1;
        }
        cout << ans/2 << endl;
    }
}