JZOJ8.16(C组)单词分类

    xiaoxiao2026-06-05  6

    题目:

    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.

    转载请注明原文地址: https://ju.6miu.com/read-1310212.html
    最新回复(0)