Flying to the Mars HDU - 1800(字典树）

系统管理员 2023-08-17 15:41 168阅读 0赞

## Flying to the Mars HDU - 1800 ##

题目链接：[https://vjudge.net/problem/HDU-1800][https_vjudge.net_problem_HDU-1800]

题目：在8888年，地球由PPF帝国统治。随着人口的增长，PPF需要为新生儿寻找更多的土地。最后，PPF决定攻击统治火星的Kscinow。问题来了！士兵怎么能到达火星？ PPF召集他的士兵并询问他们的建议。 “匆匆......”一名士兵回答。 “闭嘴 ！我是否必须提醒你，从这里到火星没有任何道路！“PPF回复道。 “飞！”另一个答案。 PPF笑道：“聪明的家伙！虽然我们没有翅膀，但我可以从HARRY POTTER购买一些魔法扫帚来帮助你。“现在，是时候学会用扫帚飞行了！我们假设一名士兵有一个级别数字表示他的学位。具有较高等级的士兵可以教低级，也就是说前者的等级>后者。但是较低的不能教更高。一名士兵最多只能有一名教师，当然，没有老师也是合法的。同样，一名士兵最多只能有一名学生，而没有学生也是可能的。老师可以用同样的扫帚教他的学生。当然，所有的士兵都必须在扫帚上练习才能飞到火星上！魔法扫帚是昂贵的！所以，你能帮助PPF计算所需的最小扫帚数量。  
    例如 ：  
    有5名士兵（A B C D E），等级编号：2 4 5 6 4;  
    一种方法：  
    C可以教B; B可以教A;因此，A B C有资格在同一个扫帚上学习。  
    D可以教E;所以D E有资格在同一把扫帚上学习;  
    使用这种方法，我们需要2把扫帚。  
    另一种方法：  
    D可以教A;所以A D有资格在同一把扫帚上学习。  
    C可以教B;所以B C有资格在同一个扫帚上学习。  
    没有老师或学生的E有资格在一把扫帚上学习。  
    使用这种方法，我们需要3把扫帚。  
    ......  
  
    在检查了所有可能的方法后，我们发现2是所需扫帚的最小数量。  
输入  
    输入文件包含多个测试用例。  
    在测试用例中，第一行包含一个正数N，表示士兵数量。（0 <= N <= 3000）  
    接下来N行：每行只有一个非负整数，表示每个士兵的等级数。（少于30位）;  
产量  
    对于每种情况，在一条线上输出最小数量的扫帚。  
样本输入

4
    10
    20
    30
    04
    5
    2
    3
    4
    3
    4

Sample Output

1
    2
    思路：这题还可以用其他方法写，由于长度达到30位，所以用字典树写，这题很坑，有前导零，一开始没注意，所以要先去除前导零
    然后再用字典树记录每个字符串出现的次数，这里不是记录前缀了，还有re了几发，上网看其他题解才知道要释放字典树的内存。。

// 
    // Created by HJYL on 2019/8/20.
    //
    #include <iostream>
    #include <vector>
    #include <map>
    #include <string>
    #include <queue>
    #include <stack>
    #include <set>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstdlib>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    struct trie{
        trie* next[50];
        int sum;
    }*root;
    trie* build()
    {
        trie *T=(trie *)malloc(sizeof(trie));
        T->sum=0;
        for(int i=0;i<10;i++)
            T->next[i]=NULL;
        return T;
    }
    int maxx;
    void insert(char* s)
    {
        trie* p=root;
        for(int i=0;s[i];i++)
        {
            if(p->next[s[i]-'0']==NULL)
            {
                p->next[s[i]-'0']=build();
            }
            p=p->next[s[i]-'0'];
        }
        p->sum++;
        if(p->sum>maxx)
            maxx=p->sum;
    }
    void  delete_tri(trie *T)//释放字典树
    {
        if(T!=NULL)
        {
            for(int i=0;i<10;i++)
            {
                if(T->next[i]!=NULL)
                    delete_tri(T->next[i]);
            }
    
        }
        free(T);
        T=NULL;
    }
    int main() {
        //freopen("C:\\Users\\asus567767\\CLionProjects\\untitled\\text", "r", stdin);
        int T;
        char str[50];
        while (~scanf("%d", &T)) {
            root=build();
            maxx=0;
                for (int i = 0; i < T; i++) {
                    scanf("%s", str);
                    int j=0;
                    while(str[j]=='0')
                        j++;
                    insert(str+j);
                }
                if(maxx==0)
                    maxx=1;
            printf("%d\n", maxx);
            delete_tri(root);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11385734.html

[https_vjudge.net_problem_HDU-1800]: https://vjudge.net/problem/HDU-1800