洛谷 P1032 [NOIP 2002 提高组] 字串变换

// P1032 的**第一版**：老老实实**单向 BFS**，从 A 铺到 B。
//
// 题目：给两个串 A、B 和至多 6 条规则 `Ai → Bi`（把子串 Ai 换成 Bi）。
//       问最少几步能把 A 变成 B；**10 步以内**做不到就输出 `NO ANSWER!`。
//
// 它**是对的**，写起来也最自然：一层一层往外铺，第一次碰到 B 就是最短。
//
// ⚠ 问题在分支数：每个状态的后继 = 6 条规则 × 每条在串里出现的位置（串长 ≤ 20），
//   记作 b。铺到第 10 层就是 `b¹⁰`。
//   ⇒ 页面第 ③ 步量了它和双向 BFS 差多少 —— 差的是**指数**，不是常数。

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

static const int MAXLEN = 20;
static int n;                                // 规则条数
static string from_[8], to_[8];
static long long pushed = 0;                 // 一共入队多少个状态 —— 这一页的尺子

/** 把 s 按所有规则、所有出现位置变换一次，得到所有后继 */
static vector<string> nexts(const string& s) {
    vector<string> out;
    for (int i = 0; i < n; i++)
        for (size_t p = s.find(from_[i]); p != string::npos; p = s.find(from_[i], p + 1)) {
            string t = s.substr(0, p) + to_[i] + s.substr(p + from_[i].size());
            if ((int)t.size() <= MAXLEN) out.push_back(t);      // ★ 长度上限，见文件头 ②
        }
    return out;
}

int main(int argc, char** argv) {
    string A, B;
    if (!(cin >> A >> B)) return 0;
    while (n < 6 && (cin >> from_[n] >> to_[n])) n++;

    if (A == B) { cout << 0 << "\n"; return 0; }

    unordered_map<string, int> dist{{A, 0}};
    vector<string> cur{A};
    int ans = -1;

    for (int level = 0; level < 10 && ans < 0 && !cur.empty(); level++) {
        vector<string> nxt;
        for (const string& s : cur) {
            for (const string& t : nexts(s)) {
                if (dist.count(t)) continue;
                dist[t] = level + 1;
                pushed++;
                if (t == B) { ans = level + 1; break; }
                nxt.push_back(t);
            }
            if (ans >= 0) break;
        }
        cur.swap(nxt);
    }

    if (ans >= 0 && ans <= 10) cout << ans << "\n";
    else cout << "NO ANSWER!\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "pushed=" << pushed << "\n";
    return 0;
}

// P1032 字串变换 —— 双向 BFS（★ 这一版就能 AC）
//
// 题目：给两个串 A、B 和至多 6 条规则 `Ai → Bi`（把子串 Ai 换成 Bi）。
//       问最少几步能把 A 变成 B；**10 步以内**做不到就输出 `NO ANSWER!`。
//
// ★ 这道题为什么是双向 BFS 的教科书：本章第 8 步说过双向 BFS 有一个**前提** ——
//   **起点和终点都明确**。这道题正好两头都给死了（A 和 B 都在输入里）。
//
// ★★★ 而它值多少钱，要算在**指数**上，不是算在时间上：
//   每个状态的分支数 = 6 条规则 × 每条规则在串里出现的位置（串长 ≤ 20）—— 记作 b。
//   单向 BFS 要铺到第 10 层：`b¹⁰`；
//   双向各铺 5 层：`2 × b⁵`。
//   ⇒ b = 10 的话是 `10¹⁰` 对 `2 × 10⁵` —— **五万倍**，而不是「快一倍」。
//
// ⚠ 两个必须做对的地方：
//   ① **按层扩展**（每次把当前较小的那一侧整层展开），并且在生成新状态时就查对面 ——
//      ⚠⚠ 而且**要把这一整层扫完再取最小**，不能一碰到相遇点就返回：
//      同一层里不同的相遇点，对面的深度可能不一样。
//      （这一条是被对拍抓出来的：草稿「碰到就返回」，双向给 6 而单向给 5。）
//   ② **串长超过 20 就丢掉**：规则可以让串变长（样例里 `y → yz`），
//      状态空间本身是无界的。题面说「所有字符串长度的上限为 20」，这一版据此剪枝。
//   ③ ★★★ **从 B 那一侧走的时候必须用「反规则」`Bi → Ai`。**
//      规则是**单向**的（`Ai → Bi`，不能反着用），所以这张图的边是**有向**的。
//      ⇒ [第 15 章 P1135](/sol/p1135/) 那条：「从终点反着跑一次」缺一个主语 ——
//        **这张图的边是不是无向的**。这道题不是，所以反向侧要建反图。
//      ⚠ 这一条是被对拍抓出来的：草稿两侧都用正向规则，
//        双向和单向 BFS 在 16 组里对不上 7 组，**而且两个方向的错都有**
//        （有时答案偏大、有时偏小）。
//
// ⚠⚠ 题面开头那段免责声明要认真读：「**本题不保证存在靠谱的多项式复杂度的做法。
//   测试数据非常的水，各种做法都可以通过，不代表算法正确。**」
//   ⇒ 这道题「能过」和「算法对」是两件事，页面第 ④ 步量了这句话。

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

