[USACO08DEC] Secret Message G

GitHub跳转原题关系图返回列表

二进制 Trie 同时记录终止数量和子树数量，统计两串中较短者为公共前缀的消息数。

OJ: luogu

题目 ID: P2922

难度:普及+/提高

标签:Trie前缀计数python

日期: 2026-07-16 19:57

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

对每条暗号，统计有多少消息与它从第一位开始相同，直到两者中较短的一条结束。

思路

把所有消息插入二进制 Trie。每个节点记录：

  • terminal_count：恰好在此结束的消息数；
  • subtree_count：经过此节点的消息数。

查询暗号时，沿路径每下降一层前，把当前节点终止的消息加入答案，它们是暗号的前缀。若暗号整条路径存在，最后再加当前节点的子树数，它们以暗号为前缀。两部分不会重复。

Python 知识

  • 只有 0/1 两条边，使用 child_zero、child_one 两个 array("i") 比节点字典更紧凑。
  • 下标 0 统一表示不存在的儿子。
  • 查询位先读成列表，即使 Trie 提前失配，也已经正确消耗本行输入。
  • for ... else 的 else 只在循环没有 break 时执行，正好处理“暗号完整走完”。

代码

python
import sys
from array import array


data = iter(map(int, sys.stdin.buffer.read().split()))
message_count, query_count = next(data), next(data)
child_zero = array("i", [0])
child_one = array("i", [0])
subtree_count = array("i", [0])
terminal_count = array("i", [0])

for _ in range(message_count):
    node = 0
    for _ in range(next(data)):
        children = child_one if next(data) else child_zero
        if not children[node]:
            children[node] = len(child_zero)
            child_zero.append(0)
            child_one.append(0)
            subtree_count.append(0)
            terminal_count.append(0)
        node = children[node]
        subtree_count[node] += 1
    terminal_count[node] += 1

answers = []
for _ in range(query_count):
    bits = [next(data) for _ in range(next(data))]
    node = answer = 0
    for bit in bits:
        answer += terminal_count[node]
        node = (child_one if bit else child_zero)[node]
        if not node:
            break
    else:
        answer += subtree_count[node]
    answers.append(str(answer))

print("\n".join(answers))

复杂度

时间和空间均为所有消息与暗号总位数的 O(L)O(L)。

总结

这类“较短串必须是较长串前缀”的计数，需要同时统计路径上的终止串和终点下方的更长串。