A 班 第 1 课：CSP-J 复赛怎么拿分 + 专题一：枚举与模拟

适用对象： 已完成 GESP C++ 1–4 级、能独立完成 GESP 四级编程题、目标 CSP-J 复赛的同学 使用方式： 自学讲义。全套 16 课，每课按 1.5 小时设计——例题必须自己动手写一遍，不许只看 学完本课，你应该能：

1. 说清 CSP-J 复赛的题量、时长、计分方式，以及"部分分"为什么是你的朋友
2. 默写文件输入输出（freopen）模板，知道考场上哪些低级错误会导致 0 分
3. 会用"数据范围 → 复杂度预算"倒推算法该怎么选
4. 独立完成两道 CSP-J T1 级真题（乘方、小苹果）

使用说明：

1. CSP-J 复赛的游戏规则（20 分钟）

1.1 考什么

📝 每道题不是"对/错"两种结果。 一道题通常有 10~25 个测试点（或分成若干子任务），过一个测试点得一份分。T4 拿 20 分和 T4 拿 0 分，差距可能就是一个"暴力"程序。

1.2 部分分策略：暴力是你的朋友

数据范围通常长这样：

对于 40% 的数据，n ≤ 1000； 对于 100% 的数据，n ≤ 1000000。

这句话的意思是：就算你只会 O(n²) 的笨办法，把它写对，就稳拿 40 分。

考场铁律（按顺序执行）：

1. 四道题全部读完再动笔，先做最有把握的
2. 每道题先保证"暴力分"到手，再想优化
3. 剩最后 30 分钟，停止开新题，逐题检查文件名、freopen、样例

1.3 复杂度预算：1 秒 ≈ 10⁸

评测机 1 秒大约能执行 10⁸（一亿）次简单运算。拿到题先看数据范围，倒推你能用什么复杂度：

⚠️ n ≤ 10⁹ 时，for (int i = 1; i <= n; i++) 直接超时。看到 10⁹ 就要警觉：这题不让你逐个枚举。

2. 文件输入输出：不会这个，写对也是 0 分（15 分钟）

2.1 规则

CSP-J 复赛和平时刷题网站最大的区别：程序从文件读入，向文件输出，不是键盘和屏幕。

假设题目名是 apple，考场要求：

• 在指定的选手目录下建立文件夹 apple，代码保存为 apple/apple.cpp
• 程序从 apple.in 读入，输出写到 apple.out

2.2 模板（在 GESP 模板基础上加两行）

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

int main() {
    freopen("apple.in", "r", stdin);
    freopen("apple.out", "w", stdout);
    // 下面正常写 cin / cout，不用改任何东西
    int n;
    cin >> n;
    cout << n * 2 << endl;
    return 0;
}

freopen 的作用是把 cin 的来源改成 apple.in、把 cout 的去向改成 apple.out。加了这两行之后，其余代码和你平时写的一模一样。

2.3 在 Dev-C++ 里练习文件输入输出

本课程统一用 Dev-C++ 5.11 写代码（新建源代码 Ctrl+N，保存 Ctrl+S，编译运行 F11）。带 freopen 的程序这样测试：

1. 把代码保存为 apple/apple.cpp（先建好题目文件夹）
2. 在同一个文件夹里新建文本文件，重命名为 apple.in（注意别变成 apple.in.txt，需要在资源管理器里打开"显示文件扩展名"），写入测试数据并保存
3. 按 F11 运行——黑窗口一闪而过、什么都不显示是正常的，因为输出进了文件
4. 打开同文件夹下新出现的 apple.out，核对答案

⚠️ 运行后黑窗口空白 ≠ 程序坏了。用了 freopen，答案就不在屏幕上，在 .out 文件里。

⚠️ 爆零清单（每年都有人踩，考前最后 30 分钟逐条检查）：

1. 文件名写错：题目叫 apple，你写成 Apple.in、aple.in——0 分
2. 本地调试时把 freopen 注释掉了，交卷前忘了恢复——0 分
3. 代码没存进指定的题目文件夹，或文件夹名大小写不对——0 分
4. 调试用的多余输出（如 cout << "debug" << endl;）没删——答案错
5. 程序末尾写了 system("pause") 或等待输入——超时

