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 |
AC用字典树做的,不过效果不太好1325MS#include<iostream> #include<string> #include<algorithm> using namespace std; #define max 100005 struct node { int v; int temp; struct node*next[10]; }; struct node*newnode() { struct node*r; r=new struct node; r->v=r->temp=0; int i; for(i=0;i<10;i++) r->next[i]=NULL; return r; } int insert(struct node*root,string str) { int i; struct node *r,*s; r=root; int flag=0; for(i=0;i<str.length();i++) { if(str[i]=='-')continue; if(r->next[str[i]-'0']==NULL) { s=newnode(); s->v=1; r->next[str[i]-'0']=s; r=s; } else { r=r->next[str[i]-'0']; r->v++; flag++; } } r->temp=1; if(flag==7)return 1; return 0; } int search(struct node*root,string str) { struct node*r; r=root; int i; for(i=0;i<str.length();i++) { if(str[i]=='-')continue; r=r->next[str[i]-'0']; } return r->v; } struct ca { char str[100]; int sum; }s[max]; int cmp(struct ca a,struct ca b) { if(strcmp(a.str,b.str)==-1) return 1; return 0; } char match[26]={"222333444555666777888999"}; int main() { int n; cin>>n; struct node*root; root=newnode(); int i=0; while(n--) { char temp[100]; scanf("%s",temp); int L=strlen(temp); int k=0; int j; for(j=0;j<L;j++) { if(temp[j]=='Z'||temp[j]=='Q'||temp[j]=='-') continue; else if(temp[j]<'Q'&&temp[j]>='A') s[i].str[k]=match[(temp[j]-'A')]; else if(temp[j]>'Q'&&temp[j]<='Z') s[i].str[k]=match[temp[j]-'A'-1]; else s[i].str[k]=temp[j]; k++; if(k==3) {s[i].str[k]='-';k++;} } s[i].str[k]='\0';k++; if(!insert(root,s[i].str)){i++;} } sort(s,s+i,cmp); int tag=0;int j; for(j=0;j<i;j++) { int t=search(root,s[j].str); if(t>=2) { tag=1; printf("%s %d\n",s[j].str,t); } } if(!tag)printf("No duplicates.\n"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator