Tire树入门专题

POJ 3630Phone List

题意：问是否有号码是其他号码的前缀。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<map>

 using namespace std;

 const int N=1e5+;

 struct Tire

 {

     int T[N][];

     int sum[N];

     int cou;

     void init()

     {

         cou=;

         memset(T,,sizeof(T));

         memset(sum,,sizeof(sum));

     }

     void Insert(char *s)

     {

         int h=,i,n=strlen(s);

         for(i=; i<n; i++)

         {

             if(T[h][s[i]-'']==)

                 T[h][s[i]-'']=cou++;

             h=T[h][s[i]-''];

         }

         sum[h]++;

     }

     int ask(char *s)

     {

         int h=,i=,n=strlen(s);

         for(i=; i<n-; i++)

         {

             if(T[h][s[i]-''])

             {

                 h=T[h][s[i]-''];

                 if(sum[h]>) return ;

             }

             else return ;

         }

         return ;

     }

 } tire;

 char s[][];

 int main()

 {

     int i,T,n;

     scanf("%d",&T);

     while(T--)

     {

         int ans=;

         scanf("%d",&n);

         getchar();

         tire.init();

         for(i=; i<n; i++)

         {

             scanf("%s",s[i]);

             getchar();

             tire.Insert(s[i]);

         }

         for(i=; i<n; i++)

             if(tire.ask(s[i])) ans=;

         if(ans==) cout<<"NO"<<endl;

         else cout<<"YES"<<endl;

     }

     return ;

 }

POJ 3630

HDU 1251统计难题

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1251

题意：统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=5e5+;

struct Tire

{

    int T[N][],sum[N];

    int cou;

    void Init()

    {

        cou=;

        memset(T,,sizeof(T));

        memset(sum,,sizeof(sum));

    }

    void Insert(char *s)

    {

        int i,h=,n=strlen(s);

        for(i=; i<n; i++)

        {

            if(T[h][s[i]-'a']==)

                T[h][s[i]-'a']=cou++;

            h=T[h][s[i]-'a'];

            sum[h]++;

        }

    }

    int ask(char *s)

    {

        int i,h=,n=strlen(s);

        for(i=; i<n; i++)

        {

            if(T[h][s[i]-'a']!=) h=T[h][s[i]-'a'];

            else return ;

        }

        return sum[h];

    }

} tire;

int main()

{

    char s[];

    tire.Init();

    while(gets(s))

    {

        if(strlen(s)==) break;

        tire.Insert(s);

    }

    while(scanf("%s",s)!=EOF)

    {

        cout<<tire.ask(s)<<endl;

    }

    return ;

}

HDU 1251

HDU 1004Let the Balloon Rise

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1004

题意：输出颜色数量最多的一种颜色。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=+;

struct Tire

{

    int T[N][],sum[N];

    int cou;

    void Init()

    {

        cou=;

        memset(T,,sizeof(T));

        memset(sum,,sizeof(sum));

    }

    int Insert(char *s)

    {

        int i,h=,n=strlen(s);

        for(i=; i<n; i++)

        {

            if(T[h][s[i]-'a']==)

                T[h][s[i]-'a']=cou++;

            h=T[h][s[i]-'a'];

        }

        sum[h]++;

        return sum[h];

    }

} tire;

int main()

{

    int n;

    char s[],ans[];

    while(scanf("%d",&n)!=EOF)

    {

        if(n==) break;

        tire.Init();

        int Max=;

        while(n--)

        {

            getchar();

            scanf("%s",s);

            int x=tire.Insert(s);

            if(x>Max)

            {

                Max=x;

                strcpy(ans,s);

            }

        }

        printf("%s\n",ans);

    }

    return ;

}

HDU 1004

HDU 4825Xor Sum

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4825

题意：在集合当中找出一个正整数 K ，使得 K 与 S 的异或结果最大。

思路：尽量使得K的高位与S的高位不同。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=3e6+;

struct Tire

{

    int T[N][],sum[N];

    int cou;

    void Init()

    {

        cou=;

        memset(T,,sizeof(T));

        memset(sum,,sizeof(sum));

    }

    void Insert(int num)

    {

        int i=,h=;

        for(i=; i>=; i--)

        {

            if(T[h][(num>>i)&]==)

                T[h][(num>>i)&]=cou++;

            h=T[h][(num>>i)&];

        }

        sum[h]=num;

    }

    int ask(int num)

    {

        int i=,h=;

        for(i=; i>=; i--)

        {

            int x=(num>>i)&,sign=;

            if(x==) sign=;

            if(T[h][sign]) h=T[h][sign];

            else h=T[h][x];

        }

        return sum[h];

    }

} tire;

int main()

{

    int n,m;

    int t,T;

    scanf("%d",&T);

    for(t=; t<=T; t++)

    {

        tire.Init();

        scanf("%d%d",&n,&m);

        int num;

        while(n--)

        {

            scanf("%d",&num);

            tire.Insert(num);

        }

        printf("Case #%d:\n",t);

        while(m--)

        {

            scanf("%d",&num);

            cout<<tire.ask(num)<<endl;

        }

    }

    return ;

}

HDU 4825

巴特西

Tire树入门专题

最新文章

热门文章