Main » 2011 » November » 10 » 韩国明星后续之字典树写法！
12:52 PM 韩国明星后续之字典树写法！ | |
| C++语言: made by PaulInsider!
#include #include #include #include using namespace std; int n,m; int find(); char str[128]; int cmp(const void*a,const void *b); struct tree { int num; tree *s[128]; }; struct hehe { int mark; char st[128]; }q[100001]; int main() { freopen ("star.in","r",stdin); freopen ("star.out","w",stdout); scanf("%d\n",&n); tree *head=new tree; for (int p=0;p<128;p++) { head->s[p]=NULL; } for (int i=0;i<n;i++) { q[i].mark=0; scanf("%[^\n]\n",&q[i].st); int lq; lq=strlen(q[i].st); tree *p=new tree; p=head; for (int j=0;j<lq;j++) { if (j==lq-1) { p->num=i; break; } if (p->s[q[i].st[j]-'0']==NULL) { tree *b=new tree; for (int u=0;u<128;u++) { b->s[u]=NULL; } p->s[(q[i].st[j])-'0']=b; b=NULL; delete b; } p=p->s[q[i].st[j]-'0']; } p=NULL; delete p; } scanf("%d\n",&m); for (int i=0;i<m;i++) { char str[128]; scanf("%[^\n]\n",&str); int lw; lw=strlen(str); int tmp; scanf("%d\n",&tmp); int temp; tree *p=new tree; p=head; for (int j=0;j<lw;j++) { if(j==lw-1) { temp=p->num; } p=p->s[str[j]-'0']; } q[temp].mark+=tmp; } qsort(q,n,sizeof(q[0]),cmp); for (int i=0;i<n;i++) { cout<<q[i].st<<endl<<q[i].mark<<endl; } return 0; } int cmp(const void *a,const void *b) { struct hehe*c=(struct hehe*)a; struct hehe *d=(struct hehe*)b; return d->mark - c->mark; } | |
|
| |
| Total comments: 0 | |