[字符串處理][字典樹]NOIP模擬題：好感統計 star 解題報告

【问题描述】

在LazyCat同学的影响下，Roby同学开始听韩国的音乐，并且越来越喜欢H.o.T，尤其喜欢安七炫和Tony，可是，爱学习爱思考的Roby同学 想，如果以后喜欢的韩星越来越多怎么办呢？Roby怎么知道Roby最喜欢谁呢（Roby都不知道谁知道呢。。。。）？
于是，Roby同学求助于你。
Roby首先会给你一张表，表上是所有他认识的韩星的名字，一开始他对所有韩星的好感度都为0。
然后Roby会告诉你一些他对某个韩星的好感度变化。
最后，请按照Roby对他们好感从大到小的顺序输出他们。

[输入]
第一行一个个数N，表示Roby知道的韩星数目。
后面有N行，表示每一个Roby认识的韩星的名字。
再下面一行一个数K。
接下来2*K行，每两行为一组，上面一行为韩星的名字Name，下面一行为好感度变化量Change。

[输出]
N*2行，依据韩星们的受Roby好感度从大到小的顺序输出，每两行为一组，第一行输出韩星的名字，第二行输出受Roby的好感度。
[样例输入]
3
HhIsaGay
ZcLoveStudy
OneBlueOne
5
ZcLoveStudy
100
OneBlueOne
8888
ZcLoveStudy
20
OneBlueOne
8888
HhIsaGay
-1000

[样例输出]
OneBlueOne
17776
ZcLoveStudy
120
HhIsaGay
-1000
[数据范围]
对于20%的数据，保证N<=100，K<=100.
对于40%的数据，保证N<=10000，K<=30000.
对于100%的数据，保证N<=100000　-8888<=Change<=8888　K<=100000.
[时限]
2S

【分析】
 字符串處理，建議用scanf讀入，方便快速。
我用了字典樹，用來記錄每個人在數組裡的編號。最後，對數組進行快速排序，輸出人名即可和好感度即可。 

【我的代碼】
#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;
}



【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.002 s	11208 KB	0
2	正确	10	0.002 s	11208 KB	0
3	正确	10	0.035 s	11208 KB	0
4	正确	10	0.035 s	11208 KB	0
5	正确	10	0.123 s	11208 KB	0
6	正确	10	0.127 s	11208 KB	0
7	正确	10	0.123 s	11208 KB	0
8	正确	10	0.129 s	11208 KB	0
9	正确	10	0.130 s	11208 KB	0
10	正确	10	0.135 s	11208 KB	0

运行完成
运行时间 0.839 s
平均内存使用 11208 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!