CF1922B Forming Triangles 题解

解题思路

显然，有以下两种选择的方法：

• 所有边一样长；
• 两条一样长的边，第三条边小于这两条边。

然后组合数计算即可。

AC 代码

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include <vector>
#define ll long long
#define N 300005
int n,a[N];
inline ll C3(ll x){
    if(x<3) return 0ll;
    return x*(x-1)*(x-2)/6ll;
}
inline ll C2(ll x){
    if(x<2) return 0ll;
    return x*(x-1)/2ll;
}
inline void work(){
    scanf("%d",&n);
    for(register int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    std::sort(a+1,a+n+1);
    std::vector<int> cnt(n+1,0);
    for(register int i=1;i<=n;++i)
        ++cnt[a[i]];
    ll ans=0,res=n;
    for(register int i=n;i>=0;--i){
        res-=cnt[i];
        ans+=C3(cnt[i]);
        ans+=C2(cnt[i])*res;
    }printf("%lld\n",ans);
}
signed main(){
    int T;scanf("%d",&T);
    while(T--) work();
}