static const int MAXLEN = 20;
static int n;                                // 规则条数
static string from_[8], to_[8];
static long long pushed = 0;                 // 一共入队多少个状态 —— 这一页的尺子

/** 把 s 变换一次，得到所有后继。
 *  ★★★ back = true 时用**反规则**（`Bi → Ai`）—— 见文件头 ③，这是这道题最容易写错的一处。 */
static vector<string> nexts(const string& s, bool back) {
    vector<string> out;
    for (int i = 0; i < n; i++) {
        const string& L = back ? to_[i] : from_[i];
        const string& R = back ? from_[i] : to_[i];
        for (size_t p = s.find(L); p != string::npos; p = s.find(L, p + 1)) {
            string t = s.substr(0, p) + R + s.substr(p + L.size());
            if ((int)t.size() <= MAXLEN) out.push_back(t);      // ★ 长度上限，见文件头 ②
        }
    }
    return out;
}

int main(int argc, char** argv) {
    string A, B;
    if (!(cin >> A >> B)) return 0;
    while (n < 6 && (cin >> from_[n] >> to_[n])) n++;

    if (A == B) { cout << 0 << "\n"; return 0; }

    unordered_map<string, int> da{{A, 0}}, db{{B, 0}};
    vector<string> qa{A}, qb{B};
    int ans = -1;

    while (!qa.empty() && !qb.empty() && ans < 0) {
        // ★ 每次展开**较小的那一侧**的一整层
        bool forward = qa.size() <= qb.size();
        vector<string>& cur = forward ? qa : qb;
        unordered_map<string, int>& mine = forward ? da : db;
        unordered_map<string, int>& other = forward ? db : da;
        if (mine[cur[0]] >= 5) break;        // 两边各 5 层，合起来就是 10 步
        vector<string> nxt;
        int best = INT_MAX;
        for (const string& s : cur) {
            int d = mine[s];
            for (const string& t : nexts(s, !forward)) {
                auto it = other.find(t);
                // ⚠⚠ 这里**不能一碰到就返回**：同一层里不同的相遇点，对面的深度可能不一样。
                //   草稿就是「第一个相遇点就 return」，被对拍当场抓到（双向给 6、单向给 5）。
                //   ⇒ 把这一整层扫完，取 da + db 的**最小值**。
                if (it != other.end()) best = min(best, d + 1 + it->second);
                if (mine.count(t)) continue;
                mine[t] = d + 1;
                nxt.push_back(t);
                pushed++;
            }
        }
        if (best != INT_MAX) { ans = best; break; }
        cur.swap(nxt);
    }

    if (ans >= 0 && ans <= 10) cout << ans << "\n";
    else cout << "NO ANSWER!\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "pushed=" << pushed << "\n";
    return 0;
}

