洛谷 P2922 [USACO08DEC] Secret Message G

// P2922 [USACO08DEC] Secret Message G —— 正解：Trie，**本章那两个计数第一次同时登场**
//
// ★ 题面那句「前缀长度必须等于暗号和那条信息长度的**较小者**」，拆开就是两种情形：
//
//     ① 信息比暗号**短**（或一样长）⇒ 信息是暗号的前缀
//        ⇒ 它在暗号那条路上的**某个节点上结束** ⇒ 沿途把 cntEnd 加起来。
//     ② 信息比暗号**长**            ⇒ 暗号是信息的前缀
//        ⇒ 它**路过**暗号的终点 ⇒ 那就是 cntPass[终点]。
//
//   ⚠⚠ 而 cntPass[终点] 里**也包含**「正好在终点结束」的那些信息 ——
//     它们在第 ① 步已经数过一遍了。⇒ **必须减掉 cntEnd[终点]**，否则重复计数。
//
//   ⇒ ans = Σ(沿途每个节点的 cntEnd) + cntPass[终点] − cntEnd[终点]
//
// ⚠ 还有一处：暗号走到一半**没路了**，说明没有任何信息以它为前缀
//   ⇒ 情形 ② 一个都没有，只能拿已经累加的那部分 —— **不能再加 cntPass**。

#include <bits/stdc++.h>
using namespace std;

/* 节点数上限 = 所有信息的总位数 + 1；题面：Σb + Σc ≤ 5×10⁵ */
const int MAXN = 500005;

int ch[MAXN][2];
int cntPass[MAXN];       // 有多少条信息**路过**这个节点
int cntEnd[MAXN];        // 有多少条信息正好在这个节点**结束**
int tot;

void insertMsg(const vector<int>& b) {
    int u = 0;
    for (size_t i = 0; i < b.size(); i++) {
        int k = b[i];
        if (!ch[u][k]) ch[u][k] = ++tot;
        u = ch[u][k];
        cntPass[u]++;
    }
    cntEnd[u]++;
}

int askCode(const vector<int>& c) {
    int u = 0;
    long long ans = 0;
    bool full = true;
    for (size_t i = 0; i < c.size(); i++) {
        int k = c[i];
        if (!ch[u][k]) { full = false; break; }      // ⚠ 走不下去 ⇒ 没有更长的信息了
        u = ch[u][k];
        ans += cntEnd[u];                            // ① 比暗号短（或一样长）的那些
    }
    if (full) ans += cntPass[u] - cntEnd[u];         // ② 比暗号长的那些（⚠ 减掉重复的）
    return (int)ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    if (!(cin >> m >> n)) return 0;
    for (int i = 0; i < m; i++) {
        int b;
        cin >> b;
        vector<int> v(b);
        for (int j = 0; j < b; j++) cin >> v[j];
        insertMsg(v);
    }
    for (int i = 0; i < n; i++) {
        int c;
        cin >> c;
        vector<int> v(c);
        for (int j = 0; j < c; j++) cin >> v[j];
        cout << askCode(v) << '\n';
    }
    return 0;
}

// P2922 的两笔账：Trie 有多少个节点，两条路各做多少次基本动作
//
// 用法：./p2922Count <csv|table> < 一份输入

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";

    int m, n;
    if (scanf("%d %d", &m, &n) != 2) return 0;
    vector<string> msg(m), code(n);
    auto readBits = [](int cnt) {
        string s;
        s.reserve(cnt);
        for (int j = 0; j < cnt; j++) { int x; if (scanf("%d", &x) != 1) return s; s += (char)('0' + x); }
        return s;
    };
    long long bBits = 0, cBits = 0;
    for (int i = 0; i < m; i++) { int b; if (scanf("%d", &b) != 1) return 0; msg[i] = readBits(b); bBits += b; }
    for (int i = 0; i < n; i++) { int c; if (scanf("%d", &c) != 1) return 0; code[i] = readBits(c); cBits += c; }

    /* ① Trie 节点数 = 所有信息的不同前缀个数 */
    long long nodes = 0;
    {
        vector<string> v(msg);
        sort(v.begin(), v.end());
        string prev;
        for (size_t i = 0; i < v.size(); i++) {
            size_t l = 0;
            while (l < v[i].size() && l < prev.size() && v[i][l] == prev[l]) l++;
            nodes += (long long)v[i].size() - (long long)l;
            prev = v[i];
        }
    }

    /* ② 两条路各做多少次「看一位」 */
    long long bruteBits = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            size_t len = min(code[i].size(), msg[j].size());
            size_t k = 0;
            while (k < len && code[i][k] == msg[j][k]) k++;
            bruteBits += (long long)k + 1;
        }
    long long trieBits = bBits + cBits;          // 每条信息插一遍、每条暗号走一遍

    vector<pair<string, long long> > out;
    out.push_back(make_pair("m", m));
    out.push_back(make_pair("n", n));
    out.push_back(make_pair("bits", bBits + cBits));
    out.push_back(make_pair("nodes", nodes));
    out.push_back(make_pair("brute_pairs", (long long)m * n));
    out.push_back(make_pair("brute_bits", bruteBits));
    out.push_back(make_pair("trie_bits", trieBits));
    out.push_back(make_pair("ratio", trieBits ? bruteBits / trieBits : 0));
    out.push_back(make_pair("mib_x100", (long long)(nodes * 3.0 * 4 * 100 / 1048576.0)));

    if (mode == "csv") for (size_t i = 0; i < out.size(); i++) printf("%s,%lld\n", out[i].first.c_str(), out[i].second);
    else for (size_t i = 0; i < out.size(); i++) printf("  %-14s %lld\n", out[i].first.c_str(), out[i].second);
    return 0;
}