首页 > 代码库 > 2012年湖南省程序设计竞赛E题 最短的名字

2012年湖南省程序设计竞赛E题 最短的名字

2024-07-04 01:04:32   224人阅读

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1115

解题报告：输入n个字符串，让你求出可以用来区别这些字符串的最少的前缀总共有多少个字母。可以区别是指每个字符串都取一个自己的前缀，同时保证所有取的这些前缀没有完全相同。

这题用字典树可以做，就是输入的时候把所有的字符串都插入到字典树中，最后把所有被走过不止一次的节点的值都加起来，每个节点的值表示这个节点被走过多少次，然后如果碰到这个节点的值是1的时候总和加1，同时要退出，后面的就不用统计了，因为这个节点只被走过一次，所以经过这个节点的那个字符串到这里已经是唯一的了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<deque>
#include<map>
#include<queue>
#include<cstdlib>
using namespace std;
const int maxn = 1005;
char temp[1000005];
int ans;
typedef struct node
{
    node* ch[26];
    int tot;
}*Linklist;
void Init(Linklist& p)
{
    p->tot = 0;
    for(int i = 0;i < 26;++i)
    p->ch[i] = NULL;
}
void push(Linklist p,char* str,int f,int len)
{
    if(f >= len)
    return ;
    if(p->ch[str[f]-‘a‘] == NULL)
    {
        p->ch[str[f]-‘a‘] = new node;
        Init(p->ch[str[f]-‘a‘]);
        p->ch[str[f]-‘a‘]->tot++;
        p = p->ch[str[f]-‘a‘];
    }
    else
    {
        p->ch[str[f]-‘a‘]->tot++;
        p = p->ch[str[f]-‘a‘];
    }
    push(p,str,f+1,len);
}

void get_tot(Linklist p)
{
    if(p == NULL || p->tot == 1)
    {
        if(p != NULL && p->tot == 1) ans++;
        return ;
    }
    else ans += p->tot;
    for(int i = 0;i < 26;++i)
    get_tot(p->ch[i]);
}
void clean(Linklist p)
{
    if(p == NULL)
    return ;
    for(int i = 0;i < 26;++i)
    if(p->ch[i] != NULL)
    clean(p->ch[i]);
    delete p;
}
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        Linklist head = new node;
        Init(head);
        for(int i = 0;i < n;++i)
        {
            scanf("%s",temp);
            push(head,temp,0,strlen(temp));
        }
//        printf("%d %d %d %d\n",head->ch[0]->tot,head->ch[0]->ch[0]->tot,head->ch[0]->ch[1]->tot,head->ch[1]->tot);
        ans = 0;
        for(int i = 0;i < 26;++i)
        get_tot(head->ch[i]);
        printf("%d\n",ans);
        clean(head);
    }
    return 0;
}
View Code

 


联系
我们