Secret Message 秘密信息

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1628 字

Trie 记结尾数与子树数统计前缀匹配

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1476
// 题意：先给 N 条二进制信息，再给 M 条密码；对每条密码统计有多少条信息与它「前 min(两者长度) 位相同」。
// 思路：信息建 Trie，结点记 endCnt（在此结束的信息数）和 subCnt（经过此结点的信息数）。走密码时把沿途结点的 endCnt 累加；若密码能完整走完，再补上终点的 subCnt-endCnt（以密码为前缀的更长信息）。
// 复杂度：O(总位数) 时间 / O(总位数) 空间
// 易错点：中途走不下去时要立刻停止并且不能补 subCnt-endCnt，走不下去说明下一位就分叉了，那些更长的信息并不匹配。
// 易错点：输入是先 N 条信息再 M 条密码，不要按 M 条密码在前读取。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[2];
    int endCnt;
    int subCnt;
    Node(){
        ch[0] = ch[1] = 0;
        endCnt = 0;
        subCnt = 0;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    if(!(cin >> N >> M)) return 0;
    vector<Node> tr;
    tr.push_back(Node());
    for(int i = 0; i < N; i++){
        int b;
        cin >> b;
        int u = 0;
        tr[u].subCnt++;
        for(int j = 0; j < b; j++){
            int x;
            cin >> x;
            if(!tr[u].ch[x]){
                tr[u].ch[x] = (int)tr.size();
                tr.push_back(Node());
            }
            u = tr[u].ch[x];
            tr[u].subCnt++;
        }
        tr[u].endCnt++;
    }
    for(int i = 0; i < M; i++){
        int c;
        cin >> c;
        int u = 0;
        int ans = 0;
        bool ok = true;
        for(int j = 0; j < c; j++){
            int x;
            cin >> x;
            if(!ok) continue;
            if(!tr[u].ch[x]){
                ok = false;
                continue;
            }
            u = tr[u].ch[x];
            ans += tr[u].endCnt;
        }
        if(ok) ans += tr[u].subCnt - tr[u].endCnt;
        cout << ans << "\n";
    }
    return 0;
}

Secret Message 秘密信息

正文

一本通·提高篇的其它内容