~/陈老师

courses/cpp

C++ 与基础算法 · 5 年级~初一，竞赛主轨道

竞赛核心 C++ 5 年级~初一

课程简介

这是进入信息学竞赛主轨道的关键课程。以 NOI 系列竞赛使用的 C++ 为主语言，本课程不是"把语法念一遍"，而是每个知识点都配可运行示例、真实运行结果与动手练习，让孩子既看得懂代码，也跑得通代码。

课程按 语法基础 → 分支循环 → 数组字符串 → 函数递归 → 结构体排序 → 基础算法 → 搜索入门 → 综合测评 八章递进，共 32 次课。每章末尾都有两级练习，配套在线题库、每周周赛与错题复盘，把知识真正转化为解题能力。

适合对象

  • 5 年级~初一，有 Python 基础或通过入学测评。
  • 数学基础较好、逻辑清晰，对编程有持续兴趣。
  • 目标参加 CSP-J/S、NOIP 等官方竞赛。
先学 Python 还是直接 C++？没有 Python 基础、年级又偏低的孩子，建议先上 Python 过渡一学期（打字、代码感觉、调试习惯都能建立起来）；已经学过 Python 或 Scratch 概念很熟、且确定走竞赛的孩子，可以直接从本课进入 C++。拿不准的话，联系我做一次免费测评，10 分钟就知道孩子适合哪条路。

课程大纲

syllabus.sh
第1章  C++ 语法基础：cin/cout、变量与类型
第2章  分支与循环：if、for、while
第3章  数组与字符串
第4章  函数与递归
第5章  结构体与排序
第6章  基础算法：枚举、模拟、贪心、二分
第7章  搜索入门：DFS / BFS
第8章  综合测评与竞赛适应

课程内容

↑ 目录第 1 章 C++ 语法基础：cin/cout、变量与类型

本章目标：搭好竞赛开发环境，认识程序基本结构与编译运行过程，掌握 cin / cout、常用数据类型与运算符。

1.1 搭建环境：Dev-C++ 还是 VS Code

竞赛练习最常用两个环境：

  • Dev-C++：开箱即用，安装后直接写代码，F11 编译运行，适合低年级起步。
  • VS Code：装 C/C++ 插件后更接近竞赛"命令行 + 文本编辑器"的真实方式，适合进阶。

无论选哪个，都要理解编译运行这一步：源代码（.cpp 文件）要经过编译器"翻译"成机器能执行的程序，再运行。所以写错一个分号，编译器会直接报错，这正是孩子练习"对照报错找问题"的机会。

1.2 第一个程序与程序结构

C++ 程序有一个固定的"骨架"，先背下来，后面的代码都往这个架子里填：

hello.cpp
#include <iostream>   // 输入输出库
using namespace std;   // 名字空间

int main() {           // 程序入口
    cout << "Hello, C++!" << endl;
    cout << "我是陈老师的学生" << endl;
    return 0;          // 正常结束
}
运行结果
Hello, C++!
我是陈老师的学生

每个部分的作用：#include <iostream> 引入输入输出功能；int main() 是程序入口，所有代码都从这里开始执行；cout << 是输出，"流出去"到屏幕；<< endl 换行；每条语句末尾必须有分号 ;，这是 C++ 最常见的报错来源。

C++ 严格区分大小写，Main 和 main 是两个名字；每条语句后忘记写分号，编译器会在下一行报错，看到报错往上看一行即可。

1.3 cin/cout 输入输出

cin >> 是输入，"流进来"到变量里。竞赛第一课就是经典的 A+B 问题（洛谷 P1001）：

aplusb.cpp
#include <iostream>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}
运行示例（输入 → 输出）
输入：3 5
输出：8

输入：123456789012 987654321098
输出：1111111110110
做加法先估算结果范围：int 最大约 21 亿（2,147,483,647），超过就上 long long。A+B 这道题用了 long long，因为数据范围可能很大。

1.4 变量与数据类型

C++ 里每一个变量都要先声明类型，编译器才知道给它留多大空间。四种常用类型：

