Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
数据测试没问题,就是WA,用Trie树写的,高手帮着看下,谢谢!!#include<iostream> #include<string> using namespace std; struct Node { Node *next[10]; bool isstring; int times; Node() { memset(next,NULL,sizeof(next)); times=0; isstring=false; } }; class Trie { private: Node *root; public: Trie() { root=new Node(); } ~Trie() { deleteTree(root); } void Insert(const char *word) { Node * location=root; while(*word!=NULL) { if(location->next[*word-'0']==NULL) { Node *temp=new Node(); location->next[*word-'0']=temp; } location=location->next[*word-'0']; word++; } location->isstring=true; location->times++; } bool search(char *word) { Node *location=root; while(*word!=NULL&&location) { location=location->next[*word-'0']; word++; } return (location!=NULL&&location->isstring); } void deleteTree(Node *root) { for(int i=0;i!=10;i++) { if(root->next[i]!=NULL) { deleteTree(root->next[i]); } } delete root; } int timescount(char *word) { Node *location=root; while(*word!=NULL&&location) { location=location->next[*word-'0']; word++; } return location->times; } }; char ans[100001][10]; int main() { int t,i,j,key; cin>>t; string s; char temp[10]; Trie tree; int index=0; int tempt=t; while(t--) { key=0; cin>>s; for(i=0;i!=s.size();i++) { if(s[i]!='-') { if(s[i]>='0'&&s[i]<='9') temp[key]=s[i]; else if(s[i]=='A'||s[i]=='B'||s[i]=='C') temp[key]='2'; else if(s[i]=='D'||s[i]=='E'||s[i]=='F') temp[key]='3'; else if(s[i]=='G'||s[i]=='H'||s[i]=='I') temp[key]='4'; else if(s[i]=='J'||s[i]=='K'||s[i]=='L') temp[key]='5'; else if(s[i]=='M'||s[i]=='N'||s[i]=='O') temp[key]='6'; else if(s[i]=='P'||s[i]=='R'||s[i]=='S') temp[key]='7'; else if(s[i]=='T'||s[i]=='U'||s[i]=='V') temp[key]='8'; else if(s[i]=='W'||s[i]=='X'||s[i]=='Y') temp[key]='9'; key++; } } temp[key]='\0'; tree.Insert(temp); strcpy(ans[index],temp); index++; } for(i=0;i!=tempt-1;i++) { key=i; for(j=i+1;j!=tempt;j++) { if(strcmp(ans[j],ans[key])<0) key=j; } if(key!=i) { char temp0[10]; strcpy(temp0,ans[key]); strcpy(ans[key],ans[i]); strcpy(ans[i],temp0); } } char temp6[10]={'*','*','*','*','*','*','*','*','*','\0'}; int key1=0; for(i=0;i!=tempt;i++) { int key5=0; if(tree.search(ans[i])) { if(strcmp(ans[i],temp6)!=0&&tree.timescount(ans[i])>1) { cout<<ans[i][0]<<ans[i][1]<<ans[i][2]<<"-"<<ans[i][3]<<ans[i][4]<<ans[i][5]<<ans[i][6]<<ans[i][7]<<" "<<tree.timescount(ans[i])<<endl; key1++; } strcpy(temp6,ans[i]); } } if(key1==0) { cout<<"No duplicates."<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator