CCF NOI，CCF NOI1136 單詞分類

問題鏈接：CCF NOI1136 單詞分類。

時間限制: 1000 ms ?空間限制: 262144 KB

題目描述?

? Oliver為了學號英語決定苦背單詞，但很快他發現要直接記住雜亂無章的單詞非常困難，他決定對單詞進行分類。
? 兩個單詞可以分為一類當且僅當組成這兩個單詞的各個字母的數量均相等。
? 例如“AABAC”，它和“CBAAA”就可以歸為一類，而和“AAABB”就不是一類。
? 現在Oliver有N個單詞，所有單詞均由大寫字母組成，每個單詞的長度不超過100.你要告訴Oliver這些單詞會被分成幾類。

CCF NOI？輸入

? 輸入文件的第一行為單詞個數N，以下N行每行為一個單詞。

輸出

? 輸出文件僅包含一個數，表示這N個單詞分成的類數。

樣例輸入

3
AABAC
CBAAA
AAABB
樣例輸出

七下英語單詞表，2

數據范圍限制

? 對于70%的數據滿足N<=100。
? 對于100%的數據滿足N<=10000。

提示

?

單詞？

? 這個問題可以用排序來解決，需要二次排序，一是單詞內排序（按字母排序），二是單詞表排序。

? 然后數一下有多少單詞相同即可

? 這里同時給出C語言程序和C++語言程序。

? C語言程序和C++語言程序的排序函數不一樣，需要注意。

? 想比較而言，C++語言的排序函數sort()使用起來比較簡潔。

• 使用宏定義可以使得代碼可閱讀性增強。
• C語言的排序函數是qsort()，需要留意用法。
• C++語言的排序函數是sort()，需要留意用法。
  

常用英語單詞？

100分通過的C語言程序：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define N 10000
#define N2 100char word[N][N2+1];int cmp( const void *a , const void *b )
{return *(char *)a - *(char *)b;
}int cmp2(const void * a,const void *b)
{return strcmp((char *)a, (char *)b) ; //字典序從小到大
}int main(void)
{int n, len, i;scanf("%d", &n);for(i=0; i<n; i++) {scanf("%s", word[i]);len = strlen(word[i]);qsort(word[i], len, sizeof(word[i][0]), cmp);}qsort(word, n, sizeof(word[0]), cmp2);int count = n;for(i=1; i<n; i++)if(strcmp(word[i-1], word[i]) == 0)count--;printf("%d\n", count);return 0;
}

100分通過的C++語言程序：

英語單詞3500分類記憶、

#include <iostream>
#include <string>
#include <algorithm>using namespace std;const int N = 10000;
string word[N];int main()
{int n;cin >> n;for(int i=0; i<n; i++) {cin >> word[i];sort(word[i].begin(), word[i].end());}sort(word, word + n);int count = unique(word, word + n) - word;cout << count << endl;return 0;
}