| ||||||||||
| 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