[USACO 08DEC]Secret Message-白红宇

[USACO 08DEC]Secret Message

阅读量：5011 次

发布时间：2019-06-12

本文共 3469 字，大约阅读时间需要 11 分钟。

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 <= b_i <= 10,000) bits of each of M (1 <= M <= 50,000) of these secret binary messages.

He has compiled a list of N (1 <= N <= 50,000) partial codewords that he thinks the cows are using. Sadly, he only knows the first c_j (1 <= c_j <= 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.

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

信息是二进制的，共有M(1≤M≤50000)条．反间谍能力很强的约翰已经部分拦截了这些信息，知道了第i条二进制信息的前bi(l《bi≤10000)位．他同时知道，奶牛使用N(1≤N≤50000)条密码．但是，他仅仅了解第J条密码的前cj(1≤cj≤10000)位．

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

在输入文件中，位的总数（即∑Bi+∑Ci）不会超过500000.

Input

Line 1: Two integers: M and N

Lines 2..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..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

Lines 1..M: Line j: The number of messages that the jth 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

题解

题目让我们解决的问题是：一个串有多少个已知串的前缀，以及该串是多少已知串的前缀。

考虑第一个问题：我们构建一棵$Trie$树，那么这个问题的答案就是从根节点到该串末尾这条树上路径的$val$和。

考虑第二个问题：同样，容易想到，这个问题的答案是以该串末尾为根的子树的$val$和。我们在$Trie$树中插入的时候就可以做一个$pushup$操作。

1 //It is made by Awson on 2017.10.8 2 #include  3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               
                13 #include 
                
                 14 #include 
                 
                  15 #define query QUERY16 #define LL long long17 #define Max(a, b) ((a) > (b) ? (a) : (b))18 #define Min(a, b) ((a) < (b) ? (a) : (b))19 using namespace std;20 const int N = 500000;21 void read(int &x) {22 char ch; bool flag = 0;23 for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());24 for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());25 x *= 1-2*flag;26 }27 28 int m, n, b, a;29 int trie[N+5][2], top;30 int pushup[N+5], val[N+5];31 32 void insert(int b) {33 int u = 0;34 for (int i = 1; i <= b; i++) {35 read(a);36 pushup[u]++;37 if (!trie[u][a]) trie[u][a] = ++top;38 u = trie[u][a];39 }40 pushup[u]++;41 val[u]++;42 }43 int query(int b) {44 int u = 0, ans = 0;45 for (int i = 1; i <= b; i++) {46 read(a); ans += val[u];47 if (!trie[u][a]) {48 for (i++; i <= b; i++) read(a);49 return ans;50 }51 u = trie[u][a];52 }53 return ans+pushup[u];54 }55 void work() {56 read(m), read(n);57 for (int i = 1; i <= m; i++) {58 read(b); insert(b);59 }60 for (int i = 1; i <= n; i++) {61 read(b); printf("%d\n", query(b));62 }63 }64 int main() {65 work();66 return 0;67 }

转载于:https://www.cnblogs.com/NaVi-Awson/p/7638533.html

你可能感兴趣的文章