申請SAE

如果您發現本博客的外觀很難看，那是因為部分外觀文件被中國.國家.防火.牆屏.蔽所致！
請翻～牆！

我的Wordpress博客的地址： http://zhuyf.tk/

2012年2月3日 星期五

網易2010“有道難題”編程挑戰賽 有道搜索框

描述 Description
在有道搜索框中，當輸入一個或者多個字符時，搜索框會出現一定數量的提示，如下圖所示：

現在給你N個單詞和一些查詢，請輸出提示結果，爲了簡這個問題，只需要輸出以查詢詞爲前綴的並且按字典序排列的最前面的8個單詞，如果符合要求的單詞一個也沒有請只輸出當前查詢詞。 


輸入格式 Input Format
第一行是一個正整數N，表示詞表中有N個單詞。
接下來有N行，每行都有一個單詞，注意詞表中的單詞可能有重複，請忽略掉重複單詞。所有的單詞都由小寫字母組成。
接下來的一行有一個正整數Q，表示接下來有Q個查詢。
接下來Q行，每行有一個單詞，表示一個查詢詞，所有的查詢詞也都是由小寫字母組成，並且所有的單詞以及查詢的長度都不超過20，且都不為空
其中：N<=10000,Q<=10000

輸出格式 Output Format
對於每個查詢，輸出一行，按順序輸出該查詢詞的提示結果，用空格隔開。

樣例輸入 Sample Input
10
a
ab
hello
that
those 
dict
youdao
world
your 
dictionary
6
bob
d
dict
dicti
yo 
z

樣例輸出 Sample Output
bob
dict dictionary
dict dictionary
dictionary 
youdao your
z
時間限制 Time Limitation
各個測試點1s
【分析】
 很明顯字典樹的題嘛！！
構建一棵字典樹，然後遞歸即可。

【我的代碼】
不知道為什麼Tyvj在線評測系統會不允許動態申請內存，我先寫了一個動態字典樹，結果WA了9組，只有第2組（就是樣例）對了，然後我上網找了一個當時參加這個比賽的大牛的代碼（當時TopCoder判的滿分）交上去，仍是WA9組，只有第二組對，他的代碼是STL中的紅黑樹(set)，也是動態內存分配～額，被逼無奈，寫了個靜態的Trie樹交上去就AC了。
由於網上暫時找不到測試數據，所以我也不知道我那個動態的字典樹是否能AC。

Code.1 靜態字典樹  分數:100
==========================
C++语言: Codee#25421
001 /*
002 *Problem: 網易2010“有道難題”編程挑戰賽 有道搜索框
003 *Author:Yee-fan Zhu [zyfworks@gmail.com]
004 *Method:Trie
005 */
006 #include <cstdio>
007 #include <cstdlib>
008 #include <cstring>
009 #define clr(arr,v) memset(arr,v,sizeof(arr))
010 #define readfile(str) freopen(str,"r",stdin)
011 #define writefile(str) freopen(str,"w",stdout)
012 using namespace std;
013 const int MAXN=200100;
014 const int SonNum=26;
015 const char base='a';
016 int P=0;
017 class TRIE
018 {
019 public:
020     bool isStr;
021     int Son[SonNum];
022     TRIE()
023     {
024         isStr=false;
025         clr(Son,-1);
026     }
027 }Trie[MAXN];
028
029 int Top=0;
030 void Insert(char *s)
031 {
032     int pos=0,k=0;
033     int son;
034     while(s[k])
035     {
036         son=s[k]-base;
037         if(Trie[pos].Son[son]==-1)
038             Trie[pos].Son[son]=++Top;
039         pos=Trie[pos].Son[son];
040         k++;
041     }
042     Trie[pos].isStr=true;
043 }
044 char Res[30];
045 void dfs(int k,int pos)
046 {
047     if(P>=8)
048         return;
049     if(Trie[pos].isStr)
050     {
051         Res[k]='\0';
052         printf("%s ",Res);
053         P++;
054     }
055    
056     for(int i=0;i<SonNum;i++)
057     {
058         if(Trie[pos].Son[i]==-1)
059             continue;
060         Res[k]=i+base;
061         dfs(k+1,Trie[pos].Son[i]);
062     }
063 }
064
065 void Search(char *s)
066 {
067     int pos=0,k=0;
068     while(s[k]&&pos!=-1)
069     {
070         pos=Trie[pos].Son[s[k]-base];
071         k++;
072     }
073     if(pos==-1)
074     {
075         printf("%s\n",s);
076         return;
077     }
078     P=0;
079     for(int i=0;i<k;i++)
080         Res[i]=s[i];
081     dfs(k,pos);
082     printf("\n");
083 }
084
085 void init()
086 {
087     int N,M;
088     scanf("%d\n",&N);
089     char str[30];
090     for(int i=1;i<=N;i++)
091     {
092         scanf("%s\n",&str);
093         Insert(str);
094     }
095     scanf("%d\n",&M);
096     for(int i=1;i<=M;i++)
097     {
098         scanf("%s\n",&str);
099         Search(str);
100     }
101     return;
102 }
103
104 int main()
105 {
106     readfile("youdao.in"),writefile("youdao.out");
107     init();
108     return 0;
109 }


