洛谷 P1381 单词背诵

// P1381 单词背诵 —— 正解：把每个单词变成一个**编号**，然后尺取。
//
// ★★ 第一问其实不用尺取，一句话就完：**整篇文章本身就是一个合法的段落**
//   ⇒ 「某个窗口里最多能有几个要背的单词」= 「整篇文章里出现过的要背的单词有几个」。
//   （所有人第一版都会去枚举窗口，那是白做的。）
//
// ★ 第二问才是尺取：找**最短**的连续段，让它把那 ans1 个单词全含进去。
//   右端一路往前，左端在「去掉它也不影响」的时候就往前挪 ——
//   「不影响」有两种：这个词根本不用背，或者它在窗口里还有第二个。
//
// ⚠ 三处会咬人：
//   ① `ans1 = 0` 时第二问必须输出 **0**（一个词都不用背 ⇒ 空段落就够了），
//      而顺手写的初值是 `m` 或者 1。
//   ② 「重复的只算一个」—— 窗口里要数的是**种类**，不是**个数**。
//   ③ 达到 ans1 的窗口有很多个，要的是**最短**的那个，不是第一个。
//
// ★★ 而这道题跟这一章的关系，题单注解写得很清楚：
//   「这里用的是 unordered_map 那种哈希，和本章的字符串哈希是**两件事** —— 分清楚它们。」
//   ⇒ 相同点：两边都是「把一个串变成一个数」；
//     ★★★ 不同点：**STL 撞了只是慢，我们自己写的哈希撞了是错的**（见 p1381Hash.cpp）。
//
// 复杂度：O((n + m) × 词长)。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    unordered_map<string, int> id;
    id.reserve(n * 2);
    string s;
    for (int i = 0; i < n; i++) { cin >> s; if (!id.count(s)) { int k = (int)id.size(); id[s] = k; } }
    int tot = (int)id.size();

    int m;
    cin >> m;
    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> s;
        unordered_map<string, int>::const_iterator it = id.find(s);
        a[i] = (it == id.end()) ? -1 : it->second;
    }

    /* 第一问：整篇文章里出现过多少种要背的单词 */
    vector<int> cnt(tot, 0);
    int ans1 = 0;
    for (int i = 0; i < m; i++) if (a[i] >= 0 && cnt[a[i]]++ == 0) ans1++;

    /* 第二问：最短的、含齐这 ans1 种的窗口 */
    int ans2 = 0;
    if (ans1 > 0) {
        fill(cnt.begin(), cnt.end(), 0);
        ans2 = INT_MAX;
        int have = 0, l = 0;
        for (int r = 0; r < m; r++) {
            if (a[r] >= 0 && cnt[a[r]]++ == 0) have++;
            while (a[l] < 0 || cnt[a[l]] > 1) { if (a[l] >= 0) cnt[a[l]]--; l++; }
            if (have == ans1) ans2 = min(ans2, r - l + 1);
        }
    }
    cout << ans1 << '\n' << ans2 << '\n';
    return 0;
}

// P1381 —— ✗ 错法四：把单词换成**单模数**哈希值当身份证。
//
// ★ 它和 p1381Hash.cpp 只差一件事：少了第二个模数。
//
// ⚠⚠ 而这道题给了它一条最短的死路：单词长度 ≤ 10、全是小写字母 ——
//   而本章 collide.cpp 造出来的那一对碰撞串 **"rnjpnw" / "vwxtxa"**（长度 6、全小写、
//   base 131 模 10⁹+7 下都是 576565069）**完全落在题面允许的范围里**。
//   ⇒ 把 "rnjpnw" 放进要背的单词表、把 "vwxtxa" 放进文章，
//     这一版就会**以为文章里出现了一个它其实没出现的单词**，两问一起错。
//
// ★★★ 而这正是题单那句注解的分量：
//   `unordered_map<string,…>` 撞了只是掉进同一个桶、再逐个 `==` 比一遍
//   ⇒ **慢一点，答案永远对**；
//   我们这份是拿哈希值**当身份证**用的 ⇒ **撞了就是答错**。
//   **这一章没有兜底那一层，所以只能靠双模数把概率压到不可能。**
#include <bits/stdc++.h>
using namespace std;

