题解：P15754 [JAG 2025 Summer Camp #1] Dyad

· · 题解

link

Solution

首先，我们假设 \forall 1 \le i \le n,a_i \le b_i，如果不满足，交换。

对于 a_i \ne b_i，我们可以用 map 记录这样的数对的数量 k，因为我们不会在买的时候考虑顺序，所以对于这样的糖果对，方法数是 \binom{k}{2}，也就是 \frac{k \times (k-1)}{2}。

但是如果 a_i = b_i，就算有两个数 i,j，a_i \ne a_j,a_i = b_i,a_j = b_j，也可以算一种情况，把 a_i,b_i，a_j,b_j 分别给双胞胎即可。所以，我们可以把 a_i = b_i 视为同一类，把它们都改成 -1 就可以了。

Code

:::success[code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef double db;
typedef __int128 i128;
const ll inf=9e18,maxn=3e5+1;
const i128 Inf=1e35;
ll n,a[maxn],b[maxn],ans;
map<pair<ll,ll>,ll> mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        if(a[i]>b[i]) swap(a[i],b[i]);
        if(a[i]==b[i]) a[i]=b[i]=-1;
        mp[{a[i],b[i]}]++;
}
    for(pair<pair<ll,ll>,ll> m:mp)
    {
        ans+=m.second*(m.second-1)/2;
    }
    cout<<ans;
}

:::