洛谷P1808单词分类[NOI导刊]
1237+
作者:crxis 发布:2021-04-30 分类:排序
题目大意:有n个单词,我们认为两个单词是一样的,只需要出现的各种字母数量都相等,请问共有多少个不同的单词?
题目描述
Oliver为了学好英语决定苦背单词,但很快他发现要直接记住杂乱无章的单词非常困难,他决定对单词进行分类。
两个单词可以分为一类当且仅当组成这两个单词的各个字母的数量均相等。
例如“AABAC”,它和“CBAAA”就可以归为一类,而和“AAABB”就不是一类。
现在Oliver有N个单词,所有单词均由大写字母组成,每个单词的长度不超过100。你要告诉Oliver这些单词会被分成几类。
输入输出格式
输入格式
输入文件的第一行为单词个数N,以下N行每行为一个单词。
输出格式
输出文件仅包含一个数,表示这N个单词分成的类数
输入输出样例
输入样例 #1
3
AABAC
CBAAA
AAABB
输出样例 #1
2
说明
对于70%的数据满足N≤100。 对于100%的数据满足N≤10000。
解题思路
排序后比较相邻是否相等即可。程序用的是桶排序,统计每个字母出现的次数;比较用的是内存比较。