Code.2 動態Trie樹 分數:?? 
=======================================
由於分數未知，所以僅供參考。

001 #include <cstdio>
002 #include <cstdlib>
003 #include <cstring>
004 #include <iostream>
005 #define readfile(str) freopen(str,"r",stdin)
006 #define writefile(str) freopen(str,"w",stdout)
007 using namespace std;
008
009 const int base='a';
010 const int SonNum=26;
011 const int MAXN=10001;
012 char Word[MAXN][21];
013 class Trie
014 {
015 public:
016     bool isStr;
017     int pos;
018     class Trie *Son[SonNum];
019 };
020
021 Trie *Root;
022 int Top=0;
023 int P=0;
024 int N,M;
025
026 Trie *NewTrie()
027 {
028     Trie *temp=new Trie;
029     temp->isStr=false;
030     temp->pos=0;
031     for(int i=0;i<SonNum;i++)
032         temp->Son[i]=NULL;
033     return temp;
034 }
035
036 void Insert(Trie *pnt,char *s,int len)
037 {
038     Trie *temp=pnt;
039     for(int i=0;i<len;i++)
040     {
041         if(temp->Son[s[i]-base]==NULL)
042             temp->Son[s[i]-base]=NewTrie();
043         temp=temp->Son[s[i]-base];
044     }
045     temp->isStr=true;
046     temp->pos=Top;
047 }
048
049 void dfs(Trie *pnt)
050 {
051     Trie *temp=pnt;
052     if(temp->isStr)
053     {
054         if(P==0)
055             printf("%s",Word[temp->pos]);
056         else
057             printf(" %s",Word[temp->pos]);
058         P++;
059     }
060     if(P==8)
061         return;
062     for(int i=0;i<SonNum;i++)
063     {
064         if(temp->Son[i]!=NULL)
065             dfs(temp->Son[i]);
066     }
067 }
068
069 void Search(Trie *pnt,char *s,int len)
070 {
071     Trie *temp=pnt;
072     for(int i=0;i<len;i++)
073     {
074         if(temp->Son[s[i]-base]==NULL)
075         {
076             printf("%s",s);
077             return;
078         }
079         temp=temp->Son[s[i]-base];
080     }
081    
082     P=0;
083     dfs(temp);
084 }
085
086 bool check(Trie *pnt,char *s,int len)
087 {
088     Trie *temp=pnt;
089     for (int i=0;i<len;i++)
090     {
091         if(temp->Son[s[i]-base]==NULL)
092             return false;
093         temp=temp->Son[s[i]-base];
094     }
095     return temp->isStr;
096 }
097
098 void init()
099 {
100     Root=NewTrie();
101     char str[20];
102     int len;
103     scanf("%d\n",&N);
104     for(int i=1;i<=N;i++)
105     {
106         memset(str,'\0',sizeof(str));
107         scanf("%s\n",str);
108         len=strlen(str);
109         if(check(Root,str,len))
110             continue;
111         Top++;
112         for(int i=0;i<len;i++)
113             Word[Top][i]=str[i];
114         Insert(Root,str,len);
115     }
116     scanf("%d\n",&M);
117     for(int i=1;i<=M;i++)
118     {
119         memset(str,'\0',sizeof(str));
120         scanf("%s\n",str);
121         Search(Root,str,strlen(str));
122         if(i!=M)
123             printf("\n");
124     }
125 }
126
127 int main()
128 {
129     readfile("youdao.in"),writefile("youdao.out");
130     init();
131     return 0;
132 }


Code.3 CSDN上某位神犇的紅黑樹（C++ STL）
分數：??
====================================

01 #include <iostream>
02 #include <cstdio>
03 #include <cstring>
04 #include <cmath>
05 #include <cstdlib>
06 #include <string>
07 #include <vector>
08 #include <deque>
09 #include <list>
10 #include <stack>
11 #include <queue>
12 #include <bitset>
13 #include <set>
14 #include <map>
15 #include <algorithm>
16 using namespace std;
17 class classcomp{
18 public:
19     bool operator() (string l, string r){
20         return strcmp(l.data(), r.data()) < 0;
21     }
22 };
23 int main(){
24     set<string, classcomp> dict;
25     set<string, classcomp>::iterator it;
26     string qword;
27     int n, q, cnt, found;
28     cin >> n;
29     while(n--){
30         cin >> qword;
31         dict.insert(qword);
32     }
33     cin >> q;
34     while(q--){
35         cnt = 0;
36         cin >> qword;
37         for(it = dict.lower_bound(qword); it!=dict.end(); ++it){
38             found = (*it).find(qword);
39             if(found == string::npos || found) break;
40             else{
41                 if(!cnt){
42                     cout << *it;
43                 }else{
44                     cout << ' ' << *it;
45                 }
46             }
47             ++cnt;
48             if(8 == cnt) break;
49         }
50         if(!cnt) cout << qword;
51         cout << endl;
52     }
53     return 0;
54 }
发贴者 时间： 下午2:02
标签： , ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)