types.cpp
#include <iostream>
using namespace std;

int main() {
    int a = 5;                  // 整数，约 ±21 亿
    long long big = 3000000000LL; // 长整数，够竞赛用
    double pi = 3.14159;        // 小数（浮点数）
    char ch = 'A';              // 单个字符，用单引号
    bool ok = true;             // 真/假
    cout << "a=" << a << " big=" << big << endl;
    cout << "pi=" << pi << " ch=" << ch << " ok=" << ok << endl;
    return 0;
}
运行结果
a=5 big=3000000000 pi=3.14159 ch=A ok=1

怎么选类型？整数用 int，怕超范围用 long long，要小数用 double，一个字母用 char，判断真假用 bool。字符必须用单引号，字符串才用双引号。

1.5 运算符与类型转换

算术、比较、逻辑运算符和数学课几乎一一对应，但有三个 C++ 特有的"坑"：

calc.cpp
#include <iostream>
using namespace std;

int main() {
    cout << 7 / 2 << endl;        // 整数除法：3
    cout << 7.0 / 2 << endl;      // 小数除法：3.5
    cout << 7 % 3 << endl;        // 取余数：1
    int x = 7, y = 2;
    double q = (double)x / y;     // 强制转换成小数
    cout << q << endl;
    int a = 3.99;                 // 小数赋给整数：自动截断
    cout << a << endl;
    char c = '0';
    int d = c - '0';              // 字符转数字
    cout << d << endl;
    return 0;
}
运行结果
3
3.5
1
3.5
3
0
① 7 / 2 得 3 而不是 3.5——两个整数相除结果还是整数（小数部分被舍去）。② int a = 3.99 不会四舍五入，而是直接截断成 3。③ 想算小数，先让一边变成小数，如 (double)x / y。

基础练习：输入两个整数，输出它们的和、差、积、商（整除）、余数，共 5 行。

挑战练习：输入一个三位数，用 / 和 % 拆出百位、十位、个位，输出这三个数的和。提示：百位是 n / 100，个位是 n % 10。

↑ 目录第 2 章 分支与循环：if、for、while

本章目标：掌握 if / else if / else 多分支与 switch，熟练使用 for、while 循环、break / continue 与嵌套循环。

2.1 if / else if / else 多分支

if 就像岔路口，条件成立走一边，不成立走另一边。注意多个分支按顺序判断，命中一个就停下：

judge.cpp
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n % 2 == 0 && n % 3 == 0)
        cout << "既能被2整除也能被3整除" << endl;
    else if (n % 2 == 0)
        cout << "只能被2整除" << endl;
    else
        cout << "不能被2整除" << endl;
    return 0;
}
运行示例（输入 → 输出）
输入：6
输出：既能被2整除也能被3整除

输入：2
输出：只能被2整除

输入：3
输出：不能被2整除

条件里可以组合比较运算符（>、==、!=）和逻辑运算符（&& 且、|| 或、! 非）。判断"相等"要写两个等号 ==。

2.2 switch 多分支

当判断的是"某个变量的值等于几"这种问题时，switch 比一长串 if 更清晰。注意每个 case 末尾的 break 不能漏，否则会"穿透"继续执行下一个分支：

switch.cpp
#include <iostream>
using namespace std;

int main() {
    int day;
    cin >> day;
    switch (day) {
        case 1: cout << "星期一" << endl; break;
        case 2: cout << "星期二" << endl; break;
        case 3: cout << "星期三" << endl; break;
        case 4: cout << "星期四" << endl; break;
        case 5: cout << "星期五" << endl; break;
        default: cout << "周末啦" << endl; break;
    }
    return 0;
}
运行示例
输入：3
输出：星期三

输入：7
输出：周末啦
case 3: 后面的冒号不能写成 ==；漏写 break 会让程序从上往下"穿透"执行后面所有分支，这是 switch 最高频的 bug。

2.3 for 循环与累加器

for 循环三个部分：起点、条件、变化。for (int i = 1; i <= 100; i++) 表示从 1 到 100 每次加 1。累加求和是最经典的应用：