📝 从今天起，每道练习题都按考场格式写 freopen（做网站题时再注释掉），把肌肉记忆练出来。

3. 专题一：枚举与模拟（40 分钟）

枚举和模拟是 T1 的绝对主力：不需要高级算法，需要的是"读懂题 + 写对代码 + 算清复杂度"。

• 枚举：把所有可能的答案一个个试过去，用循环代替聪明
• 模拟：题目说什么规则，你就用代码原样照做

3.1 例题一：乘方（CSP-J 2022 T1）

输入两个正整数 a 和 b（1 ≤ a, b ≤ 10⁹），求 aᵇ 的值。如果 aᵇ > 10⁹，输出 -1。

输入样例1：      输入样例2：
10 9             2 31

输出样例1：      输出样例2：
1000000000       -1

第一步：先想暴力。 循环 b 次，每次乘一个 a：

ans = 1
重复 b 次：ans = ans * a

第二步：算复杂度预算。 b 最大 10⁹，循环 10⁹ 次——超时了？

先别慌，再想一层：只要 a ≥ 2，乘 31 次就超过 10⁹ 了（2³¹ ≈ 2.1 × 10⁹）。所以循环里一旦发现 ans > 10⁹ 就立刻输出 -1 结束，循环实际最多跑 30 多次。

第三步：找漏网之鱼。 什么情况下 ans 永远不会超过 10⁹、循环会傻跑 b 次？——a = 1。1 乘多少次都是 1，b = 10⁹ 时循环真的会跑 10⁹ 次，超时。所以 a = 1 要特判。

完整代码：

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

int main() {
    freopen("pow.in", "r", stdin);
    freopen("pow.out", "w", stdout);
    long long a, b;
    cin >> a >> b;
    if (a == 1) {           // 特判：不特判就会超时
        cout << 1 << endl;
        return 0;
    }
    long long ans = 1;
    for (long long i = 1; i <= b; i++) {
        ans = ans * a;
        if (ans > 1000000000) {   // 超过 10^9 立刻收工
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;
    return 0;
}

⚠️ 两个易错点：

1. ans 必须用 long long。10⁹ × 10⁹ 会把 int 撑爆（int 上限约 2.1 × 10⁹），乘完再判断就晚了
2. 特判 a == 1 忘了写，能过大部分测试点，但 a = 1、b = 10⁹ 的那个测试点会超时——这就是"100 分和 90 分的区别在细节"

📝 T1 解题三步：想暴力 → 对着数据范围算复杂度 → 找特殊情况。

3.2 例题二：小苹果（CSP-J 2023 T1）

桌上有 n 个苹果排成一排（1 ≤ n ≤ 10⁹）。每天从第 1 个开始，每隔 2 个取走 1 个（即取走当天的第 1、4、7、… 个），剩下的苹果保持顺序重新排好，第二天继续。 求：(1) 取完所有苹果需要多少天；(2) 最初的第 n 个苹果（最后一个）在第几天被取走。

输入样例：
8

输出样例：
5 5

第一步：拿样例手玩一遍。 n = 8，每天取位置 1, 4, 7, …：

5 天取完 ✓。手玩发现两个规律：

• 当天有 m 个苹果，取走的个数是 ⌈m/3⌉（m 除以 3 向上取整，代码里写 (m + 2) / 3）
• 最初的第 n 个苹果永远排在最后（取苹果只会取它前面的，不改变它"最后一名"的位置）。它被取走，当且仅当某天开始时 m % 3 == 1（此时位置 1, 4, 7, …, m 正好包含最后一位）

第二步：算复杂度。 不能一个个苹果模拟（n 到 10⁹），但可以按天模拟苹果总数：每天 m 变成 m − ⌈m/3⌉，约缩小到 2/3，10⁹ 只需要约 50 天。O(log n)，随便过。

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

int main() {
    freopen("apple.in", "r", stdin);
    freopen("apple.out", "w", stdout);
    long long n;
    cin >> n;
    long long m = n, days = 0, lastDay = 0;
    while (m > 0) {
        days++;
        if (m % 3 == 1 && lastDay == 0) {
            lastDay = days;        // 最后一个苹果在今天被取走
        }
        m = m - (m + 2) / 3;       // 取走 ⌈m/3⌉ 个
    }
    cout << days << " " << lastDay << endl;
    return 0;
}

📝 模拟题的降维套路：不模拟每个"个体"，模拟"数量"。 把 O(n) 的模拟压成 O(log n) 或 O(天数)。

📝 手玩样例不是浪费时间。 上面两个规律都是列表格玩出来的，不动手很难凭空想到。

4. 本课练习（15 分钟起步，剩下的当课后作业）

每题按考场格式建文件夹、写 freopen（文件名用题目名）。

⭐ 热身 1：默写模板（题目名 t1）

合上讲义，默写带 freopen 的完整模板，编译通过为准。

⭐ 热身 2：3 或 5 的倍数（题目名 mul）

输入 n（1 ≤ n ≤ 10⁶），输出 1~n 中能被 3 或 5 整除的数的个数与总和，空格分隔。

输入样例：
10

输出样例：
5 33

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

int main() {
    freopen("mul.in", "r", stdin);
    freopen("mul.out", "w", stdout);
    int n;
    cin >> n;
    long long cnt = 0, sum = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 3 == 0 || i % 5 == 0) {
            cnt++;
            sum += i;
        }
    }
    cout << cnt << " " << sum << endl;
    return 0;
}

