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] = ' ';
            sum += Find(str);
         }
     printf("%d
" ,sum);
     }
     return 0;
}

hdu3724 字典树(商品条形码)

相关推荐