hdu3724 字典树(商品条形码)

题意：

给你一堆商品的名字，然后给你一些条形码，问你这些条形码转换成的字符串的

前缀在商品中出现的个数，条形码的每个字母是八个二进制数字，有两种数，大的是小的2倍，小的是0，大的是1，这里面的吴超是 *0.95---*1.05之间。

思路：

显然是字典树，字典树处理前缀出现次数，先把所有字符串加到树里面，然后我

们想办法吧这个二进制数字翻译成字母，其实很简单，先找到一个最大的，然后枚举每一个 int(max * 1.05 / (num[i] * 0.95)) ,如果他是1，那么当前这位是1，否则当前这位是0 ，然后转换成十进制。然后直接在树上查找就行了。

#include<stdio.h>

#include<string.h>

#include<stdlib.h>



typedef struct Tree

{

    Tree *next[26];

    int v;

}Tree;

Tree root;

void Buid_Tree(char *str)

{

    int len = strlen(str);

    Tree *p = &root ,*q;

    for(int i = 0 ;i < len ;i ++)

    {

       int id = str[i] - 'a';

       if(p -> next[id] == NULL)

       {

           q = (Tree *)malloc(sizeof(root));

           q -> v = 1;

           for(int j = 0 ;j < 26 ;j ++)

           q -> next[j] = NULL;

           p -> next[id] = q;

           p = p -> next[id];

       }

       else

       {

           p = p -> next[id];

           p -> v ++;

       }

    }

}

int Find(char *str)

{

    int len = strlen(str);

    Tree *p = &root;

    for(int i = 0 ;i < len ;i ++)

    {

        int id = str[i] - 'a';

        p = p -> next[id];

        if(p == NULL) return 0;

    }

    return p -> v;

}

int main ()

{

    int i ,n ,m ,sum;

    char str[5000];

    double num[10];

    while(~scanf("%d %d" ,&n ,&m))

    {

        for(i = 0 ;i < 26 ;i ++)

        root.next[i] = NULL;

        while(n--)

        {

           scanf("%s" ,str);

           Buid_Tree(str);

        }

        sum = 0;

        while(m--)

        {

           scanf("%d" ,&n);

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

           {

               double max = 0;

               for(int j = 1 ;j <= 8 ;j ++)

               {

                   scanf("%lf" ,&num[j]);

                   if(max < num[j]) max = num[j];

               }

               int now ,ss = 0,mk = 1;

               max = max * 1.05;

               for(int j = 8 ;j >= 1 ;j -- ,mk *= 2)

               {

                    if(int(max / (num[j] * 0.95)) == 1) now = 1;

                    else now = 0;

                    ss += now * mk;

               }

               str[i-1] = ss;

            }

            str[n] = '\0';

            sum += Find(str);

         }

     printf("%d\n" ,sum);

     }

     return 0;

}

巴特西

hdu3724 字典树(商品条形码)

最新文章

热门文章