// P1032 的**错法**：双向 BFS 写对了，**但从 B 那一侧还在用正向规则**。
//
// 题目：给两个串 A、B 和至多 6 条规则 `Ai → Bi`（把子串 Ai 换成 Bi）。
//       问最少几步能把 A 变成 B；**10 步以内**做不到就输出 `NO ANSWER!`。
//
// 规则 `Ai → Bi` 是**单向**的（不能反着用）⇒ 这张图的边是**有向**的。
//   从 B 往回走，走的应该是**反规则** `Bi → Ai`；用正向规则走出来的根本不是「B 的前驱」。
//
// ★★★ [第 15 章 P1135](/sol/p1135/) 那条：**「从终点反着跑一次」缺一个主语 ——
//   这张图的边是不是无向的。** 八数码的每一步可逆，所以那道题成立；
//   电梯和这道题都不可逆，照搬就错。
//
// ⚠⚠ 而它错得**两个方向都有**：有时答案偏大（走不到，报 NO ANSWER!），
//   有时答案**偏小**（用正向规则从 B 走出来的串，和 A 那边接上了一条根本不存在的路）。
//   ⇒ 页面第 ④ 步量了它 —— 而**官方样例照样给 3**。

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

static const int MAXLEN = 20;
static int n;                                // 规则条数
static string from_[8], to_[8];
static long long pushed = 0;                 // 一共入队多少个状态 —— 这一页的尺子

/** 把 s 变换一次，得到所有后继。
 *  ★★★ back = true 时用**反规则**（`Bi → Ai`）—— 见文件头 ③，这是这道题最容易写错的一处。 */
static vector<string> nexts(const string& s, bool back) {
    vector<string> out;
    for (int i = 0; i < n; i++) {
        const string& L = back ? to_[i] : from_[i];
        const string& R = back ? from_[i] : to_[i];
        for (size_t p = s.find(L); p != string::npos; p = s.find(L, p + 1)) {
            string t = s.substr(0, p) + R + s.substr(p + L.size());
            if ((int)t.size() <= MAXLEN) out.push_back(t);      // ★ 长度上限，见文件头 ②
        }
    }
    return out;
}

int main(int argc, char** argv) {
    string A, B;
    if (!(cin >> A >> B)) return 0;
    while (n < 6 && (cin >> from_[n] >> to_[n])) n++;

    if (A == B) { cout << 0 << "\n"; return 0; }

    unordered_map<string, int> da{{A, 0}}, db{{B, 0}};
    vector<string> qa{A}, qb{B};
    int ans = -1;

    while (!qa.empty() && !qb.empty() && ans < 0) {
        // ★ 每次展开**较小的那一侧**的一整层
        bool forward = qa.size() <= qb.size();
        vector<string>& cur = forward ? qa : qb;
        unordered_map<string, int>& mine = forward ? da : db;
        unordered_map<string, int>& other = forward ? db : da;
        if (mine[cur[0]] >= 5) break;        // 两边各 5 层，合起来就是 10 步
        vector<string> nxt;
        int best = INT_MAX;
        for (const string& s : cur) {
            int d = mine[s];
            for (const string& t : nexts(s, false)) {   // ★ 错在这里：两侧都用正向规则
                auto it = other.find(t);
                // ⚠⚠ 这里**不能一碰到就返回**：同一层里不同的相遇点，对面的深度可能不一样。
                //   草稿就是「第一个相遇点就 return」，被对拍当场抓到（双向给 6、单向给 5）。
                //   ⇒ 把这一整层扫完，取 da + db 的**最小值**。
                if (it != other.end()) best = min(best, d + 1 + it->second);
                if (mine.count(t)) continue;
                mine[t] = d + 1;
                nxt.push_back(t);
                pushed++;
            }
        }
        if (best != INT_MAX) { ans = best; break; }
        cur.swap(nxt);
    }

    if (ans >= 0 && ans <= 10) cout << ans << "\n";
    else cout << "NO ANSWER!\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "pushed=" << pushed << "\n";
    return 0;
}

