洛谷 P1308 [NOIP 2011 普及组] 统计单词数

// P1308 统计单词数 —— 正解：读一整行，全转小写，逐词切分
//
// ★★ 这道题就是[第 47 章正文](/ch/47-string-basics/)那道题的原题，题面几乎一字不差。
//   ⇒ 所以这一页**不再讲一遍「切词 vs 补空格」**（正文第 4、5、7 步已经讲透了），
//     它去量正文只提了一句、没有称过重量的那一关：**读入**。
//
// ⚠ 这一份里和读入有关的有三处，每一处都对应这一页的一个错法：
//   ① 第二行必须 `getline` 读**一整行** —— `cin >> t` 只会读到第一个空格（见 p1308Word.cpp）；
//   ② `cin >> w` 之后要先把那个残留的换行吃掉，而**不能用 `>> ws`** ——
//      `ws` 会连**文章开头的空格**一起吃掉，而题面说文章「只可能包含字母和空格」，
//      开头就是空格是合法输入，位置会整体偏移（见 p1308Ws.cpp）；
//   ③ 位置要从**原串的下标**来，别拿切出来的词长累加（见 p1308Stream.cpp）。
#include <bits/stdc++.h>
using namespace std;

int main() {
    string w, t;
    if (!(cin >> w)) return 0;
    getline(cin, t);                 // ★ 先吃掉第一行剩下的换行符（正文第 2 步那个坑）
    if (!getline(cin, t)) t = "";    // ⚠ 文章可能是空行 —— 这是合法输入

    for (char& c : w) c = (char)tolower((unsigned char)c);
    for (char& c : t) c = (char)tolower((unsigned char)c);

    long long cnt = 0;
    long long first = -1;
    size_t i = 0, n = t.size();
    while (i < n) {
        while (i < n && t[i] == ' ') i++;             // 跳过空格 -> 停在一个词的开头
        if (i >= n) break;
        size_t j = i;
        while (j < n && t[j] != ' ') j++;             // [i, j) 就是一个完整的词
        if (j - i == w.size() && t.compare(i, j - i, w) == 0) {
            cnt++;
            if (first < 0) first = (long long)i;      // ★ 位置直接就是原串的下标
        }
        i = j;
    }
    if (cnt == 0) printf("-1\n");
    else printf("%lld %lld\n", cnt, first);
    return 0;
}

// P1308 ✗ 错法一：第二行用 `cin >> t` 读
//
// ⚠ 这是这道题上最常见的第一版 —— 它一个字都不错，只是**读少了**：
//   `cin >> t` 遇到空格就停，于是「文章」只剩下第一个单词。
// ⇒ ★ 它的触发条件是一句话：**文章里不止一个词**（也就是几乎所有输入）。
//   而 `-Wall` 不会响、程序不会崩、格式完全正常 —— 它只是**在回答另一道题**：
//   「w 等不等于文章的第一个词」。
#include <bits/stdc++.h>
using namespace std;

int main() {
    string w, t;
    if (!(cin >> w)) return 0;
    if (!(cin >> t)) t = "";                  // ⚠ 只读到第一个空格

    for (char& c : w) c = (char)tolower((unsigned char)c);
    for (char& c : t) c = (char)tolower((unsigned char)c);

    long long cnt = 0, first = -1;
    size_t i = 0, n = t.size();
    while (i < n) {
        while (i < n && t[i] == ' ') i++;
        if (i >= n) break;
        size_t j = i;
        while (j < n && t[j] != ' ') j++;
        if (j - i == w.size() && t.compare(i, j - i, w) == 0) { cnt++; if (first < 0) first = (long long)i; }
        i = j;
    }
    if (cnt == 0) printf("-1\n");
    else printf("%lld %lld\n", cnt, first);
    return 0;
}

