Green Bin

so_find_skind · 2022-12-11 20:09:24 · 题解

传送门

本题思路：

首先不难看出，两者被判定为 anagram 的话，说明在排序之后是完全相等的，那么第一步就是排序，即：

for(...)
    sort(a[i].begin(),a[i].end());
sort(a+1,a+1+n);

第二步两种做法：

一、直接暴力枚举，只是因为 n\leq10^5，所以泡汤了。

二、每次记录连续相等的数量，同时我们假定数量为 ans，那么这个区间的对数即为 \frac{ans\times(ans-1)/2}{2}，将每个连续区间对数相加得和即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
long long n,ans=1,sum;
//长度为十的字符串有至多3628800种表达方式还是得防超int的
string a[100005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sort(a[i].begin(),a[i].end());
    }
    sort(a+1,a+1+n);
    a[n+1]="1";
    for(int i=2;i<=n+1;i++){
        if(a[i]==a[i-1])
            ++ans;
        else{
            sum+=ans*(ans-1)/2;
            ans=1;
        }
    }
    cout<<sum<<"\n";
    //不要忘换行
    return 0;
}