題意：
? ? ?給你一堆商品的名字，然后給你一些條形碼，問你這些條形碼轉(zhuǎn)換成的字符串的
前綴在商品中出現(xiàn)的個數(shù)，條形碼的每個字母是八個二進制數(shù)字，有兩種數(shù)，大的是小的2倍，小的是0，大的是1，這里面的吳超是 *0.95---*1.05之間。

思路：
? ? ? 顯然是字典樹，字典樹處理前綴出現(xiàn)次數(shù)，先把所有字符串加到樹里面，然后我

們想辦法吧這個二進制數(shù)字翻譯成字母，其實很簡單，先找到一個最大的，然后枚舉每一個 int(max * 1.05 / (num[i] * 0.95)) ,如果他是1，那么當前這位是1，否則當前這位是0 ，然后轉(zhuǎn)換成十進制。然后直接在樹上查找就行了。

#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; }

總結(jié)

以上是生活随笔為你收集整理的hdu3724 字典树(商品条形码)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。