首页 > 代码库 > USACO 2014 FEB自动打字{Silver题1}
USACO 2014 FEB自动打字{Silver题1}
自动打字{Silver题1}
【问题描述】
贝西新买了手机，打字不方便，请设计一款应用，帮助她快速发消息。
字典里有W（W<=30000）个小写字母构成的单词，所有单词的字符总数量不超过1,000,000，这些单词是无序的。现在给出N(1 <= N <= 1000)个询问，每个询问i包含一个的字符串s_i（每个字符串最多包含1000个字符）和一个整数K_i，对于所有以s_i为前缀的单词，其中按字典序排序后的第K_i个单词，求该单词在原字典里的序号。
【文件输入】
第一行为两个整数W和N。
接下来2..W+1行，每行一个单词；
接下来W+2..W+N+1行，一个整数和一个字符串，分别表示K_i和s_i。
【文件输出】
输出共N行，每行一个整数，表示位置，如果无解则输出-1。
【输入样例】
10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da
【输出样例】
3
1
-1
【样例说明】
以a为前缀的单词有{aa,aaa,aab,ab,abc,ac}，第4个是ab，它在原字典中的位置是3，以da为前缀的单词有{daa,dab,dadba}，第2个是dab，它在原字典中的位置是1，以da为前缀的第4个单词不存在。
思路：本题一开始听闻要使用trie树，结果后来发现原来不用trie树也可以AC。首先快排字符串，然后将以各个字母为开头的起始和终点处理出来，然后枚举就可以AC了。代码如下
1 var 2 str:array[0..30000]of string; 3 s,e:array[‘a‘..‘z‘]of longint; //以各个字母为开头的起点和终点 4 num:array[0..30000]of integer; 5 w,n,i,j,k:longint; 6 temp:string; 7 ch:char; 8 9 procedure openit;10 begin11 assign(input,‘auto.in‘);assign(output,‘auto.out‘);12 reset(input);rewrite(output);13 end;14 15 procedure closeit;16 begin17 close(input);close(output);18 end;19 20 procedure qsort(l,r:longint); //快排字符串21 var i,j,p:longint;22 m,q:ansistring;23 begin24 i:=l;j:=r;m:=str[(l+r) div 2];25 repeat26 while str[i]<m do inc(i);27 while str[j]>m do dec(j);28 if not (i>j) then29 begin30 q:=str[i];str[i]:=str[j];str[j]:=q;31 p:=num[i];num[i]:=num[j];num[j]:=p;32 inc(i);dec(j);33 end;34 until i>j;35 if l<j then qsort(l,j);36 if i<r then qsort(i,r);37 end;38 39 procedure datain;40 var i:longint;41 begin42 readln(w,n);43 for i:=1 to w do readln(str[i]);44 for i:=1 to w do num[i]:=i;45 qsort(1,w);46 k:=2;ch:=str[1,1];s[ch]:=1;e[ch]:=1;47 while k<=w do48 begin49 if str[k,1]<>ch then begin50 ch:=str[k,1];51 s[ch]:=k;e[ch]:=k;52 end53 else inc(e[ch]);54 inc(k);55 end;56 end;57 58 59 begin60 openit;61 datain;62 for i:=1 to n do63 begin64 readln(k,ch,temp);65 for j:=s[temp[1]] to e[temp[1]] do //枚举66 if str[j]>=temp then break;67 if (j+k-1>w) or (length(str[j+k-1])<length(temp)) then68 begin69 writeln(‘-1‘);70 continue;71 end;72 j:=j+k-1;73 if copy(str[j],1,length(temp))=temp then writeln(num[j])74 else writeln(‘-1‘);75 end;76 closeit;77 end.
USACO 2014 FEB自动打字{Silver题1}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。