K01 基本功 + 模拟、枚举与字符串（第二轮系统课 · 第 1 次）

这是什么： 第二轮冲刺系统课的第 1 份讲义，对应 10/2 那次 4 小时的课。总安排见 F0_第二轮冲刺总览.md。

本次两个模块：

K 系列的读法： 每一节开头都有一道口算或盲写，先合上讲义做，再往下看。做对了，那一节只看"坑"就行；做不对，再从头读。

一、M1 基本功

口算：8 道，每道 1 分钟（先做再往下读）

写在纸上，每道只写结论和一句理由。1 秒按 10⁸ 次简单运算估（L01 1.3 节）。

1. n ≤ 10⁵，双重循环 for i in 1..n, for j in i..n 做一次加法。1 秒能跑完吗？
2. n ≤ 10⁶，对 n 个数调用一次 sort。能跑完吗？
3. int a[1000000000];（10⁹ 个 int）要多少内存？题目内存限制 512 MB，行不行？
4. long long a[10000000];（10⁷ 个）要多少内存？
5. a、b ≤ 10⁹，写 int c = a * b; 会发生什么？
6. long long x = 5; printf("%d", x); 有什么问题？
7. n ≤ 10⁹，写一个 for (int i = 1; i <= n; i++)，每次循环做一次加法。能过吗？
8. 在 main 函数里面写 int a[1000000];，本地 Dev-C++ 运行会怎样？

📝 7 道以上对 → 1.1、1.2 只看 ⚠️ 标记的地方，直接去 1.3。

1.1 数据范围 → 复杂度，内存也要算

S0 第三节那张表你们见过：

⚠️ 这张表只管时间。还有一张表管内存，很多人从来没算过：

📝 一句话记：数组长度超过 10⁸，不用算了，一定爆。

看一个真实的写法。 分糖果（P7909）有同学这样写：

int n, l, r;
cin >> n >> l >> r;
vector<int> m(r - l, 0);          // ← 开一个长度 r-l 的数组
for (int i = l; i < r; i++) ...   // ← 把每一个数都试一遍

题目写着 r ≤ 10⁹。这一行 vector<int> m(r - l) 最坏要 3.7 GB，评测结果是 MLE、RE、TLE 混在一起。

⚠️ 看到 10⁹ 这个数，脑子里要自动跳出一句话："不能一个一个试，要找规律或者用数学。" 分糖果的正解是一个取模结论（S5 1.1 节），小苹果的正解是按天模拟、每天算一个式子，都和"开数组"无关。

反过来，数据范围也告诉你暴力能拿几分。 小苹果（P9748）的数据表：

n ≤ 10⁶ 时，每天把剩下的苹果重新排一遍，总工作量约 3n ≈ 3×10⁶，开数组老老实实模拟能过前 9 个点，拿 90 分。只有最后一个点要正解。

📝 所以"看数据范围"有两个用处：①判断这个写法会不会超；②判断暴力能拿到第几档。 这就是规矩 1：

// n<=1e9，所以需要 O(log n) 或 O(1)——不能开数组

动手前先写这一行。写不出来，说明还没读完题。

1.2 溢出与输出格式

⚠️ 三个最常见的坑：

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

int main() {
    int a = 1000000000, b = 1000000000;

    long long bad = a * b;          // 坑一：右边先按 int 算，已经溢出了，再存进 long long 也救不回来
    long long good = 1LL * a * b;   // 正确：先把 a 变成 long long 再乘
    cout << (bad == good ? "same" : "different") << endl;
    cout << good << endl;

    long long x = 5;
    printf("%lld\n", x);            // 坑二：long long 用 %lld，不是 %d
    return 0;
}

坑三：别用 long。 它在 Linux 评测机上是 64 位，在 Windows 的 Dev-C++ 里却只有 32 位——本地和评测机结果可能不一样。要么 int，要么 long long。

📝 判断要不要 long long：把题目给的最大值代进去，算一下最大的中间结果。 超过 2×10⁹ 就用 long long。拿不准的时候，全用 long long 几乎不会错（只是内存翻倍）。

⚠️ 座位（P14358）有同学的代码里有一句 printf("%d %d", ...) 输出 long long 变量——本地可能看起来是对的，评测机上不一定。要么全用 cout，要么类型和格式符严格对上。

1.3 自造三组数据（规矩 2）

样例过了不等于对。 样例是出题人给你"看懂题意"用的，不是给你"检查代码"用的。

提交前，自己造三组：

拿乘方（P8813）练一次。 题目：给 a、b（1 ≤ a, b ≤ 10⁹），a^b 超过 10⁹ 输出 -1，否则输出 a^b。

先别看下表，自己写出 3 组以上的数据和正确答案，再对照：

⚠️ 这张表里最关键的是"恰好等于"那一行。 大多数只差最后 10 分的代码，死在 > 和 >= 上。

造最大数据：手打不了 10⁵ 个数，就写个小程序生成：

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

// 生成一组最大数据：n = 100000，每个数在 1~1000000000 之间
int main() {
    freopen("big.in", "w", stdout);
    int n = 100000;
    cout << n << endl;
    srand(12345);
    for (int i = 1; i <= n; i++) {
        long long x = 1LL * rand() * rand() % 1000000000 + 1;
        cout << x << (i == n ? '\n' : ' ');
    }
    return 0;
}

