HDU - 3724 Encoded Barcodes （字典树）

题意：给定n个字符串和m个经过处理得到的字符串，问对于m个字符串中的每个字符串，n个字符串中以该字符串为前缀的个数。
分析：
1、误差在[0.95x, 1.05x]，因此求8个数的平均数，大于平均数为1，否则为0。
2、字典树求前缀个数。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<string>

#include<iostream>

#include<set>

#include<map>

#include<stack>

#include<queue>

#include<vector>

#include<sstream>

typedef long long LL;

const int INF = 0x3f3f3f3f;

using namespace std;

const int MAXN = 1000000 + 10;

const double eps = 1e-8;

int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a < b ? -1 : 1;

}

struct Trie{

    int val;

    Trie *nex[26];

    Trie(){

        val = 0;

        for(int i = 0; i < 26; ++i) nex[i] = NULL;

    }

};

void build(string x, Trie *root){

    int len = x.size();

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

        int cur = x[i] - 'a';

        if(root -> nex[cur] == NULL){

            root -> nex[cur] = new Trie();

        }

        root = root -> nex[cur];

        ++root -> val;

    }

}

int query(string x, Trie *root){

    int len = x.size();

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

        int cur = x[i] - 'a';

        if(root -> nex[cur] == NULL) return 0;

        root = root -> nex[cur];

    }

    return root -> val;

}

int POW[10];

void init(){

    POW[0] = 1;

    for(int i = 1; i <= 7; ++i){

        POW[i] = POW[i - 1] * 2;

    }

}

int main(){

    int N, M;

    init();

    while(scanf("%d%d", &N, &M) == 2){

        string s;

        Trie *root = new Trie();

        for(int i = 0; i < N; ++i){

            cin >> s;

            build(s, root);

        }

        int K;

        int ans = 0;

        while(M--){

            scanf("%d", &K);

            s = "";

            while(K--){

                double ave = 0;

                double a[10];

                for(int i = 0; i < 8; ++i){

                    scanf("%lf", &a[i]);

                    ave += a[i];

                }

                ave /= 8;

                int x = 0;

                for(int i = 0; i < 8; ++i){

                    if(a[i] > ave){

                        x += POW[7 - i] * 1;

                    }

                }

                s += x - 97 + 'a';

            }

            ans += query(s, root);

        }

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

    }

    return 0;

}