// P1032 对拍生成器：`./p1032Gen <seed> [字母表大小] [A 的长度] [走几步]`
//   字母表大小 默认 3 —— ★★★ **这个旋钮是这一页的全部**
//   A 的长度   默认 6
//   走几步     默认 4（B 由 A 真的走这么多步得到 ⇒ 答案 ≤ 这个数）
//
// 造法：随机造 6 条规则（`Ai → Bi`，长度 1~2 变 1~3），随机造 A，
//   再从 A **真的走 k 步**得到 B。⇒ 输入一定有解，而且答案 ≤ k。
//
// ★★★ 字母表大小为什么是那个旋钮：一个状态的后继数
//   = 6 条规则 × 每条规则的左边在串里出现的位置数。
//   字母只有 2 个的时候，长度 1 的规则**几乎每个位置都能匹配** ⇒ 分支数接近串长 × 6；
//   字母有 26 个的时候，一条长度 2 的规则在长度 6 的串里平均只匹配 0.007 次 ⇒ 分支数接近 0。
//   ⇒ **照题面「均由小写英文字母组成」随机造，造出来的几乎全是一步到头的平凡数据。**
//   页面第 ③ 步把这条曲线画出来了。

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

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    mt19937 rng(seed * 2654435761u + 31u);
    int alpha = argc > 2 ? atoi(argv[2]) : 3;
    int la = argc > 3 ? atoi(argv[3]) : 6;
    int steps = argc > 4 ? atoi(argv[4]) : 4;
    alpha = max(1, min(26, alpha));
    la = max(1, min(12, la));
    steps = max(0, min(10, steps));

    auto rndStr = [&](int lo, int hi) {
        int len = lo + (int)(rng() % (hi - lo + 1));
        string t;
        for (int i = 0; i < len; i++) t += char('a' + rng() % alpha);
        return t;
    };

    vector<pair<string, string>> rules;
    for (int i = 0; i < 6; i++) rules.push_back({rndStr(1, 2), rndStr(1, 3)});

    string A = rndStr(la, la), B = A;
    for (int i = 0; i < steps; i++) {          // 从 A 真的走 steps 步得到 B
        vector<string> cand;
        for (auto& r : rules)
            for (size_t p = B.find(r.first); p != string::npos; p = B.find(r.first, p + 1)) {
                string t = B.substr(0, p) + r.second + B.substr(p + r.first.size());
                if ((int)t.size() <= 20) cand.push_back(t);
            }
        if (cand.empty()) break;
        B = cand[rng() % cand.size()];
    }

    printf("%s %s\n", A.c_str(), B.c_str());
    for (auto& r : rules) printf("%s %s\n", r.first.c_str(), r.second.c_str());
    return 0;
}

// P1032 的**对照版**：双向 BFS 写对了，只是**去掉了「串长超过 20 就丢掉」那一句**。
//
// ⚠ 它**不是错法** —— 这一页原来打算把它当错法写，被实测打回来了。
//
// 草稿的理由听起来很硬：规则可以让串**变长**（样例里就有 `y → yz`），
//   状态空间本身是无界的 ⇒「必须剪长度」。
// ★★★ 可这句话缺了一步算术：两侧各只铺 **5** 层，每步最多把串加长 2 ⇒
//   串长最多 `|A| + 10`。而题面保证 `|A| ≤ 20`……
//   **在生成器给的规模上，这条线大多数时候根本碰不到。**
//
// 实测（每档 200 组，字母表 3）：
//   A 长  6：入队 31456 → 31456（**1.00 倍**，一次都没碰到那条线）
//   A 长  9：入队 64811 → 65020（1.00 倍）
//   A 长 12：入队 104424 → 108502（**1.04 倍**）
//   而**答案一次都没有不同**。
//
// ⇒ 结论要说准：这条剪枝**不是必需的，也不值钱** —— 它省的是 4%，不是一个数量级。
//   ⚠ 这是[第 10 章 P1068](/sol/p1068/) 那条的又一次：**别把「听起来有道理的提醒」当结论用**。

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