再用自己的程序读 big.in，数一下跑了几秒（Dev-C++ 运行窗口最后会显示用时）。

写在哪里：三组数据写在代码最后的注释里，老师课上抽查：

/* 自造数据
1 1000000000   -> 1
10 9           -> 1000000000
2 30           -> -1
*/

1.4 对拍和考场规程

• 对拍（有暴力时最强的查错法）：见 S7 第二节第 4 步。
• 考场文件流程：见 freopen函数用法教程.md 第 3 节，考前一周会发 F2_考场规程卡。

二、M2 模拟与枚举

L01 第 3 节讲过乘方和小苹果。这里补两套"不管什么题都能用"的问法。

2.1 模拟三步

写模拟之前，先在纸上回答三个问题：

⚠️ 第三问的后半句最容易漏：步数决定能不能直接模拟。 小苹果只要约 50 步，所以按天模拟完全没问题；要模拟的是"天"，不是"每个苹果"。一个苹果开一个格子，就回到 1.1 那 3.7 GB 了。

2.2 枚举三问

题目：公鸡 5 元一只，母鸡 3 元一只，小鸡 1 元三只。用 100 元买 100 只鸡，每种至少 0 只，列出所有买法。

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

int main() {
    // 公鸡最多 20 只（100/5），母鸡最多 33 只（100/3）
    for (int x = 0; x <= 20; x++) {
        for (int y = 0; y <= 33; y++) {
            int z = 100 - x - y;            // 小鸡数量直接算出来，不用第三重循环
            if (z < 0) continue;
            if (z % 3 != 0) continue;       // 小鸡三只一买，不是 3 的倍数就凑不出整数钱
            if (5 * x + 3 * y + z / 3 == 100) {
                cout << x << " " << y << " " << z << endl;
            }
        }
    }
    return 0;
}

📝 判断 z % 3 != 0 那一行：用整数算钱，就不会遇到小数比较的麻烦。能用整数就别用小数，这是枚举题的通用习惯。

三、M2 字符串工具箱

盲写（15 分钟，合上讲义）

读入一整行英文（单词之间可能有多个空格，行首行尾也可能有空格），输出单词个数和最长的单词（一样长输出最早出现的那个）。

输入 I love CSP junior → 输出 4 换行 junior

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

int main() {
    string s;
    getline(cin, s);                 // 读一整行，空格也读进来
    int cnt = 0;
    string best = "";
    int i = 0, n = s.size();
    while (i < n) {
        if (s[i] == ' ') { i++; continue; }        // 跳过空格
        int j = i;
        while (j < n && s[j] != ' ') j++;          // j 停在单词后面第一个空格
        string w = s.substr(i, j - i);             // 第二个参数是长度，不是结束位置
        cnt++;
        if (w.size() > best.size()) best = w;      // 用 > 不用 >=，才能保留最早的
        i = j;
    }
    cout << cnt << endl << best << endl;
    return 0;
}

📝 这个"i 找开头、j 找结尾、substr 切出来"的双指针切分，是字符串题最常用的一个动作。 会了它，统计单词、找单词、替换单词都是它的变形。

3.1 常用函数一张表

3.2 两个例子

例 1：统一大小写后比较（很多题都说"不区分大小写"）：

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

string lower(string s) {
    for (int i = 0; i < (int)s.size(); i++) s[i] = tolower(s[i]);
    return s;
}

int main() {
    string a, b;
    cin >> a >> b;
    cout << (lower(a) == lower(b) ? "same" : "different") << endl;
    return 0;
}

例 2：找出一个串在另一个串里所有出现的位置：

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

int main() {
    string s = "abababa", t = "aba";
    int pos = s.find(t);
    while (pos != (int)string::npos) {
        cout << pos << " ";
        pos = s.find(t, pos + 1);     // 从下一个位置继续找（允许重叠）
    }
    cout << endl;
    return 0;
}

⚠️ pos + 1 还是 pos + t.size()，取决于题目允不允许重叠。 读题时要找这句话。

四、课堂题与小测

所有题都执行三条规矩：先写复杂度注释 → 写代码 → 自造三组数据写在末尾注释。卡住时按 S8 的提示一层一层看，交过一次才准翻标程（前三题在 S10，小苹果在 L01 3.2 节）。

五、课后作业

做法：每题照样三条规矩；AC 之后才算完成，老师看洛谷记录。档位老师当面分配。

难度标注用洛谷的颜色：红 = 入门，橙 = 普及−，黄 = 普及/提高−。

📝 B 档的 P1308 统计单词数，就是第三节盲写题 + 例 1 + 例 2 的组合。 做不出来，先回去把那三段代码再盲写一遍。

六、30 秒自测

1. 看到"n ≤ 10⁹"，第一反应应该是什么？
2. vector<int> v(1000000000); 大概要多少内存？
3. long long c = a * b;（a、b 是 int）哪里错了？
4. s.find(t) 找不到时返回什么？该怎么判断？
5. 自造数据的三组分别是什么？

本次打卡（填进 F0 的知识地图表）：M1 ①（口算 ≥7 对）、M2 ①（盲写题通过）；作业 AC 后打 ②③。