洛谷 P1598 [USACO03FEB] 垂直柱状图

// P1598 垂直柱状图 —— 正解：数 26 个字母，再竖着打出来
//
// ★★ 这道题的算法只有一句「数一遍」，**真正的考点是输出格式**，题面把话说得很死：
//   「在任何一行末尾不要打印不需要的多余空格」「不要打印任何空行」。
// ⇒ 所以这一页量的东西也和别的页不一样：**它是全书里「对拍绝对不能 strip」最锋利的一次**
//   —— 三个错法里有一个只在空格上不同，一 strip 就全绿（见 p1598Chars.cpp）。
//
// ⚠⚠ 另外有一处题面和数据打架，必须在这儿说清楚：
//   题面写「四行**大写字母**」，而**官方样例里有 `.`、`!` 和空格** ⇒ **非字母必须跳过**。
//   ⚠ 而「不跳过」的后果不是答案错，是 `cnt[c - 'A']` 里的下标变成**负数**
//     （`'.' - 'A'` = −19、`'!' - 'A'` = −32、`' ' - 'A'` = −33）—— 那是 UB，
//     它在这道题上**不改变答案**，所以对拍和样例都看不见它。
#include <bits/stdc++.h>
using namespace std;

int main() {
    int cnt[26] = {0};
    string line;
    for (int i = 0; i < 4; i++) {
        if (!getline(cin, line)) break;
        for (char c : line)
            if (c >= 'A' && c <= 'Z') cnt[c - 'A']++;   // ★ 只数大写字母，别的一律跳过
    }
    int mx = 0;
    for (int i = 0; i < 26; i++) mx = max(mx, cnt[i]);

    for (int h = mx; h >= 1; h--) {                     // ★ 从最高那一层往下打
        string row;
        for (int i = 0; i < 26; i++) {
            if (i) row.push_back(' ');
            row.push_back(cnt[i] >= h ? '*' : ' ');
        }
        while (!row.empty() && row.back() == ' ') row.pop_back();   // ⚠ 行末不许有多余空格
        printf("%s\n", row.c_str());
    }
    for (int i = 0; i < 26; i++) printf("%c%c", 'A' + i, i == 25 ? '\n' : ' ');
    return 0;
}

// P1598 解析页上那几个「和算法无关」的数字的出处。
//   ./p1598Chars < 输入        人话版
//   ./p1598Chars csv < 输入    给 check:viz 用
//
// 它回答三件事：
//   ① ⚠⚠ **题面和数据打架**：题面写「四行**大写字母**」，可这份输入里有哪些非字母字符？
//      它们的 `c - 'A'` 是多少（也就是「不跳过」的话会往数组外面写到哪儿去）；
//   ② ★★ 官方那组样例是不是**全字母句**（26 个字母一个不缺）——
//      这一条直接决定了「最后一行只打出现过的字母」那个错法会不会被样例打死；
//   ③ ★ `Z` 的出现次数和最大值 —— 「行末留空格」那个错法的触发条件就是 `cnt['Z'] < max`。
#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    bool csv = argc > 1 && string(argv[1]) == "csv";
    int cnt[26] = {0};
    map<char, int> other;
    string line;
    while (getline(cin, line))
        for (char c : line) {
            if (c >= 'A' && c <= 'Z') cnt[c - 'A']++;
            else other[c]++;
        }
    int mx = 0, missing = 0;
    for (int i = 0; i < 26; i++) { mx = max(mx, cnt[i]); if (!cnt[i]) missing++; }

    if (csv) {
        printf("missing,%d\n", missing);
        printf("maxCnt,%d\ncntZ,%d\n", mx, cnt[25]);
        string names;
        for (auto& kv : other) {
            if (!names.empty()) names.push_back('|');
            names += (kv.first == ' ' ? string("SPACE") : string(1, kv.first));
            names += ":" + to_string((int)kv.first - 'A');
        }
        printf("others,%s\n", names.c_str());
        return 0;
    }

    printf("① 这份输入里的非字母字符（题面说「由大写字母组成」）：\n");
    for (auto& kv : other)
        printf("   %-6s 出现 %2d 次，c - 'A' = %d\n",
               kv.first == ' ' ? "空格" : string(1, kv.first).c_str(), kv.second, (int)kv.first - 'A');
    printf("   ⇒ 不跳过它们的话，cnt[c - 'A'] 会写到数组**外面**去（负下标，UB）\n");
    printf("② 26 个字母里一次都没出现的有 %d 个 ⇒ %s\n",
           missing, missing == 0 ? "★ 这是一个全字母句" : "不是全字母句");
    printf("③ 最大出现次数 = %d，Z 出现 %d 次 ⇒ 「行末留空格」那个错法%s现形\n",
           mx, cnt[25], cnt[25] < mx ? "会" : "不会");
    return 0;
}

