洛谷 P1071 [NOIP 2009 提高组] 潜伏者

// P1071 潜伏者 —— 正解：建一张双向的字母表，三种「无解」一个都不能漏
//
// ★ 题面把编码规则写成了三条，而**每一条都对应一件要检查的事**：
//   ② 加密就是把原信息里的字母换成它的密字   -> 同一个原文字母 x 只能有一个密字 y；
//   ③ 不同的字母对应不同的密字               -> 同一个密字 y 只能来自一个原文字母 x；
//   ①「A~Z 全部出现过」才算破译完成           -> 26 个字母**都要**在原信息里出现过。
// ⇒ ★★ 前两条是**双向**的，漏掉哪一个方向都会放过一整类输入（见 p1071One.cpp）；
//   第三条则和前两条完全无关，是另一件事（见 p1071Cover.cpp）。
//
// ⚠ 输入用 `cin >> a >> b >> c` 读三个「词」，这样行末的空格和换行怎么摆都无所谓
//   —— 官方样例的输入里**真的带着尾随空格**。
#include <bits/stdc++.h>
using namespace std;

int main() {
    string a, b, c;
    if (!(cin >> a >> b >> c)) return 0;
    if (a.size() != b.size()) { printf("Failed\n"); return 0; }

    int enc[26], dec[26];
    memset(enc, -1, sizeof(enc));
    memset(dec, -1, sizeof(dec));
    for (size_t i = 0; i < b.size(); i++) {
        int x = b[i] - 'A';                    // 原文字母
        int y = a[i] - 'A';                    // 它的密字
        if (enc[x] != -1 && enc[x] != y) { printf("Failed\n"); return 0; }   // 一个 x 两个 y
        if (dec[y] != -1 && dec[y] != x) { printf("Failed\n"); return 0; }   // 一个 y 两个 x
        enc[x] = y; dec[y] = x;
    }
    for (int x = 0; x < 26; x++)
        if (enc[x] == -1) { printf("Failed\n"); return 0; }                  // 有字母没出现过

    string out;
    for (char ch : c) out.push_back((char)('A' + dec[ch - 'A']));
    printf("%s\n", out.c_str());
    return 0;
}

// P1071 ✗ 错法一：只查了一个方向
//
// ⚠ 题面第 ③ 条是**两句话**：「每个字母只对应一个唯一的密字」＋「**不同的字母对应不同的密字**」。
//   只写前一句（`enc[x]` 一致）就漏掉了后一句 —— 两个不同的原文字母**可以**被映到同一个密字。
// ★ 官方**样例一**考的正是这个：密文 `AA` ↔ 原文 `AB` ⇒ A 和 B 的密字都是 A。
// ★ 触发条件：**enc 方向自洽、可 dec 方向有冲突、而且 26 个字母都出现过**。
#include <bits/stdc++.h>
using namespace std;

int main() {
    string a, b, c;
    if (!(cin >> a >> b >> c)) return 0;
    if (a.size() != b.size()) { printf("Failed\n"); return 0; }

    int enc[26], dec[26];
    memset(enc, -1, sizeof(enc));
    memset(dec, -1, sizeof(dec));
    for (size_t i = 0; i < b.size(); i++) {
        int x = b[i] - 'A', y = a[i] - 'A';
        if (enc[x] != -1 && enc[x] != y) { printf("Failed\n"); return 0; }
        enc[x] = y; dec[y] = x;               // ⚠ 少了「一个 y 只能来自一个 x」那一句
    }
    for (int x = 0; x < 26; x++) if (enc[x] == -1) { printf("Failed\n"); return 0; }

    string out;
    for (char ch : c) out.push_back((char)('A' + dec[ch - 'A']));
    printf("%s\n", out.c_str());
    return 0;
}

// P1071 解析页上那几个「生成器为什么必须反着造」的数字的出处。
//   ./p1071Count        人话版
//   ./p1071Count csv    给 check:viz 用
//
// ★★ 它只回答一个问题，而这个问题决定了整页的对拍策略：
//   **随机造一段长度 L 的原文，26 个字母全出现的概率有多大？**
//   —— 这是「[生成器该照抄题面的比值](/sol/p1020/)」在这道题上的具体形态：
//     题面允许 L 小到 1、大到 100，而顺手写的生成器在 `1..100` 里均匀摇 L
//     ⇒ 绝大多数轮次连 26 个字母都凑不齐，正解直接 Failed，**对拍在验零**。
//
// ⚠ 这个概率用容斥算是精确的（不用估、不用跑蒙特卡洛）：
//   P(全覆盖) = Σ_{k=0..26} (-1)^k C(26,k) ((26-k)/26)^L
#include <bits/stdc++.h>
using namespace std;

static double coverProb(int L) {
    double p = 0;
    for (int k = 0; k <= 26; k++) {
        double term = 1;
        for (int i = 0; i < k; i++) term = term * (26 - i) / (i + 1);        // C(26,k)
        term *= pow((26.0 - k) / 26.0, (double)L);
        p += (k % 2 ? -term : term);
    }
    return p;
}