sum.cpp
#include <iostream>
using namespace std;

int main() {
    long long sum = 0;
    for (int i = 1; i <= 100; i++)
        sum += i;                 // 累加器：每次加 i
    cout << "1+2+...+100 = " << sum << endl;

    for (int i = 10; i >= 1; i--) // 倒着数
        cout << i << " ";
    cout << endl;
    return 0;
}
运行结果
1+2+...+100 = 5050
10 9 8 7 6 5 4 3 2 1

i++ 就是 i = i + 1，sum += i 就是 sum = sum + i。<= 还是 <、从 0 开始还是从 1 开始，是循环最常见的边界错误，先想清楚再写。

2.4 while 循环与 break/continue

不知道要循环多少次时用 while。用 break 强行退出循环，用 continue 跳过本次继续下一轮：

while.cpp
#include <iostream>
using namespace std;

int main() {
    int n = 1, cnt = 0;
    while (n <= 1000) { n *= 2; cnt++; }   // 翻倍到超过 1000
    cout << "翻倍 " << cnt << " 次后 n=" << n << endl;

    for (int i = 1; i <= 10; i++) {
        if (i % 2 == 0) continue;   // 偶数跳过
        cout << i << " ";
    }
    cout << endl;
    return 0;
}
运行结果
翻倍 10 次后 n=1024
1 3 5 7 9
while 最怕死循环——循环条件永远成立就永远跑不完。写循环前先确认：循环变量一定会变、最终一定会让条件不成立。开发时先跑小数据验证。

2.5 循环嵌套与枚举

外层循环每走一步，内层循环完整跑一遍。最经典的例子是枚举所有三位数并判断"水仙花数"（每位数字的立方和等于它本身）：

narcissus.cpp
#include <iostream>
using namespace std;

int main() {
    for (int i = 100; i <= 999; i++) {
        int a = i / 100;        // 百位
        int b = i / 10 % 10;    // 十位
        int c = i % 10;         // 个位
        if (a * a * a + b * b * b + c * c * c == i)
            cout << i << " ";
    }
    cout << endl;
    return 0;
}
运行结果
153 370 371 407
拆位是竞赛高频基本功：除以大单位取高位，取余小单位取低位。拆百位 /100，十位先 /10 再 %10，个位直接 %10。

基础练习：输入 n，输出 1 到 n 之间所有既能被 2 整除也能被 3 整除的数。

挑战练习：用嵌套循环打印九九乘法表，要求对齐成三角形。提示：外层管行，内层管到第几列，每行结尾输出换行。

↑ 目录第 3 章 数组与字符串

本章目标：掌握一维、二维数组的定义、下标访问与越界风险，学会用 string 处理文本，为后续算法打底。

3.1 一维数组与下标

数组是"一排带编号的格子"。注意下标从 0 开始：第 1 个数在 a[0]，第 n 个数在 a[n-1]。求最大值是最常见的遍历：

max.cpp
#include <iostream>
using namespace std;

int main() {
    int a[105], n;
    cin >> n;
    int mx = -1e9;               // 初始成很小的数
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] > mx) mx = a[i]; // 遇到更大的就更新
    }
    cout << "最大值：" << mx << endl;
    return 0;
}
运行示例（输入 → 输出）
输入：
5
8 3 12 5 7
输出：最大值：12
数组下标从 0 开始，遍历时最容易写成 i <= n 多访问一个格子。竞赛中数组多开 5~10 个余量（要 100 个就开 a[105]），防止越界导致莫名错误。

3.2 逆序输出与计数

数组可以"记住"所有数据，这正是它比循环强的地方——先存下来，后面再回来用。逆序输出就是倒着访问下标：

reverse.cpp
#include <iostream>
using namespace std;

int main() {
    int a[105], n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = n - 1; i >= 0; i--)  // 从最后一个往前
        cout << a[i] << " ";
    cout << endl;
    return 0;
}
运行示例
输入：
5
1 2 3 4 5
输出：5 4 3 2 1

