题目很简单，给出一个字典，再给一些串，查询这些串是否在字典中。
如果对字典排序后用二分查找，时间复杂度为O(N*logN)，由于题目没有给出字典大小，这个界也不好估计。不过我用排序+二分TLE了。
下面是用Hash Table实现的算法，空间复杂度会高些（因为Hash表要很大的空间，来使得key分散开），但每次插入跟查询的时间几乎是O(1)，所以93ms就能AC。
1 #include <iostream>
2 #include <list>
3 #include <string>
4 #include <algorithm>
5
6 using namespace std;
7 const int maxn=50000;
8 struct node{
9 int idx;
10 node *next;
11 }htable[maxn];
12
13 //node *htable[maxn];
14 char dic[maxn][200];
15
16 unsigned long hash(char *key)
17 {
18 unsigned long h = 0;
19 while(*key)
20 {
21 h = (h << 4) + *key++;
22 unsigned long g = h & 0xf0000000L;
23 if(g)
24 h ^= g >> 24;
25 h &= ~g;
26 }
27 return h % maxn;
28 }
29
30 void insert(char *key,int idx)
31 {
32 unsigned long i=hash(key);
33 node *cur=htable[i].next;
34 node *pre=&htable[i];
35 while(cur!=NULL && strcmp(dic[cur->idx],key)!=0) {pre=cur;cur=cur->next;}
36 // 将新的key加入到hash table中
37 if(cur==NULL){
38 node *a=new node();
39 a->idx=idx;
40 a->next=NULL;
41 pre->next=a;
42 }
43 }
44
45 bool search(char *key)
46 {
47 unsigned long i=hash(key);
48 node *cur=htable[i].next;//,*pre=NULL;
49 while(cur!=NULL && strcmp(dic[cur->idx],key)!=0) {cur=cur->next;}
50 if(cur==NULL) return false;
51 return true;
52 }
53
54 int main()
55 {
56 //freopen("in.txt","r",stdin);
57 char s[200];
58 int i,j,k,n;
59 scanf("%d",&n);
60
61 // initialization
62 for(i=0;i<maxn;i++) htable[i].next=NULL;
63 // 插入数据
64 for(i=0;i<n;i++){
65 getchar();
66 scanf("%s",s);
67 strcpy(dic[i],s);
68 insert(s,i);
69 }
70
71 scanf("%d",&n);
72 for(i=0;i<n;i++){
73 int flag=0;
74 while(true){
75 scanf("%s",s);
76 if(strcmp(s,"-1")==0) break;
77 if(!search(s)){
78 if(flag==0){
79 printf("Email %d is not spelled correctly.\n",i+1);
80 flag=1;
81 }
82 printf("%s\n",s);
83 }
84 }
85 if(flag==0) printf("Email %d is spelled correctly.\n",i+1);
86 }
87 printf("End of Output\n");
88 return 1;
89 }
这是超时的版本，用了list的STL跟binary_search函数来查找。但超时可能是因为用C++的STL和输入输出，因为Discuss中有人用快排+二分过的。
1 list<string> dic;//=new list<string>(51000);
2 char tmp[200];
3 int main()
4 {
5 int i,j,k,n;
6 string s;
7 scanf("%d",&n);
8 for(i=0;i<n;i++) {getchar();scanf("%s",tmp);dic.push_back(new string(tmp));}
9 //dic.insert("anc");
10 //sort(dic.begin(),dic.end());
11 dic.sort();
12 for(list<string>::iterator it=dic.begin();it!=dic.end();it++) cout<<(*it)<<endl;
13 scanf("%d",&n);
14 for(i=0;i<n;i++){
15 int flag=1;
16 while(cin>>s && s!="-1"){
17 if(!binary_search(dic.begin(),dic.end(),s)){
18 if(flag==1){
19 printf("Email %d is not spelled correctly.\n",i+1);
20 flag=0;
21 }
22 cout<<s<<endl;
23 }
24 }
25 if(flag==1) printf("Email %d is spelled correctly.\n",i+1);
26 }
27 printf("End of Output\n");
28 return 1;
29 }