const long long MOD1 = 1000000007;
const long long B1 = 131;

static long long key(const string& s) {
    long long a = 0;
    for (char c : s) a = (a * B1 + (c - 'a' + 1)) % MOD1;
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    unordered_map<long long, int> id;
    id.reserve(n * 2);
    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        long long k = key(s);
        if (!id.count(k)) { int t = (int)id.size(); id[k] = t; }
    }
    int tot = (int)id.size();
    int m;
    cin >> m;
    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> s;
        unordered_map<long long, int>::const_iterator it = id.find(key(s));
        a[i] = (it == id.end()) ? -1 : it->second;
    }
    vector<int> cnt(tot, 0);
    int ans1 = 0;
    for (int i = 0; i < m; i++) if (a[i] >= 0 && cnt[a[i]]++ == 0) ans1++;
    int ans2 = 0;
    if (ans1 > 0) {
        fill(cnt.begin(), cnt.end(), 0);
        ans2 = INT_MAX;
        int have = 0, l = 0;
        for (int r = 0; r < m; r++) {
            if (a[r] >= 0 && cnt[a[r]]++ == 0) have++;
            while (a[l] < 0 || cnt[a[l]] > 1) { if (a[l] >= 0) cnt[a[l]]--; l++; }
            if (have == ans1) ans2 = min(ans2, r - l + 1);
        }
    }
    cout << ans1 << '\n' << ans2 << '\n';
    return 0;
}

// P1381 —— 把「三种查表方式」摆在一起量一遍，顺带回答题单那句注解。
//
// ★ 三种都对，差别在别处：
//   ① `map<string,int>`            红黑树，O(log n) 次**串比较**
//   ② `unordered_map<string,int>`  ★ 它**也在算字符串哈希**（`std::hash<string>`），
//                                  但哈希值只当**桶号**，同一个桶里再逐个 `==` 比串
//                                  ⇒ **撞了只是慢，答案永远对**
//   ③ 自写双模数哈希 → `unordered_map<unsigned long long,int>`
//                                  ⇒ 哈希值当**身份证**用，**撞了就是答错**
//
// ⇒ ★★★ 这就是题单那句「和本章的字符串哈希是两件事」的全部内容：
//   **不是算法不一样，是有没有兜底那一层不一样。**
//
// ⚠ 顺带把「顶格数据上我们这份哈希撞没撞」数出来 —— 撞了就说明双模数也不保险。
//
// 用法：./p1381Count [table|csv]
#include <bits/stdc++.h>
using namespace std;

static string padDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) { if ((c & 0xC0) == 0x80) continue; disp += (c < 0x80) ? 1 : 2; }
    return s + string(max(0, width - disp), ' ');
}

const long long MOD1 = 1000000007, MOD2 = 998244353, B1 = 131, B2 = 13331;
static unsigned long long key2(const string& s) {
    long long a = 0, b = 0;
    for (char c : s) { long long x = c - 'a' + 1; a = (a * B1 + x) % MOD1; b = (b * B2 + x) % MOD2; }
    return ((unsigned long long)a << 32) ^ (unsigned long long)b;
}
static long long key1(const string& s) {
    long long a = 0;
    for (char c : s) a = (a * B1 + (c - 'a' + 1)) % MOD1;
    return a;
}