统计出现次数是计数数组的经典应用：开一个数组 cnt[x]，碰到 x 就让 cnt[x]++，一次遍历统计完所有数的次数。

3.3 二维数组

二维数组像一张表格：a[行][列]。外层循环管行，内层管列。求某一行的和：

table.cpp
#include <iostream>
using namespace std;

int main() {
    int a[3][4];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 4; j++)
            a[i][j] = i * 4 + j + 1;   // 填 1~12
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++)
            cout << a[i][j] << " ";
        cout << endl;                  // 一行结束换行
    }
    long long s = 0;
    for (int j = 0; j < 4; j++) s += a[0][j];
    cout << "第0行之和：" << s << endl;
    return 0;
}
运行结果
1 2 3 4
5 6 7 8
9 10 11 12
第0行之和：10
把二维数组想象成教室里"排和座"，a[行][列] 就是某排某座的同学。写 cin >> a[i][j] 的双重循环，就是按"先排后座"的次序读进来。

3.4 string 字符串

string 是 C++ 处理文本的利器，长度、拼接、查找、替换、切片都有现成操作：

string.cpp
#include <iostream>
#include <string>
using namespace std;

int main() {
    string s = "hello";
    string t = "world";
    string u = s + " " + t;         // 拼接
    cout << "长度=" << s.length() << " u=" << u << endl;
    cout << "第一个l在第" << s.find('l') << "位" << endl;
    s[0] = 'H';                     // 像数组一样改字符
    cout << "改后=" << s << endl;
    cout << "前5个字符=" << u.substr(0, 5) << endl;
    return 0;
}
运行结果
长度=5 u=hello world
第一个l在第2位
改后=Hello
前5个字符=hello
s.find('l') 找到返回下标（从 0 开始），找不到返回一个很大的数 npos，用 if (s.find(x) == string::npos) 判断"没找到"。

基础练习：读入 n 个数，先逆序输出，再输出最大值和最小值。

挑战练习：读入一个只含小写字母的单词，统计每个字母出现次数，并输出出现最多的字母。提示：cnt[c - 'a']，用字符减 'a' 得到 0~25 的下标。

↑ 目录第 4 章 函数与递归

本章目标：学会用函数把大问题拆成小积木，理解值传递与引用传递，掌握递归"自己调用自己"的核心思想。

4.1 函数定义与返回值

函数就是"自己造的积木"：返回值类型 + 函数名 + 参数。定义一次，随处调用：

abs.cpp
#include <iostream>
using namespace std;

int myabs(int x) {
    if (x < 0) return -x;
    return x;
}

int main() {
    cout << myabs(-7) << endl;
    cout << myabs(5) << endl;
    return 0;
}
运行结果
7
5

return 有两个作用：返回结果和立即结束函数。void 型函数不返回结果，只执行动作（比如打印）。函数写在 main 前面，或在前面先声明，main 才能调用它。

4.2 值传递与引用传递

普通参数是"值传递"——函数拿到的是副本，改副本不影响原变量。想让函数真的改变外面的变量，参数前加 & 变成"引用传递"：

swap.cpp
#include <iostream>
using namespace std;

void swap2(int &a, int &b) {   // & 表示引用传递
    int t = a;
    a = b;
    b = t;
}

int main() {
    int x = 3, y = 8;
    cout << "交换前：" << x << " " << y << endl;
    swap2(x, y);
    cout << "交换后：" << x << " " << y << endl;
    return 0;
}
运行结果
交换前：3 8
交换后：8 3
如果 swap2 的参数不加 &，函数里确实交换了，但那是两个副本，main 里的 x、y 纹丝不动——这是"为什么我的交换没生效"最经典的答案。

4.3 递归思想：自己调用自己

递归是"把一个大问题，拆成一个更小的同类型问题"。斐波那契数列就是最标准的例子：第 n 项 = 前两项之和。

fib.cpp
#include <iostream>
using namespace std;

long long fib(int n) {
    if (n <= 2) return 1;          // 终止条件
    return fib(n - 1) + fib(n - 2); // 拆成更小的自己
}