⭐⭐ 实战：数字统计（NOIP 2010 普及组 T1，题目名 two）

输入两个整数 L 和 R（1 ≤ L ≤ R ≤ 10⁵），统计 L~R 的所有整数中，数字 2 一共出现了多少次。例如 22 里有两个 2。

输入样例：
2 22

输出样例：
6

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

int main() {
    freopen("two.in", "r", stdin);
    freopen("two.out", "w", stdout);
    int l, r;
    cin >> l >> r;
    int cnt = 0;
    for (int i = l; i <= r; i++) {
        int x = i;
        while (x > 0) {
            if (x % 10 == 2) cnt++;   // 看个位
            x = x / 10;               // 砍掉个位
        }
    }
    cout << cnt << endl;
    return 0;
}

⭐⭐⭐ 冲刺：约数个数（题目名 div）

输入 n（1 ≤ n ≤ 10¹²），输出 n 的约数（因数）个数。

先想：从 1 枚举到 n 是什么复杂度？过得了吗？过不了怎么办？（提示：约数总是成对出现的——如果 i 整除 n，那么 n/i 也整除 n。）

输入样例：
12

输出样例：
6

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

int main() {
    freopen("div.in", "r", stdin);
    freopen("div.out", "w", stdout);
    long long n;
    cin >> n;
    long long cnt = 0;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cnt += 2;              // i 和 n/i 配一对
            if (i * i == n) cnt--; // 完全平方数：i 和 n/i 是同一个，别数两次
        }
    }
    cout << cnt << endl;
    return 0;
}

本课要点速查

考场模板（默写级）：

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

int main() {
    freopen("题目名.in", "r", stdin);
    freopen("题目名.out", "w", stdout);

    return 0;
}

复杂度预算表：

爆零清单： 文件名错、freopen 注释没恢复、文件夹没建对、调试输出没删、system("pause") 没删。

T1 解题三步： 想暴力 → 对数据范围算复杂度 → 找特殊情况（a=1、n=0、完全平方数……）。

本课新零件： freopen、(m + 2) / 3 向上取整、while (x > 0) { x % 10; x /= 10; } 拆位、i * i <= n 枚举到根号。

结束前的自我检查

1. 合上讲义能默写带 freopen 的模板
2. 乘方、小苹果两道例题不看答案重写一遍，用样例验证
3. 星级练习全部完成（⭐⭐⭐ 想不出来允许看提示，但看完提示要独立写码）
4. 用一句话向别人解释："为什么 n ≤ 10⁹ 的题不能写 O(n) 循环？"