[USACO08DEC] Secret Message G

题目描述

DESCRIPTION

Bessie is leading the cows in an attempt to escape! To do this, the cows are sending secret binary messages to each other.

Ever the clever counterspy, Farmer John has intercepted the first $b_i$ ($1 \le b_i \le 10,000$) bits of each of $M$ ($1 \le M \le 50,000$) of these secret binary messages.

He has compiled a list of $N$ ($1 \le N \le 50,000$) partial codewords that he thinks the cows are using. Sadly, he only knows the first $c_j$ ($1 \le c_j \le 10,000$) bits of codeword $j$.

For each codeword $j$, he wants to know how many of the intercepted messages match that codeword (i.e., for codeword $j$, how many times does a message and the codeword have the same initial bits). Your job is to compute this number.

The total number of bits in the input (i.e., the sum of the $b_i$ and the $c_j$) will not exceed $500,000$.

INPUT FORMAT

Line $1$: Two integers: $M$ and $N$.

Lines $2 \ldots M+1$: Line $i+1$ describes intercepted code $i$ with an integer $b_i$ followed by $b_i$ space-separated 0's and 1's.

Lines $M+2 \ldots M+N+1$: Line $M+j+1$ describes codeword $j$ with an integer $c_j$ followed by $c_j$ space-separated 0's and 1's.

OUTPUT FORMAT

Lines $1 \ldots N$: Line $j$: The number of messages that the $j$-th codeword could match.

SAMPLE INPUT

4 5 
3 0 1 0 
1 1 
3 1 0 0 
3 1 1 0 
1 0 
1 1 
2 0 1 
5 0 1 0 0 1 
2 1 1

SAMPLE OUTPUT

1 
3 
1 
1 
2

HINT

Four messages; five codewords.

The intercepted messages start with 010, 1, 100, and 110.

The possible codewords start with 0, 1, 01, 01001, and 11.

0 matches only 010: $1$ match

1 matches 1, 100, and 110: $3$ matches

01 matches only 010: $1$ match

01001 matches 010: $1$ match

11 matches 1 and 110: $2$ matches

题目大意

贝茜正在领导奶牛们逃跑．为了联络，奶牛们互相发送秘密信息．

信息是二进制的，共有 $M$ ( $1 \le M \le 50000$ ) 条，反间谍能力很强的约翰已经部分拦截了这些信息，知道了第 $i$ 条二进制信息的前 $b_i$ ( $1 \le b_i \le 10000$ ) 位，他同时知道，奶牛使用 $N$ ( $1 \le N \le 50000$ ) 条暗号．但是，他仅仅知道第 $j$ 条暗号的前 $c_j$ ( $1 \le c_j \le 10000$ ) 位。

对于每条暗号 $j$，他想知道有多少截得的信息能够和它匹配。也就是说，有多少信息和这条暗号有着相同的前缀。当然，这个前缀长度必须等于暗号和那条信息长度的较小者。

在输入文件中，位的总数 ( 即 $\sum b_i + \sum c_i$ ) 不会超过 $500000$。

题解

这是一道经典的字典树统计问题

按照拦截到的信息建立 $01-Trie$ 树，并在建树的过程中统计多少条消息经过当前节点($cnt_u$)，有多少条消息截止于当前节点($end_u$)

对于每一个查询，沿着字典树向下走，将途径节点的 $end_u$ 累加，查询的过程中可能出现以下两种终止情况，(假设终止于节点 $v$)

• 如果再往下走就没有与该信息相符的节点时，说明没有比该信息长且前缀为该信息的消息，这时直接输出答案 $\sum_{u \in root \to v}{end_u}$ 即可.

• 如果询问的消息已经遍历完，那么 $cnt_u$ 包含的消息必定有与查询的消息相同的前缀，也有可能刚好在此处终结，因此在加上 $cnt_u$ 的同时还要减去 $end_u$，答案为 $\sum_{u \in root \to ed}{end_u} + (cnt_v - end_v)$.

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 500000 + 5;

int trie[N][2], cnt[N], ed[N], tot;
void insert(bool *val, int n)
{
    int u = 0;
    for (int i = 1; i <= n; i++)
    {
        int c = val[i];
        if (!trie[u][c])
            trie[u][c] = ++tot;
        u = trie[u][c];
        ++cnt[u];
    }
    ++ed[u];
}

int query(bool *val, int n)
{
    int res = 0;
    int u = 0;
    for (int i = 1; i <= n; i++)
    {
        int c = val[i];
        if (!trie[u][c])
            return res;
        u = trie[u][c];
        res += ed[u];
    }
    return res - ed[u] + cnt[u];
}

int m, n, k;
bool a[N];

int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &k);
        for (int j = 1; j <= k; j++)
            scanf("%d", &a[j]);
        insert(a, k);
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &k);
        for (int j = 1; j <= k; j++)
            scanf("%d", &a[j]);
        printf("%d\n", query(a, k));
    }
    return 0;
}