int main() {
    int n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}
运行示例
输入：10
输出：55
写递归三要素：终止条件（什么时候停下）、递归表达式（怎么拆小）、返回值含义（这个函数代表什么）。先写好终止条件再写递归调用，避免无限递归。

4.4 汉诺塔：递归的巅峰体验

汉诺塔问题——把 n 个盘子从 A 移到 C，每次只能移一个，大盘不能压小盘。递归解法只有三句话，却解决了指数级的移动过程：

hanoi.cpp
#include <iostream>
using namespace std;

long long cnt = 0;

void hanoi(int n, char from, char tmp, char to) {
    if (n == 0) return;                     // 没有盘子就不动
    hanoi(n - 1, from, to, tmp);            // 1. 上面 n-1 个先挪到中间
    cnt++;                                  // 2. 最大的盘子挪到目标
    cout << "把盘" << n << "从" << from << "移到" << to << endl;
    hanoi(n - 1, tmp, from, to);            // 3. 中间 n-1 个再挪到目标
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    cout << "共移动 " << cnt << " 次" << endl;
    return 0;
}
运行示例（n=3）
把盘1从A移到C
把盘2从A移到B
把盘1从C移到B
把盘3从A移到C
把盘1从B移到A
把盘2从B移到C
把盘1从A移到C
共移动 7 次

3 个盘子要 7 次，n 个盘子要 2^n - 1 次，所以 n 稍大就非常慢。递归的代码极其简洁，代价是运行可能很慢——这为后面学"记忆化""动态规划"埋下伏笔。

基础练习：用函数写一个求阶乘的 fac(n)，再在主函数里输出 1 到 10 的阶乘。

挑战练习：用递归计算 1 到 n 的和，并画出 sum(3) 的调用过程图；再想想汉诺塔 4 个盘子要移几次，验证 2^4 - 1 = 15。

↑ 目录第 5 章 结构体与排序

本章目标：用 struct 把关联数据捆在一起，理解经典排序原理，学会用 sort 高效排序。

5.1 结构体：给数据分组

一个学生的"姓名 + 分数"是关联的，分别存进两个数组容易搞混。用 struct 定义一种新"数据类型"，把字段打包在一起：

student.cpp
#include <iostream>
using namespace std;

struct Student {          // 自定义类型
    string name;
    int score;
};

int main() {
    Student a = {"小明", 90};
    Student b = {"小红", 95};
    cout << a.name << " " << a.score << endl;
    if (a.score > b.score)
        cout << a.name << " 分数高" << endl;
    else
        cout << b.name << " 分数高" << endl;
    return 0;
}
运行结果
小明 90
小红 分数高

定义结构体时注意：大括号末尾有分号 };。访问字段用点号 a.name。Student s[105] 还可以开结构体数组，一批学生一起处理。

5.2 冒泡排序原理

冒泡排序的思路：每一趟把"当前最大"像气泡一样浮到最后。理解它不是为了用它（有更快的 sort），而是为了理解"排序到底做了什么"：

bubble.cpp
#include <iostream>
using namespace std;