static const int MAXLEN = 20;
static int n;                                // 规则条数
static string from_[8], to_[8];
static long long pushed = 0;                 // 一共入队多少个状态 —— 这一页的尺子

/** 把 s 按所有规则、所有出现位置变换一次，得到所有后继 */
static vector<string> nexts(const string& s) {
    vector<string> out;
    for (int i = 0; i < n; i++)
        for (size_t p = s.find(from_[i]); p != string::npos; p = s.find(from_[i], p + 1)) {
            string t = s.substr(0, p) + to_[i] + s.substr(p + from_[i].size());
            out.push_back(t);                    // ★ 错在这里：没有长度上限
        }
    return out;
}

int main(int argc, char** argv) {
    string A, B;
    if (!(cin >> A >> B)) return 0;
    while (n < 6 && (cin >> from_[n] >> to_[n])) n++;

    if (A == B) { cout << 0 << "\n"; return 0; }

    unordered_map<string, int> da{{A, 0}}, db{{B, 0}};
    vector<string> qa{A}, qb{B};
    int ans = -1;

    while (!qa.empty() && !qb.empty() && ans < 0) {
        // ★ 每次展开**较小的那一侧**的一整层
        bool forward = qa.size() <= qb.size();
        vector<string>& cur = forward ? qa : qb;
        unordered_map<string, int>& mine = forward ? da : db;
        unordered_map<string, int>& other = forward ? db : da;
        if (mine[cur[0]] >= 5) break;        // 两边各 5 层，合起来就是 10 步
        vector<string> nxt;
        for (const string& s : cur) {
            int d = mine[s];
            for (const string& t : nexts(s)) {
                if (mine.count(t)) continue;
                auto it = other.find(t);
                if (it != other.end()) { ans = d + 1 + it->second; break; }   // ★ 生成时就查对面
                mine[t] = d + 1;
                nxt.push_back(t);
                pushed++;
            }
            if (ans >= 0) break;
        }
        cur.swap(nxt);
    }

    if (ans >= 0 && ans <= 10) cout << ans << "\n";
    else cout << "NO ANSWER!\n";
    if (argc > 1 && string(argv[1]) == "count") cerr << "pushed=" << pushed << "\n";
    return 0;
}

// P1032 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1032Count`      人看的版本
// `./p1032Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 四段：
//   ① 官方样例：四个版本各输出什么（★ 两个错法它都放过了）；
//   ② ★★★ **字母表大小**这个旋钮：分支数、单向 vs 双向的入队状态数；
//      ⇒ 照题面「均由小写英文字母组成」随机造，造出来的几乎全是平凡数据；
//   ③ ★★★ 两个错法的抓获率：
//      · 反向侧用正向规则（**这张图是有向的**）；
//      · 不剪串长（只坏复杂度、不坏答案）；
//   ④ 单向 BFS 在字母表小的时候要铺多少 —— 带上限，不然它根本不返回。

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

static bool CSV = false;
static void row(const char* key, const vector<long long>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (long long x : v) printf(",%lld", x);
    printf("\n");
}

static const int MAXLEN = 20;
static int n;
static string from_[8], to_[8];
static long long pushed, cap_;
static bool blew;

static vector<string> nexts(const string& s, bool back, bool limit) {
    vector<string> out;
    for (int i = 0; i < n; i++) {
        const string& L = back ? to_[i] : from_[i];
        const string& R = back ? from_[i] : to_[i];
        if (L.empty()) continue;
        for (size_t p = s.find(L); p != string::npos; p = s.find(L, p + 1)) {
            string t = s.substr(0, p) + R + s.substr(p + L.size());
            if (!limit || (int)t.size() <= MAXLEN) out.push_back(t);
        }
    }
    return out;
}