#define TIMEIT3(expr, out) do { \
    double _v[3]; \
    for (int _k = 0; _k < 3; _k++) { \
        auto _t0 = chrono::steady_clock::now(); \
        volatile long long _r = (expr); (void)_r; \
        _v[_k] = chrono::duration<double, milli>(chrono::steady_clock::now() - _t0).count(); \
    } \
    sort(_v, _v + 3); (out) = _v[1]; \
} while (0)

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

    /* 顶格：n = 1000 个要背的单词，m = 10⁵ 个文章单词，词长 ≤ 10 */
    mt19937 rng(20260909u);
    const int N = 1000, M = 100000;
    vector<string> words(N), art(M);
    for (int i = 0; i < N; i++) {
        int len = 1 + (int)(rng() % 10);
        string s(len, 'a');
        for (int j = 0; j < len; j++) s[j] = (char)('a' + rng() % 26);
        words[i] = s;
    }
    for (int i = 0; i < M; i++) art[i] = (rng() % 3 == 0) ? words[rng() % N] : words[rng() % N];

    double tMap = 0, tUmapS = 0, tOwn = 0;
    TIMEIT3(([&] {
        map<string, int> id;
        for (int i = 0; i < N; i++) id[words[i]] = i;
        long long hit = 0;
        for (int i = 0; i < M; i++) if (id.count(art[i])) hit++;
        return hit;
    })(), tMap);
    TIMEIT3(([&] {
        unordered_map<string, int> id;
        id.reserve(N * 2);
        for (int i = 0; i < N; i++) id[words[i]] = i;
        long long hit = 0;
        for (int i = 0; i < M; i++) if (id.count(art[i])) hit++;
        return hit;
    })(), tUmapS);
    TIMEIT3(([&] {
        unordered_map<unsigned long long, int> id;
        id.reserve(N * 2);
        for (int i = 0; i < N; i++) id[key2(words[i])] = i;
        long long hit = 0;
        for (int i = 0; i < M; i++) if (id.count(key2(art[i]))) hit++;
        return hit;
    })(), tOwn);

    /* ⚠ 撞没撞：把 N 个不同的单词的键数一数 */
    set<string> uniq(words.begin(), words.end());
    set<unsigned long long> k2;
    set<long long> k1;
    for (set<string>::const_iterator it = uniq.begin(); it != uniq.end(); ++it) {
        k2.insert(key2(*it));
        k1.insert(key1(*it));
    }

    if (mode == "table") {
        printf("★ 顶格 n = 1000、m = 10⁵（词长 ≤ 10），三种查表方式（3 次取中位数）\n\n");
        printf("    %s %12s\n", padDisp("查表方式", 44).c_str(), "毫秒");
        printf("    %s %10.1f\n", padDisp("① map<string,int>（红黑树）", 44).c_str(), tMap);
        printf("    %s %10.1f\n", padDisp("② unordered_map<string,int>（STL 自己哈希）", 44).c_str(), tUmapS);
        printf("    %s %10.1f\n", padDisp("③ 自写双模数哈希 → unordered_map<u64>", 44).c_str(), tOwn);
        printf("\n    ⇒ ② 比 ① 快 %.1f 倍；③ 和 ② 差 %.2f 倍 —— **选哪个都能过**，这道题的关卡不在这儿\n",
               tMap / tUmapS, tUmapS / tOwn);
        printf("\n⚠ 那 %d 个互不相同的单词，键撞了没有：\n", (int)uniq.size());
        printf("    双模数（64 位键）：%d 个不同的键 ⇒ %s\n",
               (int)k2.size(), k2.size() == uniq.size() ? "没撞" : "★ 撞了！");
        printf("    单模数（10⁹+7）  ：%d 个不同的键 ⇒ %s\n",
               (int)k1.size(), k1.size() == uniq.size() ? "没撞（随机数据撞不到，要**造**）" : "★ 撞了！");
        printf("\n    ⇒ ★★★ 单模数这一行的「没撞」一点都不让人放心："
               "collide.cpp 造到第 36819 个串就撞出了一对，\n"
               "      而那一对（rnjpnw / vwxtxa）**长度 6、全小写，完全落在这道题的题面里**。\n");
    } else {
        printf("tMap,%.1f\ntUmapS,%.1f\ntOwn,%.1f\n", tMap, tUmapS, tOwn);
        printf("uniq,%d\nk2,%d\nk1,%d\n", (int)uniq.size(), (int)k2.size(), (int)k1.size());
        printf("ratio21,%.1f\n", tMap / tUmapS);
    }
    return 0;
}