int main(int argc, char** argv) {
    bool csv = argc > 1 && string(argv[1]) == "csv";

    /* 顺手写的生成器：L 在 1..100 里均匀摇 ⇒ 平均覆盖概率 */
    double avg = 0;
    for (int L = 1; L <= 100; L++) avg += coverProb(L);
    avg /= 100.0;

    /* 期望要多长才凑得齐 26 个字母（优惠券收集问题）*/
    double need = 0;
    for (int i = 1; i <= 26; i++) need += 26.0 / i;

    /* 最小的、覆盖概率超过一半的 L */
    int half = 0;
    for (int L = 26; L <= 100000; L++) if (coverProb(L) >= 0.5) { half = L; break; }

    if (csv) {
        printf("cover100,%.4f\n", coverProb(100) * 100.0);
        printf("cover50,%.4f\n", coverProb(50) * 100.0);
        printf("avg,%.4f\n", avg * 100.0);
        printf("need,%.2f\n", need);
        printf("half,%d\n", half);
        return 0;
    }
    printf("① 随机原文长度 L，26 个字母全出现的概率：\n");
    for (int L : {26, 50, 75, 100}) printf("   L = %3d -> %.4f%%\n", L, coverProb(L) * 100.0);
    printf("② 顺手写的生成器（L 在 1..100 里均匀摇）平均覆盖概率只有 %.4f%%\n", avg * 100.0);
    printf("③ 期望要 %.2f 个字母才凑得齐 26 种（优惠券收集）；\n", need);
    printf("   而覆盖概率第一次过半，要 L = %d\n", half);
    return 0;
}

// P1071 的生成器：./p1071Gen 种子 [档位]
//
// ⚠⚠ 这道题最难写的不是正解，是生成器 —— 照题面「三行随机大写字母」造出来的数据，
//   **正解几乎每一轮都输出 Failed**（随机两行必然撞出冲突、26 个字母也出不全）
//   ⇒ 三个错法多半跟着一起 Failed，对拍在**验零**
//     （[「一致有两种：都算对了，和都没算」](/sol/p1746/)）。
// ⇒ ★★ 出路是**反着造**：先随机一个 26 字母的置换（那就是密码本），
//   再随机原文，拿置换加密出第一行 —— 这样造出来的数据天生没有冲突。
//   （[第 13 章 P1162](/sol/p1162/)、[第 40 章 P1888](/sol/p1888/) 那条的又一次。）
//
// 档位：
//   0  ★ 顺手写的：三行随机大写字母（⚠ 前两行等长 —— 题面保证了这一条；正解几乎恒 Failed）
//   1  ⚠ 反着造：随机置换 + 随机原文 ⇒ 没有冲突，但 26 个字母**不一定**出全
//   2  ⚠ 反着造 ＋ 保证 26 个字母全出现 ⇒ 正解一定输出翻译结果
//   3  ⚠⚠ 专门档：26 个字母全出现，**但故意让两个原文字母共用一个密字**
//      （★ 这是 p1071One「只查一个方向」唯一现形的形状）
//   4  ★ 最终档：上面几档混着来
//
// ⚠ rng() 一律先落到具名变量再传参（[第 24 章 P1776](/sol/p1776/) 那一跤）。
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int mode = argc > 2 ? atoi(argv[2]) : 0;
    mt19937 rng(seed * 1000003u + 20260907u);
    if (mode == 4) { unsigned r = rng() % 4u; mode = (int)r; }   // 最终档：随机挑一档

    auto randLen = [&](int lo, int hi) { unsigned r = rng() % (unsigned)(hi - lo + 1); return lo + (int)r; };

    if (mode == 0) {
        int len12 = randLen(1, 100);                   // ⚠ 题面保证「第一行长度与第二行相等」
        for (int i = 0; i < 3; i++) {
            int len = (i < 2) ? len12 : randLen(1, 100);
            string s;
            for (int k = 0; k < len; k++) { unsigned c = rng() % 26u; s.push_back((char)('A' + c)); }
            printf("%s\n", s.c_str());
        }
        return 0;
    }

    /* 反着造：先摇一个置换当密码本 */
    vector<int> perm(26);
    for (int i = 0; i < 26; i++) perm[i] = i;
    shuffle(perm.begin(), perm.end(), rng);

    string plain;
    if (mode >= 2) {                                   // 保证 26 个字母全出现
        for (int i = 0; i < 26; i++) plain.push_back((char)('A' + i));
        int extra = randLen(0, 74);
        for (int k = 0; k < extra; k++) { unsigned c = rng() % 26u; plain.push_back((char)('A' + c)); }
        shuffle(plain.begin(), plain.end(), rng);
    } else {
        int len = randLen(1, 100);
        for (int k = 0; k < len; k++) { unsigned c = rng() % 26u; plain.push_back((char)('A' + c)); }
    }

    if (mode == 3) {                                   // ⚠ 让两个原文字母共用一个密字
        unsigned u = rng() % 26u, v = rng() % 25u;
        int x = (int)u, y = (int)v; if (y >= x) y++;
        perm[y] = perm[x];
    }

    string cipher;
    for (char ch : plain) cipher.push_back((char)('A' + perm[ch - 'A']));

    int len3 = randLen(1, 100);
    string third;
    for (int k = 0; k < len3; k++) { unsigned c = rng() % 26u; third.push_back((char)('A' + c)); }

    printf("%s\n%s\n%s\n", cipher.c_str(), plain.c_str(), third.c_str());
    return 0;
}