/** mode 0 = 正解双向；1 = 反向侧用正向规则（错）；2 = 不剪串长；3 = 单向 BFS */
static string solve(const string& A, const string& B, int mode, long long cap = 0) {
    pushed = 0; cap_ = cap; blew = false;
    bool limit = (mode != 2);
    if (A == B) return "0";

    if (mode == 3) {
        unordered_map<string, int> dist{{A, 0}};
        vector<string> cur{A};
        for (int level = 0; level < 10 && !cur.empty(); level++) {
            vector<string> nxt;
            for (const string& s : cur)
                for (const string& t : nexts(s, false, limit)) {
                    if (dist.count(t)) continue;
                    dist[t] = level + 1;
                    if (++pushed >= cap && cap) { blew = true; return "?"; }
                    if (t == B) return to_string(level + 1);
                    nxt.push_back(t);
                }
            cur.swap(nxt);
        }
        return "NO ANSWER!";
    }

    unordered_map<string, int> da{{A, 0}}, db{{B, 0}};
    vector<string> qa{A}, qb{B};
    while (!qa.empty() && !qb.empty()) {
        bool forward = qa.size() <= qb.size();
        vector<string>& cur = forward ? qa : qb;
        unordered_map<string, int>& mine = forward ? da : db;
        unordered_map<string, int>& other = forward ? db : da;
        if (mine[cur[0]] >= 5) break;
        vector<string> nxt;
        int best = INT_MAX;
        for (const string& s : cur) {
            int d = mine[s];
            bool back = (mode == 1) ? false : !forward;
            for (const string& t : nexts(s, back, limit)) {
                auto it = other.find(t);
                if (it != other.end()) best = min(best, d + 1 + it->second);
                if (mine.count(t)) continue;
                mine[t] = d + 1;
                nxt.push_back(t);
                if (++pushed >= cap && cap) { blew = true; return "?"; }
            }
        }
        if (best != INT_MAX) return best <= 10 ? to_string(best) : string("NO ANSWER!");
        cur.swap(nxt);
    }
    return "NO ANSWER!";
}

/** 和 p1032Gen.cpp 逐字一致 */
static void gen(int seed, int alpha, int la, int steps, string& A, string& B) {
    mt19937 rng((unsigned)seed * 2654435761u + 31u);
    alpha = max(1, min(26, alpha));
    la = max(1, min(12, la));
    steps = max(0, min(10, steps));
    auto rndStr = [&](int lo, int hi) {
        int len = lo + (int)(rng() % (hi - lo + 1));
        string t;
        for (int i = 0; i < len; i++) t += char('a' + rng() % alpha);
        return t;
    };
    n = 6;
    for (int i = 0; i < 6; i++) { from_[i] = rndStr(1, 2); to_[i] = rndStr(1, 3); }
    A = rndStr(la, la);
    B = A;
    for (int i = 0; i < steps; i++) {
        vector<string> cand;
        for (int i2 = 0; i2 < 6; i2++)
            for (size_t p = B.find(from_[i2]); p != string::npos; p = B.find(from_[i2], p + 1)) {
                string t = B.substr(0, p) + to_[i2] + B.substr(p + from_[i2].size());
                if ((int)t.size() <= 20) cand.push_back(t);
            }
        if (cand.empty()) break;
        B = cand[rng() % cand.size()];
    }
}