// P1381 数据生成器（对拍用）。用法：./p1381Gen <seed> [档位]，不给档位就是**最终档 4**。
//
// ★★ 这一页的生成器是整页最难写的一处，理由和[第 47 章 P1071](/sol/p1071/) 一模一样：
//   照题面随机造 —— n 个随机小写串当单词表、m 个随机小写串当文章 ——
//   两边**撞上的概率是 26⁻¹⁰ 量级** ⇒ **正解每一轮都输出 `0 0`**。
//   ⇒ 那不是「抓获率低」，是**这批数据根本没在问问题**。
//   ⇒ 出路是**反着造**：文章里的词**从单词表里抽**（再掺一点表外的词）。
//
// 每个错法靠什么现形：
//   ①ans2 初值是 m   ← 只要 ans1 = 0 —— ★ 顺手那一档一抓一个准（那一档全是 0 0）
//   ②数个数不数种类  ← 要「某个要背的词在文章里出现两次以上」
//   ③取第一个窗口    ← 要「最短的窗口不是最早的那个」
//   ④单模数当身份证  ← ★★ 只能埋 collide.cpp 那一对："rnjpnw" 进单词表、"vwxtxa" 进文章
//
// 档位：
//   0  ★ 顺手写法：单词表和文章各自随机 —— **正解恒输出 0 0**，只有 ① 会现形
//   1  ★ 反着造：文章里的词大半从单词表里抽 —— ② ③ 这才有得谈
//   2  ★ 词表压到很小（2~4 个）＋ 文章长 —— 逼出「最短窗口不是第一个」
//   3  ★ 档 1 ＋ 埋那一对碰撞串 —— 为 ④ 造的
//   4  ★★ 最终档 = 2 ＋ 3
#include <bits/stdc++.h>
using namespace std;

static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }
static string rw(int lo, int hi, int alpha) {
    int len = ri(lo, hi);
    string s(len, 'a');
    for (int i = 0; i < len; i++) s[i] = (char)('a' + ri(0, alpha - 1));
    return s;
}

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1u;
    int level = argc > 2 ? atoi(argv[2]) : 4;
    rng.seed(seed * 2654435761u + 4242u);

    vector<string> words, art;
    if (level == 0) {
        int n = ri(3, 8), m = ri(10, 30);
        for (int i = 0; i < n; i++) words.push_back(rw(4, 10, 26));
        for (int i = 0; i < m; i++) art.push_back(rw(4, 10, 26));
    } else {
        int n = (level == 2 || level == 4) ? ri(2, 4) : ri(3, 8);
        int m = ri(20, 45);
        for (int i = 0; i < n; i++) words.push_back(rw(2, 4, 3));      // ★ 短词 + 小字母表：容易重复
        for (int i = 0; i < m; i++) {
            if (ri(0, 3) == 0) art.push_back(rw(2, 4, 3));             // 掺一点表外的词
            else art.push_back(words[ri(0, (int)words.size() - 1)]);
        }
        if (level == 3 || level == 4) {
            words.push_back("rnjpnw");                                  // ★ 只进单词表
            art.insert(art.begin() + ri(0, (int)art.size()), "vwxtxa");  // ★ 只进文章
        }
    }

    printf("%d\n", (int)words.size());
    for (const string& w : words) printf("%s\n", w.c_str());
    printf("%d\n", (int)art.size());
    for (const string& w : art) printf("%s\n", w.c_str());
    return 0;
}