题目:
Oliver为了学号英语决定苦背单词,但很快他发现要直接记住杂乱无章的单词非常困难,他决定对单词进行分类。 两个单词可以分为一类当且仅当组成这两个单词的各个字母的数量均相等。 例如“AABAC”,它和“CBAAA”就可以归为一类,而和“AAABB”就不是一类。 现在Oliver有N个单词,所有单词均由大写字母组成,每个单词的长度不超过100.你要告诉Oliver这些单词会被分成几类。
分析:
直接先把所有单词按照字典序重组一次,再把整个存储字符串的数组排序一次,然后相邻的依次比较,若不同则类型+1,最后输出。
附上代码: const maxn=100000; var n,ans:longint; s:array [0..maxn] of string; data:array ['A'..'Z'] of longint; procedure init; var i,j:longint; st:string; ch:char; begin readln(n); for i:=1 to n do begin readln(st); fillchar(data,sizeof(data),0); for j:=1 to length(st) do inc(data[st[j]]); for ch:='A' to 'Z' do for j:=1 to data[ch] do s[i]:=s[i]+ch; end; end; procedure qsort(l,r:longint); var i,j:longint; k,mid:string; begin i:=l; j:=r; mid:=s[(l+r) shr 1]; repeat while s[i]<mid do inc(i); while s[j]>mid do dec(j); if i<=j then begin k:=s[i]; s[i]:=s[j]; s[j]:=k; inc(i); dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; procedure main; var i,j:longint; begin qsort(1,n); i:=1;j:=2; while i<>n do begin if s[i]<>s[j] then inc(ans); inc(i);inc(j); end; write(ans+1); end; begin init; main; end.
