首页 > ACM题库 > HDU-杭电 > HDU 1761 Spring-outing Decision(2)-字典树-[解题报告] c-sharp
2013
12-23

HDU 1761 Spring-outing Decision(2)-字典树-[解题报告] c-sharp

Spring-outing Decision(2)

问题描述 :

历经千辛万苦,ACgirl 终于定好了时间,在那一天,她们班全班的人都有时间去春游。
正当 ACgirl 以为春游的安排就这样搞定的时候,又出现了一个新的问题。
原来,她们班的同学并不是很和睦,而是分裂成一个个小团体。

对每个人来说,都有喜欢和讨厌的人。当有他喜欢的人去春游时,他就会跟着他一起去。反之,当有他讨厌的人去春游时,他则不会去春游。而去春游的人当中既有他喜欢的人又有他讨厌的人 或者 既没他喜欢的人也没他讨厌的人的时候,他就会保持自己最近的决定。

现在,身为辅导员的 ACgirl 正在统计人数。她按下面这样的方法统计人数。刚开始,她有一张初始的名单,这张名单里记录着一开始就要去春游的人。然后,她拿出一张白纸,把上次的要去春游人的名单给每个同学看,并且记录下现在要去春游的人。她重复该步骤 M 次。

现在 ACgirl 又需要你帮忙了,她想知道她做了这M次询问以后,最后去春游的都有谁。

输入:

本题目包含多组测试,请处理到文件结束。
每组测试第一行包含两个正整数N和M(N,M<=100)。其中N表示ACgirl班里一共有多少人,M表示ACgirl一共做了多少次询问。
接下来给出这N个学生的信息。
每个学生的信息的第一行是这个学生的名字(长度不大于20,均由小写字母构成)。
第二行刚开始有一个正整数 P (P < N) ,表示这个学生有多少个喜欢的人,这一行接下来有 P 个名字,表示他所喜欢的人。
第三行刚开始有一个正整数 Q (Q < N),表示这个学生有多少个讨厌的人,这一行接下来有 Q 个名字,表示他讨厌的人。
在每个测试的最后一行,会给出初始决定去春游的名单。
同样,先有一个正整数 R ( R < N ) , 表示初始要去的人数,接下来给出这 R 个人的姓名。

输入数据保证,同一个班里不会出现两个名字相同的人,一个人也不会既喜欢,又恨一个人,当然,他也不会喜欢或讨厌自己。同样,在初始名单里,不会出现两个重复的名字。

输出:

对于每组测试,请在一行里面请按字典序输出经过 M 次询问,最后决定要去春游的人的名字。
两个名字之间用一个空格分开。
如果最后没有一个人去春游,请输出"None"(不带引号)。

样例输入:

4 1
a
1 b
1 c
b
1 a
1 c
c
1 a
1 d
d
1 b
1 a
2 a d

样例输出:

a b

#include <iostream>
#include <algorithm>
using namespace std;
#define N 105

struct elem 
{
    char name[25];
    int tnum,xnum;
    char tname[N][25];
    char xname[N][25];
}stu[N];

struct trie 
{
    int end;
    int count;
    trie *next[26];
};

trie *root;
char add_str[N][25];
char del_str[N][25];
int len_add,len_del;

int cmp(elem a,elem b)
{
    return strcmp(a.name,b.name)<0?1:0;
}

trie* newtrie()   
{   
    trie *t;   
    t=(trie*)malloc(sizeof(struct trie));   
    memset(t,0,sizeof(struct trie));   
    return t;   
}

void insert(char *ch)   
{   
    int i;   
    trie *t,*s;   
    s=root;   
    for(i=0;ch[i];i++)   
    {   
        if(s->next[ch[i]-'a'])   
        {   
            s=s->next[ch[i]-'a'];   
            s->count=s->count+1;   
        }   
        else  
        {   
            t=newtrie();   
            s->next[ch[i]-'a']=t;   
            s=t;   
            s->count=1;   
        }   
    }   
	s->end = 1;
} 

int search(char *ch)   
{   
    int i;   
    trie *s=root;   
    if(ch[0]==0) return 0;   
    for(i=0;ch[i];i++)   
    {   
        if(s->next[ch[i]-'a'])      
            s=s->next[ch[i]-'a'];      
        else  
            break;   
    }  
    if(ch[i]==0 && s->end == 1) return s->count;   
    else return 0;   
} 

void Delete(char *ch)   
{   
    int i;   
    trie *s;   
    s=root;   
    for(i=0;ch[i];i++)   
    {   
        s=s->next[ch[i]-'a'];
        s->count=s->count-1;
    }   
	s->end = 0;
} 

int main()
{
    int n,m,k,i,j,ttt;
    char ch[25];
    while (scanf("%d %d",&n,&m)!=EOF)
    {
        root = newtrie();
        getchar();
        for(i=0;i<n;i++)
        {
            scanf("%s",stu[i].name);
            scanf("%d",&stu[i].tnum);
            getchar();
            for(j=0;j<stu[i].tnum;j++)
                scanf("%s",stu[i].tname[j]);
            scanf("%d",&stu[i].xnum);
            getchar();
            for (j=0;j<stu[i].xnum;j++)
                scanf("%s",stu[i].xname[j]);
        }
        scanf("%d",&k);
        getchar();
        for(i=0;i<k;i++)
        {
            scanf("%s",ch);
            insert(ch);
        }
        int flag1,flag2;
        while (m--)
        {
            len_add = 0;
            len_del = 0;
            for(i=0;i<n;i++)
            {
                for(j=0;j<stu[i].tnum;j++)
                {
                    flag1 = search(stu[i].tname[j]);
					if(flag1 !=0)
						break;
                }
                for (j=0;j<stu[i].xnum;j++)
                {
                    flag2 = search(stu[i].xname[j]);
					if(flag2 !=0)
						break;
                }
                if(flag1 !=0 && flag2 == 0)
                {
                    strcpy(add_str[len_add],stu[i].name);
                    len_add++;
                }
                else if(flag1 == 0 && flag2 != 0)
                {
                    strcpy(del_str[len_del],stu[i].name);
                    len_del++;
                }
            }
            for(i=0;i<len_add;i++)
            {
                if(search(add_str[i]) == 0)
                    insert(add_str[i]);
            }
            for(i=0;i<len_del;i++)
            {
                if(search(del_str[i]) != 0)
                    Delete(del_str[i]);
            }
        }
        sort(stu,stu+n,cmp);
        ttt=0;
        for(i=0;i<n;i++)
        {
            if(search(stu[i].name) != 0)
            {
                if(ttt>0)
                    printf(" ");
                ttt++;
                printf("%s",stu[i].name);
            }
        }
        if(ttt==0)
            printf("None");
        printf("/n");
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/xiaotaoqibao/article/details/5804827