洛谷 P5015 [NOIP 2018 普及组] 标题统计

// P5015 标题统计 —— 正解：读一整行，数「不是空格」的字符
//
// ★ 这道题的全部内容就是一句话：**标题在一行里，而这一行含空格** ⇒ 只能 `getline`。
// ⚠ 三个容易漏的角，全在题面里写着：
//   ① 「空格和换行符不计算在内」—— 换行不是 `getline` 读出来的东西（它把换行吃掉了），
//      所以只要排掉空格；⚠ 换成逐字符读到 EOF 的写法就必须自己排掉换行（见 p5015Nl.cpp）；
//   ② 标题**可以以空格开头**，也可以整行都是空格 ⇒ 答案 0 是合法输出；
//   ③ 题面三档数据范围**一字不差都写着 `1 ≤ |s| ≤ 5`** —— 所以规模这一维在这道题上根本不存在，
//      ⚠ 而这也意味着：**这道题的输入空间小到可以全枚举**（见 p5015All.cpp）。
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    if (!getline(cin, s)) s = "";
    int ans = 0;
    for (char c : s) if (c != ' ' && c != '\r') ans++;   // ⚠ \r 是给带 CRLF 的输入留的保险
    printf("%d\n", ans);
    return 0;
}

// P5015 ✗ 错法一：`cin >> s`
//
// ⚠ 这是这道题上最常见的第一版 —— 它读到第一个空格就停，
//   于是「标题」只剩**第一段**。⇒ 它恒等于在回答另一道题：
//   「标题里**第一个空格之前**有几个字符？」
// ★ 触发条件因此是一句话：**标题被空格切成了两段或更多**。
//   ⚠ 而官方样例一（`234 `）只有一段 ⇒ **它放过这个错法**；样例二（`Ca 45 `）当场打死它。
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    if (!(cin >> s)) s = "";
    printf("%d\n", (int)s.size());
    return 0;
}

// P5015 解析页上所有数字的出处 —— ★ 这一页一个生成器都没写。
//   ./p5015All          人话版
//   ./p5015All csv      给 check:viz 用
//
// ★★★ 为什么不写生成器：题面的三档数据范围**一字不差都写着 `1 ≤ |s| ≤ 5`**
//   ⇒ 100% 档的输入空间是「62 个字母数字 + 空格」里挑 1~5 个，
//     一共 Σ 63^L = **1 008 443 583** 个（10.08 亿）—— 已经能枚举了，但还能再小一步：
//   ★★ **答案只取决于每个字符的「类别」**（空格 / 字母 / 数字），
//     ⇒ 3 类 × 长度 1~5 = **363 个代表输入**就覆盖了那 10.08 亿个。
//   ⚠ 而「只取决于类别」这句话是**验过**的（第 ② 段自检）：
//     拿真实的 63 个字符枚举长度 1~3 的全部 254 079 个输入，逐个和它的代表比 —— 0 个不同。
//
// ⇒ [「输入空间小的时候，算一遍比对拍又快又充分」](/sol/p1002/)的又一次
//   （[第 44 章 P1009](/sol/p1009/) 是 50 个整数、[第 46 章 P5704](/sol/p5704/) 是 26 个字符）。
#include <bits/stdc++.h>
using namespace std;

/* 五个版本，全部写成「输入的原始字节 → 输出」的纯函数（读入方式的差别也在里面） */
static int ansGetline(const string& raw) {              // ★ 正解：getline + 排掉空格
    int n = 0;
    for (char c : raw) { if (c == '\n') break; if (c != ' ' && c != '\r') n++; }
    return n;
}
static int ansChar(const string& raw) {                 // ★ 另一种正确写法：逐字符
    int n = 0;
    for (char c : raw) if (c != ' ' && c != '\n' && c != '\r') n++;
    return n;
}
static int ansCin(const string& raw) {                  // ✗ cin >> s：只拿第一段
    size_t i = 0;
    while (i < raw.size() && (raw[i] == ' ' || raw[i] == '\n')) i++;
    int n = 0;
    while (i < raw.size() && raw[i] != ' ' && raw[i] != '\n') { n++; i++; }
    return n;
}
static int ansNl(const string& raw) {                   // ✗ 换行也数进去
    int n = 0;
    for (char c : raw) if (c != ' ') n++;
    return n;
}
static int ansDigit(const string& raw) {                // ✗ 只数数字字符
    int n = 0;
    for (char c : raw) { if (c == '\n') break; if (c >= '0' && c <= '9') n++; }
    return n;
}

