记录编号	33390	评测结果	AAAAAAAAAA
题目名称	韩国明星	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.882 s
提交时间	2011-11-10 15:11:52	内存使用	10.95 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
int N,K;

const int sonnum=127;
const char base=0; 
struct Trie 
{ 
    bool isStr;
	int Num;
    struct Trie *son[sonnum];
}; 

Trie *Tree;
int Suki[100001];

class NUM
{
public:
	int n;
	int Suki;
	char str[100];
	NUM()
	{
		Suki=0;
	}
}Su[100001];

int top=0;

Trie *NewTrie()
{ 
    Trie *temp=new Trie; 
    temp->isStr=false; 
	temp->Num=0;
    for (int i=0;i<sonnum;i++) 
        temp->son[i]=NULL;
    return temp; 
} 

void Insert(Trie *pnt,char *s,int len)
{                              
	top++;
	Su[top].n=top;
	Su[top].Suki=0;
	for (int i=0;i<len;i++)
		Su[top].str[i]=s[i];
	
    Trie *temp=pnt; 
    for (int i=0;i<len;i++) 
    { 
        if (temp->son[s[i]-base]==NULL) 
            temp->son[s[i]-base]=NewTrie(); 
        temp=temp->son[s[i]-base]; 
    } 
    temp->isStr=true; 
	temp->Num=top;
} 

void check(Trie *pnt,char *s,int len,int change) 
{ 
    Trie *temp=pnt; 
    for (int i=0;i<len;i++) 
		temp=temp->son[s[i]-base]; 
    Su[temp->Num].Suki+=change; 
} 

int cmp(const void *a,const void *b)
{
	class NUM *c=(class NUM *)a;
	class NUM *d=(class NUM *)b;
	return d->Suki-c->Suki;
	return 0;
}

void init()
{
	Tree=NewTrie();
	char str[100];
	scanf("%d\n",&N);
	for (int i=1;i<=N;i++)
	{
		memset(str,'\0',sizeof(str));
		scanf("%[^\n]\n",&str);
		Insert(Tree,str,strlen(str));
	}
	scanf("%d\n",&K);
	int tmp;
	for (int i=1;i<=K;i++)
	{
		memset(str,'\0',sizeof(str));
		scanf("%[^\n]\n",&str);
		scanf("%d\n",&tmp);
		check(Tree,str,strlen(str),tmp);
	}
	qsort(Su+1,top,sizeof(Su[0]),cmp);
	
	for (int i=1;i<=top;i++)
	{
		printf("%s\n%d\n",Su[i].str,Su[i].Suki);
	}
}

int main()
{
	freopen("star.in","r",stdin);
	freopen("star.out","w",stdout);
	init();
	return 0;
}