int main(int argc, char** argv) {
    CSV = (argc > 1 && string(argv[1]) == "csv");
    const long long CAP = 3000000;

    /* ① 官方样例 */
    {
        n = 3;
        from_[0] = "abc"; to_[0] = "xu";
        from_[1] = "ud";  to_[1] = "y";
        from_[2] = "y";   to_[2] = "yz";
        string a = solve("abcd", "xyz", 0), b = solve("abcd", "xyz", 1);
        string c = solve("abcd", "xyz", 2), d = solve("abcd", "xyz", 3);
        if (!CSV) printf("① 官方样例：正解 %s｜反向侧用正向规则 %s｜不剪串长 %s｜单向 BFS %s"
                         "（★ 两个错法样例都放过了）\n", a.c_str(), b.c_str(), c.c_str(), d.c_str());
        row("sample", {a == "3", b == "3", c == "3", d == "3"});
    }

    /* ② ★★★ 字母表大小这个旋钮 */
    {
        if (!CSV) printf("\n② 字母表大小：分支数、以及单向 / 双向要铺多少（每档 200 组）\n");
        vector<long long> out;
        for (int alpha : {2, 3, 5, 10, 26}) {
            long long branch = 0, uni = 0, bi = 0;
            int trivial = 0, uniBlew = 0;
            for (int s = 1; s <= 200; s++) {
                string A, B;
                gen(s, alpha, 6, 5, A, B);
                branch += (long long)nexts(A, false, true).size();
                if (A == B) trivial++;
                solve(A, B, 0, CAP);
                bi += pushed;
                solve(A, B, 3, CAP);
                if (blew) uniBlew++;
                uni += pushed;
            }
            out.push_back(branch); out.push_back(bi); out.push_back(uni);
            out.push_back(trivial); out.push_back(uniBlew);
            if (!CSV) printf("  字母表 %2d：起点分支数合计 %4lld｜双向入队 %8lld｜单向入队 %9lld"
                             "（撞上限 %d 组）｜A == B 的平凡数据 %d 组\n",
                             alpha, branch, bi, uni, uniBlew, trivial);
        }
        row("alpha", out);
    }

    /* ③ ★★★ 两个错法的抓获率 */
    {
        if (!CSV) printf("\n③ 两个错法各被抓多少（每档 200 组）\n");
        vector<long long> out;
        for (int alpha : {2, 3, 5, 26}) {
            int badFwd = 0, badLen = 0, smaller = 0, bigger = 0;
            for (int s = 1; s <= 200; s++) {
                string A, B;
                gen(s, alpha, 6, 5, A, B);
                string ok = solve(A, B, 0, CAP);
                string f = solve(A, B, 1, CAP);
                string l = solve(A, B, 2, CAP);
                if (f != ok) {
                    badFwd++;
                    if (ok != "NO ANSWER!" && f != "NO ANSWER!") {
                        if (atoi(f.c_str()) < atoi(ok.c_str())) smaller++; else bigger++;
                    }
                }
                if (l != ok) badLen++;
            }
            out.push_back(badFwd); out.push_back(smaller); out.push_back(bigger); out.push_back(badLen);
            if (!CSV) printf("  字母表 %2d：反向侧用正向规则 %3d / 200（其中答案偏小 %d、偏大 %d）"
                             "｜不剪串长 %d / 200\n", alpha, badFwd, smaller, bigger, badLen);
        }
        row("catch", out);
    }

    /* ④ 不剪串长：只坏复杂度 */
    {
        // ⚠ 草稿这里用 A 的长度 6，量出来入队数**一模一样（1.00 倍）** ——
        //   因为规则每步最多把串加长 2，五层下来 6 + 10 = 16，**根本长不到 20**。
        //   ⇒ 那一档量的是个空壳。换成 A 长 12（12 + 10 = 22 > 20）才碰得到这条线。
        if (!CSV) printf("\n④ 「不剪串长」值多少：A 的长度决定它碰不碰得到那条线（每档 200 组）\n");
        vector<long long> out;
        for (int la : {6, 9, 12}) {
            long long withLimit = 0, without = 0;
            int diff = 0;
            for (int s = 1; s <= 200; s++) {
                string A, B;
                gen(s, 3, la, 5, A, B);
                string x = solve(A, B, 0, CAP); withLimit += pushed;
                string y = solve(A, B, 2, CAP); without += pushed;
                if (x != y) diff++;
            }
            out.push_back(withLimit); out.push_back(without); out.push_back(diff);
            if (!CSV) printf("  A 长 %2d：入队 %lld → %lld（%.2f 倍）｜答案不同 %d / 200\n",
                             la, withLimit, without, without * 1.0 / withLimit, diff);
        }
        row("nolimit", out);
    }
    return 0;
}