// P1308 的生成器：./p1308Gen 种子 [档位]
//
// ★ 动笔之前先写清楚「每个错法靠什么现形」（[第 46 章第 13 步](/ch/46-bitwise/)那张清单）：
//   · p1308Word（`cin >> t`）        → **文章不止一个词**（几乎所有输入，一抓一个准）；
//   · p1308Ws（`>> ws`）             → **文章开头有空格**，而且答案不是 -1；
//   · p1308Stream（位置靠词长累加）  → **第一次命中之前出现过多余的空格**（行首空格 或 连续空格）；
//   · p1308Neg（没找到打 `0 -1`）    → **答案正好是 -1**。
//
// ⚠⚠ 关键在于：后三条要的那些输入，**顺手写的生成器一个都不会造** ——
//   谁会主动在文章开头放空格、在词之间放两个空格？可题面只说文章
//   「只可能包含字母和空格」，这三种全是**合法输入**。
//   ⇒ 这正是[第 20 章 P1020](/sol/p1020/)那条「生成器该照抄题面」的另一面：
//     **照抄的不只是规模，还有题面允许的那些形状。**
//
// 档位：
//   0  ★ 顺手写的：3~12 个词、词间恰好一个空格、开头不留空格
//   1  ⚠ 开头留 1~3 个空格（p1308Ws 的专门档）
//   2  ⚠ 词间 1~3 个空格（p1308Stream 的专门档）
//   3  ★ 最终档：两个旋钮一起开
//   9  ★ 顶格：文章正好 10⁶ 个字符（题面上限）—— 给 p1308Read.cpp 量读入用
//
// ⚠ 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);

    const bool leadSpace = (mode == 1 || mode == 3);
    const bool multiSpace = (mode == 2 || mode == 3);
    const bool huge = (mode == 9);

    /* 词表：几个短词，其中一个是要找的 w —— 短词表才有足够的命中率 */
    const char* pool[] = {"to", "the", "be", "or", "not", "is", "a", "an", "at"};
    const int POOL = 9;
    unsigned r0 = rng() % (unsigned)POOL;
    string w = pool[r0];

    unsigned r1 = rng() % 10u;
    int words = 3 + (int)r1;
    if (huge) words = 1 << 30;                // ★ 顶格档：写满 10⁶ 个字符为止

    string t;
    if (leadSpace) { unsigned r = rng() % 3u; t.append((size_t)(1 + r), ' '); }
    for (int i = 0; i < words; i++) {
        if (huge && t.size() >= 999990) break;    // ★ 顶格档：留出最后一个词的余量
        if (i) {
            int gap = 1;
            if (multiSpace) { unsigned r = rng() % 3u; gap = 1 + (int)r; }
            t.append((size_t)gap, ' ');
        }
        unsigned r = rng() % (unsigned)POOL;
        string x = pool[r];
        /* 大小写随机翻转 —— 题面说「不区分大小写」*/
        for (char& c : x) { unsigned f = rng() % 2u; if (f) c = (char)toupper((unsigned char)c); }
        t += x;
    }
    if (huge) while (t.size() < 1000000) t.push_back('x');   // 补到正好 10⁶

    unsigned rw = rng() % 2u;
    if (rw) for (char& c : w) c = (char)toupper((unsigned char)c);

    printf("%s\n%s\n", w.c_str(), t.c_str());
    return 0;
}

