题目链接：poj 2408 Anagram Groups
题目大意：给定若干个字符串，将其分组，按照组成元素相同为一组，输出数量最多的前5组，每组按照字典序输出所
有字符串。数量相同的输出字典序较小的一组。
解题思路：将所有的字符串统计字符后hash，排序之后确定每组的个数并且确定一组中字典序最小的字符串。根据个数
以及字符串对组进行排序。
#include #include #include #include #include using namespace std; const int maxn = 30005; const int maxm = 30; const int X = 30; typedef unsigned long long ll; typedef pair pii; int N, M, E; vector vec, grop; vector g[maxn]; char word[maxn][maxm], st[maxn][maxm]; inline ll Hash(char* s) { int len = strlen(s), c[maxm]; memset(c, 0, sizeof(c)); for (int i = 0; i < len; i++) c[s[i]-'a']++; ll ret = 0; for (int i = 0; i < 26; i++) ret = ret * X + c[i]; return ret; } inline bool cmp (const pii& a, const pii& b) { if (a.second == b.second) return strcmp(st[a.first], st[b.first]) < 0; return a.second > b.second; } inline bool sort_by(const int& a, const int& b) { return strcmp(word[a], word[b]) < 0; } int main () { N = M = E = 0; vec.clear(); grop.clear(); while (scanf("%s", word[N]) == 1) { ll key = Hash(word[N]); vec.push_back(make_pair(key, N)); N++; } sort(vec.begin(), vec.end()); int cnt = 0; ll pre = -1; for (int i = 0; i < vec.size(); i++) { int idx = vec[i].second; if (vec[i].first != pre) { if (cnt) grop.push_back(make_pair(M++, cnt)); cnt = 0; g[M].clear(); pre = vec[i].first; strcpy(st[M], word[idx]); } cnt++; g[M].push_back(idx); if (strcmp(word[idx], st[M]) < 0) strcpy(st[M], word[idx]); } if (cnt) grop.push_back(make_pair(M++, cnt)); sort(grop.begin(), grop.end(), cmp); for (int i = 0; i < min(5, (int)grop.size()); i++) { printf("Group of size %d: ", grop[i].second); int x = grop[i].first; sort(g[x].begin(), g[x].end(), sort_by); for (int j = 0; j < g[x].size(); j++) { if (j == 0 || strcmp(word[g[x][j-1]], word[g[x][j]])) printf("%s ", word[g[x][j]]); } printf(".\n"); } return 0; }