题解 AT4862 【[ABC137C] Green Bin】
Zirnc
2020-02-29 17:03:12
[ChungZH's blog](https://chungzh.cn) · [ChungZH's portfolio](https://chungzh.cc)
## 题目
我们将调用通过以某种顺序排列字符串 $a$ 中包含的字符而获得的字符串，即 _anagram_。
例如，`greenbin` 是 `beginer` 的 _anagram_。 如此处所示，当同一字符多次出现时，该字符必须使用该次数。
给定 $N$ 个字符串 $s_1,s_2,\ldots,s_N$。每个字符串的长度为 $10$，由小写英文字符组成。 此外，所有这些字符串都是不同的。 找出整数对的数量 $(1 \leq i < j \leq N)$，使 $s_i$ 是 $s_j$ 的 _anagram_。
## 题解
每输入一个字符串就先排好序，然后用 STL 中的 map 记录每种字符串出现的次数，最后用 `(a.second * (a.second - 1) / 2)` 求出 $i, j$ 对数。
```cpp
#include <algorithm>
#include <iostream>
#include <map>
#define ll long long
using namespace std;
int main() {
int n;
cin >> n;
map<string, ll> m;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
sort(s.begin(), s.end());
m[s]++;
}
ll ans = 0;
for (auto a : m)
ans += (ll)(a.second * (a.second - 1) / 2);
cout << ans << endl;
return 0;
}
```