// P1598 ✗ 错法一：星号那几行末尾留了多余空格
//
// ⚠ 题面两处都写了这件事（输出格式一次、提示里又一次），可它是**看不见**的错 ——
//   页面上、终端里，一行末尾多几个空格和不多，长得一模一样。
// ★ 触发条件是一句精确的话：**`Z` 的出现次数小于最大值**
//   （只要某一层里 `Z` 那一列是空的，这一行就带着多余空格结束）。
//   ⇒ ⚠ 反过来说：**如果 `Z` 恰好是出现最多的字母，这个 bug 就一次都不会现形。**
// ⇒ ★★★ 而它最要命的地方在对拍上：**逐字节比抓得到，strip 之后一个都抓不到。**
#include <bits/stdc++.h>
using namespace std;

int main() {
    int cnt[26] = {0};
    string line;
    for (int i = 0; i < 4; i++) {
        if (!getline(cin, line)) break;
        for (char c : line) if (c >= 'A' && c <= 'Z') cnt[c - 'A']++;
    }
    int mx = 0;
    for (int i = 0; i < 26; i++) mx = max(mx, cnt[i]);
    for (int h = mx; h >= 1; h--) {
        string row;
        for (int i = 0; i < 26; i++) { if (i) row.push_back(' '); row.push_back(cnt[i] >= h ? '*' : ' '); }
        printf("%s\n", row.c_str());                    // ⚠ 少了那一句 rtrim
    }
    for (int i = 0; i < 26; i++) printf("%c%c", 'A' + i, i == 25 ? '\n' : ' ');
    return 0;
}

// P1598 的生成器：./p1598Gen 种子 [档位]
//
// ★ 三个错法各靠什么现形：
//   · p1598Trail（行末留空格）→ **Z 的次数 < 最大次数**（某一层里 Z 那列是空的）；
//   · p1598Miss（最后一行只打出现过的）→ **存在一次都没出现的字母**；
//   · p1598Flip（柱子上下颠倒）→ **不是每个字母的次数都 ∈ {0, 最大值}**。
//
// 档位：
//   0  ★ 顺手写的：四行随机大写字母，每行 10~40 个
//   1  ⚠ 保证 26 个字母全出现（★ 官方样例正是这一档 —— 它是个全字母句）
//   2  ⚠⚠ **26 个字母各出现同样多次** ⇒ 上面三条触发条件**同时不成立**，三个错法一起是 0
//   3  ★ 最终档：随机字母 ＋ 混进 `.` `!` 和空格（题面说没有，可官方样例里有）
//
// ⚠ 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);

    vector<char> pool;
    if (mode == 2) {
        unsigned r = rng() % 4u;
        int k = 1 + (int)r;                              // 每个字母各来 k 次
        for (int i = 0; i < 26; i++) for (int j = 0; j < k; j++) pool.push_back((char)('A' + i));
    } else {
        if (mode == 1) for (int i = 0; i < 26; i++) pool.push_back((char)('A' + i));
        unsigned r = rng() % 60u;
        int extra = 20 + (int)r;
        for (int i = 0; i < extra; i++) { unsigned c = rng() % 26u; pool.push_back((char)('A' + c)); }
    }
    shuffle(pool.begin(), pool.end(), rng);

    /* 摊成四行；每行的字母之间随机插空格，档 3 还会混进 . 和 ! */
    size_t p = 0;
    for (int i = 0; i < 4; i++) {
        size_t take = (i == 3) ? pool.size() - p : (pool.size() - p) / (size_t)(4 - i);
        string line;
        for (size_t k = 0; k < take && p < pool.size(); k++, p++) {
            line.push_back(pool[p]);
            unsigned g = rng() % 4u;
            if (g == 0) line.push_back(' ');
            if (mode == 3) {
                unsigned d = rng() % 12u;
                if (d == 0) line.push_back('.');
                if (d == 1) line.push_back('!');
            }
        }
        printf("%s\n", line.c_str());
    }
    return 0;
}