static const char CLS[3] = {' ', 'a', '7'};             // 空格 / 字母 / 数字，各取一个代表

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

    /* ① 363 个代表输入：三个错法各错几个、从哪个长度开始错 */
    int bad[3] = {0, 0, 0};
    int firstLen[3] = {0, 0, 0};
    int total = 0;
    for (int len = 1; len <= 5; len++) {
        int pw = 1;
        for (int k = 0; k < len; k++) pw *= 3;
        for (int code = 0; code < pw; code++) {
            string s;
            int c = code;
            for (int k = 0; k < len; k++) { s.push_back(CLS[c % 3]); c /= 3; }
            string raw = s + "\n";
            total++;
            int ok = ansGetline(raw);
            if (ansChar(raw) != ok) { fprintf(stderr, "两种正确写法对不上：[%s]\n", s.c_str()); return 1; }
            int w[3] = {ansCin(raw), ansNl(raw), ansDigit(raw)};
            for (int i = 0; i < 3; i++)
                if (w[i] != ok) { bad[i]++; if (!firstLen[i]) firstLen[i] = len; }
        }
    }

    /* ② 自检：「答案只取决于字符的类别」—— 拿真实字符枚举长度 1~3 的全部输入 */
    string alpha = " ";
    for (char c = 'a'; c <= 'z'; c++) alpha.push_back(c);
    for (char c = 'A'; c <= 'Z'; c++) alpha.push_back(c);
    for (char c = '0'; c <= '9'; c++) alpha.push_back(c);
    long long checked = 0, mismatch = 0;
    for (int len = 1; len <= 3; len++) {
        long long pw = 1;
        for (int k = 0; k < len; k++) pw *= (long long)alpha.size();
        for (long long code = 0; code < pw; code++) {
            string s, rep;
            long long c = code;
            for (int k = 0; k < len; k++) {
                char ch = alpha[(size_t)(c % (long long)alpha.size())];
                c /= (long long)alpha.size();
                s.push_back(ch);
                rep.push_back(ch == ' ' ? ' ' : (ch >= '0' && ch <= '9' ? '7' : 'a'));
            }
            checked++;
            string ra = s + "\n", rb = rep + "\n";
            if (ansGetline(ra) != ansGetline(rb) || ansCin(ra) != ansCin(rb)
                || ansNl(ra) != ansNl(rb) || ansDigit(ra) != ansDigit(rb)) mismatch++;
        }
    }

    /* ③ 100% 档的真实输入空间有多大 */
    long long space = 0, pw = 1;
    for (int L = 1; L <= 5; L++) { pw *= 63; space += pw; }

    /* ④ 「如果 s 很长」—— 题面把规模这一维锁死了，这里量一下它本来能有多快 */
    string big(1000000, 'a');
    for (size_t i = 7; i < big.size(); i += 7) big[i] = ' ';
    big.push_back('\n');
    auto t0 = chrono::steady_clock::now();
    volatile int sink = ansGetline(big);
    auto t1 = chrono::steady_clock::now();
    double bigMs = chrono::duration<double, milli>(t1 - t0).count();
    (void)sink;

    if (csv) {
        printf("total,%d\n", total);
        printf("badCin,%d\nbadNl,%d\nbadDigit,%d\n", bad[0], bad[1], bad[2]);
        printf("firstCin,%d\nfirstNl,%d\nfirstDigit,%d\n", firstLen[0], firstLen[1], firstLen[2]);
        printf("checked,%lld\nmismatch,%lld\n", checked, mismatch);
        printf("space,%lld\n", space);
        printf("bigFast,%d\n", bigMs < 50.0 ? 1 : 0);
        return 0;
    }

    printf("① 3 类字符 × 长度 1~5 = %d 个代表输入（覆盖 100%% 档的全部 %lld 个输入）\n", total, space);
    printf("   ✗ cin >> s        错 %3d / %d 个，从长度 %d 起开始出现反例\n", bad[0], total, firstLen[0]);
    printf("   ✗ 换行也数进去    错 %3d / %d 个，从长度 %d 起开始出现反例\n", bad[1], total, firstLen[1]);
    printf("   ✗ 只数数字字符    错 %3d / %d 个，从长度 %d 起开始出现反例\n", bad[2], total, firstLen[2]);
    printf("② 自检「答案只取决于字符的类别」：真实字符长度 1~3 共 %lld 个输入，对不上 %lld 个\n",
           checked, mismatch);
    printf("③ 顺带量一下「如果 s 很长」：10⁶ 个字符数一遍 %.2f 毫秒 —— 而题面把 |s| 锁在 5\n", bigMs);
    return 0;
}