题解 AT4862 【[ABC137C] Green Bin】

Zirnc · 2020-02-29 17:03:12 · 题解

ChungZH's blog · ChungZH's portfolio

题目

我们将调用通过以某种顺序排列字符串 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 对数。

#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;
}