int main() {
    int a[10] = {6, 3, 8, 1, 9, 2, 7, 4, 5, 0};
    int n = 10;
    for (int i = 0; i < n - 1; i++)          // n-1 趟
        for (int j = 0; j < n - 1 - i; j++)  // 每趟少比一个
            if (a[j] > a[j + 1]) {           // 相邻比较交换
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
            }
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
运行结果
0 1 2 3 4 5 6 7 8 9
内层循环边界是 j < n - 1 - i，不是 n - 1。已经浮到后面的最大值不该再比较，漏写 - i 不会错，但会多做无用功，还容易越界。

5.3 sort 与自定义比较

竞赛里用 sort 就够了。默认升序排数字；结构体排序需要自己写"比较规则"告诉它怎么比：

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

struct Student {
    string name;
    int score;
};

bool cmp(Student a, Student b) {
    if (a.score != b.score) return a.score > b.score; // 分高在前
    return a.name < b.name;                           // 同分姓名字典序
}

int main() {
    Student s[5] = {
        {"小刚", 88}, {"小明", 92}, {"小红", 92},
        {"小丽", 95}, {"小强", 88}
    };
    int n = 5;
    sort(s, s + n, cmp);
    for (int i = 0; i < n; i++)
        cout << s[i].name << " " << s[i].score << endl;
    return 0;
}
运行结果
小丽 95
小明 92
小红 92
小刚 88
小强 88
cmp(a, b) 返回 true 表示"a 应该排在 b 前面"。想让谁在前，就写谁得分高：降序写 a.score > b.score，升序写 <。

基础练习：读入 n 个数，用 sort 从小到大排序后输出。

挑战练习：定义 Student 结构体，读入姓名和三科成绩，按总分从高到低输出成绩单，同分时按姓名拼音升序。提示：cmp 里先比分总分，再比名字。

↑ 目录第 6 章 基础算法：枚举、模拟、贪心、二分

本章目标：系统学习竞赛四大基础算法，养成"先估算复杂度再写码"的习惯。

6.1 枚举：穷举所有可能

枚举就是把所有可能都试一遍，找到符合条件的答案。经典"百钱买百鸡"：公鸡 5 文一只、母鸡 3 文一只、小鸡 1 文三只，100 文买 100 只：

chicken.cpp
#include <iostream>
using namespace std;

int main() {
    for (int x = 0; x <= 100; x++)         // 公鸡数
        for (int y = 0; y <= 100; y++) {   // 母鸡数
            int z = 100 - x - y;           // 小鸡数
            if (z < 0 || z % 3 != 0) continue;
            if (5 * x + 3 * y + z / 3 == 100)
                cout << "公鸡" << x << " 母鸡" << y
                     << " 小鸡" << z << endl;
        }
    return 0;
}
运行结果
公鸡0 母鸡25 小鸡75
公鸡4 母鸡18 小鸡78
公鸡8 母鸡11 小鸡81
公鸡12 母鸡4 小鸡84
枚举要先算清楚"层数和范围"。两层循环是 100×100 = 1 万 次没问题；三层到 100 万次也能接受；超过 10^7 就要警惕超时。写枚举前先估算复杂度。

6.2 模拟：按规则一步步来

模拟题就是"题目说怎么做，代码就怎么做"，考验读题和细心。要点：把规则逐条翻译成代码，特别注意边界（开头/结尾、第一天/最后一天）。

simulate.cpp
#include <iostream>
using namespace std;

int main() {
    // 模拟：小明每天攒 2 元，每 7 天花掉 5 元，问 30 天后剩多少
    int money = 0;
    for (int day = 1; day <= 30; day++) {
        money += 2;
        if (day % 7 == 0) money -= 5;
    }
    cout << "30天后剩 " << money << " 元" << endl;
    return 0;
}
运行结果
30天后剩 40 元
验证模拟题的好办法：把天数改成小数字自己手算。比如上面改成 7 天，手算应该剩 9 元（每天 2 元共 14，第 7 天花 5），和程序对照，逻辑对不对一目了然。

6.3 贪心：每一步取当前最优

贪心算法在每一步都做"当前看来最好"的选择，往往能得到整体最优。经典"排队打水"：每个人打水时间不同，如何让所有人等待总和最短？答案是按时间短的先打：

queue.cpp
#include <iostream>
#include <algorithm>
using namespace std;

struct Water { int id, t; };
bool cmpW(Water a, Water b) { return a.t < b.t; }

int main() {
    Water w[5] = {{1,3},{2,1},{3,2},{4,5},{5,4}};
    sort(w, w + 5, cmpW);          // 打水时间短的先
    long long wait = 0, sum = 0;   // wait: 当前排队等待
    for (int i = 0; i < 5; i++) {
        sum += wait;               // 这人等了 wait 分钟
        wait += w[i].t;            // 他打完后累计排队增加
    }
    cout << "总等待时间=" << sum << endl;
    cout << "打水顺序：";
    for (int i = 0; i < 5; i++) cout << w[i].id << " ";
    cout << endl;
    return 0;
}
运行结果
总等待时间=20
打水顺序：2 3 1 5 4
贪心不是万能钥匙——"每一步局部最优"只在特定问题上等于"整体最优"。判断一个题能不能用贪心，要想清楚有没有反例。想不出来反例、又能证明每次最优选择不破坏后续选择，才敢用它。

6.4 二分查找：在有序世界里迅速缩小范围

在有序数组中查找一个数，二分每次把范围砍一半：10 万 个数据最多 17 次就能找到。前提是数据有序：

binary.cpp
#include <iostream>
using namespace std;

int main() {
    int a[10] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int n = 10, x;
    cin >> x;
    int l = 0, r = n - 1, ans = -1;   // -1 表示没找到
    while (l <= r) {
        int mid = (l + r) / 2;        // 取中间
        if (a[mid] == x) { ans = mid; break; }
        else if (a[mid] < x) l = mid + 1;  // 目标在右边
        else r = mid - 1;                  // 目标在左边
    }
    cout << ans << endl;
    return 0;
}
运行示例
输入：13
输出：6          ← 13 在数组下标 6

输入：6
输出：-1         ← 6 不在数组中
二分前提是有序，乱序数组必须先排序。循环条件写 l <= r，更新要么 l = mid + 1 要么 r = mid - 1——中间那个数已经比较过，必须跳过，否则会死循环。

基础练习：用枚举输出 1000 以内的所有完全数（等于自身约数之和，如 6=1+2+3）。

挑战练习：在有序数组中用二分查找目标值，找不到输出"不存在"；再想想：为什么二分每次必须把区间缩小至少一半？

↑ 目录第 7 章 搜索入门：DFS / BFS

本章目标：掌握深度优先（DFS）与广度优先（BFS）两种搜索框架，理解栈与队列在搜索中的作用。

7.1 DFS：一条路走到黑，再回头

DFS 的思想是"能走就往前走，走不通就退回来换一条"（回溯）。全排列是最经典的入门题——used[i] 标记用过没有，退回来时记得恢复标记：

permutation.cpp
#include <iostream>
using namespace std;

int n;
bool used[15];
int path[15];

void dfs(int step) {
    if (step > n) {               // 终止：凑齐一个排列
        for (int i = 1; i <= n; i++) cout << path[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) { // 尝试每个还没用的数
        if (!used[i]) {
            used[i] = true;
            path[step] = i;
            dfs(step + 1);        // 递归下一层
            used[i] = false;      // 回溯：恢复标记
        }
    }
}

int main() {
    cin >> n;
    dfs(1);
    return 0;
}
运行示例（n=3）
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
DFS 写起来有固定套路：终止条件 → 尝试所有选择 → 标记 → 递归 → 回溯。忘记"回溯恢复标记"是最高频 bug——那样后面的排列会被"已用过"误杀。

7.2 BFS：一圈一圈向外扩散

BFS 用队列，像水波一样一层层向外扩散，所以它求出的路径是最短步数。迷宫最短路是标准应用：

maze.cpp
#include <iostream>
#include <queue>
using namespace std;

struct P { int x, y, step; };

int main() {
    int n = 5, m = 5;
    int g[10][10] = {           // 1 是墙，0 是路
        {0,0,1,0,0},
        {1,0,1,0,0},
        {0,0,1,0,1},
        {0,1,0,0,0},
        {0,0,0,1,0}
    };
    bool vis[10][10] = {false};
    int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
    queue<P> q;
    q.push({0, 0, 0}); vis[0][0] = true;
    int ans = -1;
    while (!q.empty()) {
        P cur = q.front(); q.pop();
        if (cur.x == n - 1 && cur.y == m - 1) { ans = cur.step; break; }
        for (int k = 0; k < 4; k++) {
            int nx = cur.x + dx[k], ny = cur.y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 出界
            if (g[nx][ny] == 1 || vis[nx][ny]) continue;          // 墙/走过
            vis[nx][ny] = true;
            q.push({nx, ny, cur.step + 1});
        }
    }
    cout << "最短步数=" << ans << endl;
    return 0;
}
运行结果
最短步数=12
BFS 必须在入队时就标记 visited，而不是出队时才标记——否则同一个格子会被反复入队，又慢又错。方向数组 dx/dy 各 4 个方向，出界判断要写全。

基础练习：输出 1~n 的全排列；再用 DFS 求一个简单迷宫是否存在通路。

挑战练习：用 BFS 求迷宫最短步数，并输出最短路径本身。提示：记录每个格子的"前一步从哪来"，到达终点后从终点倒着回溯。

↑ 目录第 8 章 综合测评与竞赛适应

本章目标：完成一次限时小比赛，掌握读题、估复杂度、命名规范、文件读写与时间分配，完成从"学知识"到"考成绩"的转化。

本章是结课章，以限时测评代替常规的基础/挑战练习——把前 7 章的知识放进真实赛场检验，比零散刷题更能检验学习效果。

8.1 文件输入输出 freopen

官方竞赛要求从文件读入、写到文件，而不是从键盘输入、屏幕输出。只用一行把"标准输入输出"重定向到文件：

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

int main() {
    freopen("test.in", "r", stdin);    // 读入文件
    freopen("test.out", "w", stdout);  // 输出文件
    int a, b;
    cin >> a >> b;                     // 实际从 test.in 读
    cout << a + b << endl;             // 实际写到 test.out
    return 0;
}
文件名的输入输出名必须和题目要求完全一致，大小写都不能错，否则直接 0 分。交卷前务必检查这两行、并在本地用样例数据实际测一遍。

8.2 比赛规范与策略

从本章开始按竞赛规范写代码：

  • 禁止调试输出：system("pause")、打印调试信息在判题环境里会干扰结果，一律不写。
  • 读题顺序：先读全卷，从简单题做起；每题先估数据范围与复杂度，再动手。
  • 样例优先：写完先跑题目的样例，对不上就先修再提交。
  • 时间分配：留出最后 15 分钟检查文件名、样例、边界（0、1、最大值）。
竞赛比的不是"会不会"，而是"稳定的会"。平时作业按比赛标准做：限时、独立、先估复杂度、写完测边界，考试才不会慌。

结课测评：2 小时限时赛，题目覆盖 8 章知识点，作为进入 CSP 冲刺班的依据。赛后逐题讲解并要求重写错题，把坑填平。

学制安排

schedule.sh
班型      小班教学（8~12 人）
周期      32 次课 / 两学期
频次      每周 1 次
时长      每次 120 分钟
配套      在线题库 + 每周周赛 + 月度测评

课程特色

  • 题量保底：课后配套分级题库，每天 1~2 道，通过率即真实进度。
  • 周赛机制：每周一次小比赛，提前适应竞赛节奏，暴露薄弱点。
  • 错题复盘：每次测评后逐题讲解，要求学生重写错题，把坑填平。
  • 竞赛衔接：结课即可无缝衔接《CSP-J/S 认证冲刺》课程。
试读体验：课程核心内容可先看 C++ 入门导读 与 枚举算法导读，感受教学风格。

常见问题

  • 零基础能直接学吗？ 建议先通过 Python 入门或入学测评，语言基础直接影响进度。
  • 会不会影响数学课？ 算法与数学紧密相关，绝大多数学生数学成绩反而提升。
  • 每周需要多少练习时间？ 建议课后每周 2~3 小时做题，练习发送到邮箱 lackychen@foxmail.com，老师逐题批改，比突击更有效。
  • 代码写错了不会改怎么办？ 课堂会教"读报错三步法"：看报错定位到哪一行 → 看那行的语法与变量名 → 往上多读一行找漏掉的括号或分号。
./apply --cpp 查看 CSP 冲刺课程 →

$ cat ~/learning-path.txt

图形化启蒙→Python→C++→CSP-J/S→NOIP·一对一规划（任意阶段可叠加）