// P1308 —— 四种读法读同一份输入，各自报「读进来花了多少毫秒」。
//   ./p1308Read sync   [文件]   默认的 cin + getline（什么都不关）
//   ./p1308Read nosync [文件]   ios::sync_with_stdio(false) + getline
//   ./p1308Read scanf  [文件]   scanf("%s") + scanf("%[^\n]")
//   ./p1308Read fread  [文件]   一次 fread 把整份输入吞进来，自己切两行
//
// ⚠⚠⚠ 第二个参数不是可有可无的（2026-09-07 在 check:viz 里当场撞出来的）：
//   给了文件就 `freopen` 到 stdin 上 —— **评测机做的正是这件事**（把 stdin 重定向到一个文件）。
//   不给文件时读的是**管道**，而管道那一头是谁、写得多快，**会被一起量进来**：
//   同一个二进制、同一份数据，从文件读 0.7 毫秒，被 node 用管道喂是 3 毫秒以上
//   ——⇒ 关同步那一版快到「它在等喂数据的人」，量到的于是不再是它自己的速度。
//   ⇒ ★★ 这和[第 46 章 P1469](/sol/p1469/) 那条「量内存要量差值，因为起步那一截取决于谁 spawn 它」
//     是同一件事的另一半：**量什么都要先问一句「这个数里有没有别人的份」。**
//
// ★ 为什么要单独量这一关：题面的文章长度是 **10⁶**，
//   而[第 6 章 P2367](/sol/p2367/) / [第 38 章 P1972](/sol/p1972/) 那两页立过一条规矩 ——
//   **四种读法的倍数跨题几乎不变，变的是绝对时间，而分数线在绝对时间上。**
//   ⇒ 所以这道题该不该写读入优化，是一道要**乘一遍**才能回答的题，不能背。
//
// ⚠ 输出里也带上算出来的答案：四种读法**必须给出同一个答案**，
//   否则量到的就是「读丢了一截」而不是「读得快」（[第 12 章 P1923](/sol/p1923/) 那个 33.5 MB 的桶）。
#include <bits/stdc++.h>
using namespace std;

static string answer(string w, string t) {
    for (char& c : w) c = (char)tolower((unsigned char)c);
    for (char& c : t) c = (char)tolower((unsigned char)c);
    long long cnt = 0, first = -1;
    size_t i = 0, n = t.size();
    while (i < n) {
        while (i < n && t[i] == ' ') i++;
        if (i >= n) break;
        size_t j = i;
        while (j < n && t[j] != ' ') j++;
        if (j - i == w.size() && t.compare(i, j - i, w) == 0) { cnt++; if (first < 0) first = (long long)i; }
        i = j;
    }
    char buf[64];
    if (cnt == 0) snprintf(buf, sizeof(buf), "-1");
    else snprintf(buf, sizeof(buf), "%lld %lld", cnt, first);
    return string(buf);
}

static vector<char> big;                       // scanf / fread 两种模式要的落脚处

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "sync";
    if (argc > 2 && !freopen(argv[2], "r", stdin)) { fprintf(stderr, "open failed\n"); return 1; }
    string w, t;

    auto t0 = chrono::steady_clock::now();
    if (mode == "nosync") {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cin >> w;
        getline(cin, t);
        if (!getline(cin, t)) t = "";
    } else if (mode == "scanf") {
        big.assign(1 << 21, 0);
        if (scanf("%s", big.data()) == 1) w = big.data();
        int c = getchar();
        while (c != EOF && c != '\n') c = getchar();
        big[0] = 0;
        if (scanf("%1048576[^\n]", big.data()) == 1) t = big.data(); else t = "";
    } else if (mode == "fread") {
        big.clear();
        char chunk[1 << 16];
        size_t got;
        while ((got = fread(chunk, 1, sizeof(chunk), stdin)) > 0) big.insert(big.end(), chunk, chunk + got);
        size_t p = 0, n = big.size();
        while (p < n && big[p] != '\n') p++;
        w.assign(big.begin(), big.begin() + (long)p);
        size_t q = ++p;
        while (q < n && big[q] != '\n') q++;
        if (p <= n) t.assign(big.begin() + (long)p, big.begin() + (long)min(q, n));
    } else {
        cin >> w;                              // ★ 默认：sync_with_stdio 开着
        getline(cin, t);
        if (!getline(cin, t)) t = "";
    }
    auto t1 = chrono::steady_clock::now();
    double readMs = chrono::duration<double, milli>(t1 - t0).count();

    auto t2 = chrono::steady_clock::now();
    string ans = answer(w, t);
    auto t3 = chrono::steady_clock::now();
    double calcMs = chrono::duration<double, milli>(t3 - t2).count();

    printf("%s,%.2f,%.2f,%zu,%s\n", mode.c_str(), readMs, calcMs, t.size(), ans.c_str());
    return 0;
}