C++ 竞赛编程：USACO 学习指南

🌐 English Version | 📖 当前：中文版

本书是专为参加 USACO（美国计算机奥林匹克竞赛） 的同学编写的 C++ 竞赛编程完整指南，覆盖从 Bronze 到 Platinum 级别所需的核心知识。也可用于 NOIP/CSP 等国内竞赛的算法学习。

📚 本书结构

每章页首徽章标注对应级别：🥉 Bronze / 🥈 Silver / 🥇 Gold / 💎 Platinum，可据此按需选读。

🗺️ USACO 分级学习路线

USACO 分为 Bronze → Silver → Gold → Platinum 四级逐级晋升，赛制详见理解 USACO。各级别对号入座：

🥉 Bronze — 语言基础与暴力思维

🥈 Silver — 图论与 DP 入门

🥇 Gold — 本书核心进阶内容

💎 Platinum — 高阶专题

🔗 Gold 依赖链

Gold 各章环环相扣，按依赖关系学习事半功倍：

5.6 并查集 ──→ 5.9 MST ──→ 5.14 网络流（割与连通性思想）
                  │
5.1 树的表示 ──→ 5.13 欧拉序/LCA ──→ 5.12 树链剖分
                  │                    │
                  └──→ 5.15 树上差分与点分治
5.2 BFS/DFS ──→ 5.10 拓扑排序 ──→ 5.11 SCC（缩点后回到 DAG）
5.4 最短路（Dijkstra）──→ 6.8 树形 DP（树上路径计数/换根）

🚀 如何使用本书

1. 入门学习者 — 从 C++ 基础 开始，按目录顺序学习
2. 有一定基础 — 直接进入核心数据结构或按上方路线表对号入座
3. 赛前冲刺 — 用附录速查手册和算法模板库快速复习

💡 学习建议

• 每章都有配套练习题（🟢 简单 / 🟡 中等 / 🔴 困难 / 🏆 挑战），先尝试自己解答再参考题解
• 代码示例均为 C++17，注意竞赛中常见的 I/O 优化写法
• 卡住时用调试指南的对拍流程验证思路

📝 翻译说明：本书中文版正在持续完善中。如遇内容缺失，可参考 英文原版。

第二部分：C++ 基础

在解决算法题之前，你需要先学会「说这门语言」。第二部分是 C++ 速成课——从第一个程序开始，涵盖函数、数组和向量。你将建立起后续所有章节所需的基础技能。

你将学到什么

为什么选择 C++？

竞赛选手绝大多数选择 C++，原因有两点：

1. 速度 —— C++ 程序比 Python 或 Java 运行更快，而在时间限制严格（通常 10^8 次操作只有 1-2 秒）时，速度至关重要
2. STL —— C++ 标准模板库提供了几乎所有你可能用到的数据结构和算法的现成实现

注意： USACO 接受 C++、Java 和 Python。但在顶级选手中 C++ 是最主流的选择，本书专注于 C++。

第二部分学习建议

• 亲手敲代码。 不要复制粘贴。你的手需要熟悉语法。
• 主动制造错误。 故意引入错误，看看会发生什么。读懂编译器报错本身也是一项技能。
• 运行每一个示例。 亲眼看到输出出现在屏幕上，远比仅仅阅读更能加深理解。

出发！

第 2.1 章：你的第一个 C++ 程序

2.1.0 从一道题出发：让电脑替你算数

全书从一道最简单的「题」开始——它朴素，但结构和你将来在 USACO 里遇到的每一道题一模一样：

🐄 题目：两头奶牛的牛奶 农夫 John 有两头奶牛：Bessie 今天产 a 升奶，Elsie 产 b 升。 输入：一行两个整数 a 和 b（读入后才知道具体数值）。 输出：它们今天一共产了多少升奶？

输入：7 5
输出：12

这道题为什么值得作为起点？

注意它和你平时「算数」的区别：

1. 写代码时你还不知道 a 和 b 是多少——程序要先「读入」数据，再计算，再「输出」结果。这就是所有竞赛题的固定三段式：读入 → 处理 → 输出。
2. 电脑需要被告知每一件小事：在哪里存 a 和 b？整数和小数有什么区别？结果怎么打印到屏幕上？
3. 你的代码还必须能被机器执行——需要把它编译成可运行程序，这需要搭建环境。

所以本章的路线自然是你上面看到的目标清单：搭好环境 → 写出第一行代码 → 逐行理解 → 学会变量与输入输出 → 最终独立解出上面这道奶牛题。

欢迎！完成本章后，你将：

• 搭建好可用的 C++ 开发环境（用在线编译器只需 5 分钟）
• 编写、编译并运行第一个 C++ 程序
• 理解代码中每一行的含义
• 学会变量、数据类型和输入输出
• 完成 13 道练习题并查看完整题解

2.1.0b 搭建开发环境

写代码之前，你需要一个可以编写和运行代码的地方。有两种选择：在线编译器（推荐新手使用——无需安装）和本地开发环境（可选，适合离线工作）。

选项 A：在线编译器（推荐——从这里开始！）

只需一个浏览器，打开以下任意网站：

使用 Ideone（新手最简单）：

1. 打开 ideone.com
2. 在语言下拉框选择 "C++17 (gcc 8.4)"
3. 将代码粘贴到文本区
4. 点击绿色 "Run" 按钮
5. 在底部面板查看输出

就这么简单！无需安装，无需配置。

选项 B：使用 CLion（推荐本地 IDE）

如果你想在自己的电脑上离线编写和运行 C++ 代码，强烈推荐 CLion ——JetBrains 出品的专业 C/C++ IDE。它拥有智能代码补全、一键编译运行和内置调试器，能大幅提升你的效率。

💡 学生免费！ CLion 是付费软件，但 JetBrains 为学生提供免费教育许可。用你的 .edu 邮箱在 JetBrains 学生许可页面 申请即可。

安装步骤：

第一步：安装 C++ 编译器（CLion 需要外部编译器）

第二步：安装 CLion

1. 前往 CLion 下载页面 下载对应系统的安装包
2. 运行安装包并按提示完成安装（保持默认选项即可）
3. 首次启动时选择**「激活」**→ 用 JetBrains 学生账号登录，或开始 30 天免费试用

第三步：创建第一个项目

1. 打开 CLion，点击 "New Project"
2. 选择 "C++ Executable"，将语言标准设为C++17
3. 点击 "Create"——CLion 会自动生成包含 main.cpp 的项目
4. 在 main.cpp 中编写代码，点击右上角绿色**▶ Run** 按钮即可编译运行
5. 输出会出现在底部的"Run" 面板中

🔧 CLion 自动检测编译器： 首次启动时，CLion 会自动扫描已安装的编译器（GCC / Clang / MSVC）。如果检测成功，你会在 "Settings → Build → Toolchains" 中看到绿色对勾 ✅。若未检测到，请确认第一步的编译器已正确安装并添加到 PATH。

CLion 竞赛编程实用功能：

• 内置终端：底部的 Terminal 标签可以直接输入测试数据
• 调试器：设置断点、逐行执行代码、查看变量值——追踪 bug 的必备工具
• 代码格式化：Ctrl + Alt + L（Mac：Cmd + Option + L）自动整理代码缩进

如何编译和运行（本地）

安装好 g++ 后，编译和运行方法如下：

g++ -o hello hello.cpp -std=c++17

逐字分解这条命令：

运行方法：

./hello        # Linux/Mac：./ 表示「在当前目录」
hello.exe      # Windows（.exe 会自动添加）

🤔 为什么是 ./hello 而不是直接 hello？ 在 Linux/Mac 上，系统默认不会从当前目录运行程序（出于安全考虑）。./ 明确告诉系统「在当前目录找这个程序」。

2.1.1 Hello, World!

每段编程之旅都从同一个地方开始。下面是最简单的完整 C++ 程序：

#include <iostream>    // 告诉编译器我们要使用输入/输出功能

int main() {           // 每个 C++ 程序都从 main() 开始执行
    std::cout << "Hello, World!" << std::endl;  // 打印到屏幕
    return 0;          // 0 = 成功，程序正常结束
}

运行后你应该看到：

Hello, World!

每一行的含义：

第 1 行：#include <iostream> 这是一条预处理指令——在正式编译之前执行的指令。它的意思是「把 iostream 库的内容复制粘贴到我的程序中」。iostream 库提供了 cin（读取输入）和 cout（打印输出）。没有这行，你的程序就无法输出任何内容。

可以这样理解：做饭之前，你需要先把食材拿进厨房。

第 3 行：int main() 这声明了 main 函数——每个 C++ 程序的起点。运行一个 C++ 程序时，计算机总是从 main() 内部的第一行开始执行。int 表示这个函数返回一个整数（退出码）。每个 C++ 程序必须有且仅有一个 main。

第 4 行：std::cout << "Hello, World!" << std::endl; 这行打印文字。拆解来看：

• std::cout —— 「控制台输出」流（可以理解为屏幕）
• << —— 「放入」运算符；将数据送入流
• "Hello, World!" —— 要打印的文字（引号本身不会被打印）
• << std::endl —— 添加换行（相当于按回车）
• ; —— C++ 中每条语句都以分号结束

第 5 行：return 0; 退出 main 并告诉操作系统程序成功结束。（非零返回值表示发生了错误。）

编译流程

图示：编译流程

上图展示了从源代码到可执行文件的三个阶段：你的 .cpp 文件输入给 g++ 编译器，最终生成可运行的二进制文件。理解这个流程有助于在编译错误发生前就预防它们。

2.1.2 竞赛选手的标准模板

解 USACO 题目时，你会用到一套标准模板。下面是完整带注释的版本：

#include <bits/stdc++.h>      // 「全包含」——一次性包含所有标准库
using namespace std;           // 让我们可以写 cout 而不是 std::cout

int main() {
    ios_base::sync_with_stdio(false);  // 禁用 C 和 C++ I/O 的同步（更快）
    cin.tie(NULL);                      // 解除 cin 和 cout 的绑定（输入更快）

    // 你的解题代码写在这里

    return 0;
}

为什么用 #include <bits/stdc++.h>？

这是 GCC 专有的头文件，一次性包含所有标准库。不用再写：

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
// ... 还有 20 多行

一行搞定。在竞赛编程中，这是普遍做法，能节省时间。

注意： bits/stdc++.h 只在 GCC 编译器（USACO 评测机使用的编译器）下有效。竞赛编程中完全没问题，但不要在生产软件中使用。

为什么用 using namespace std;？

标准库把所有内容放在名为 std 的命名空间中。没有这行，你需要到处写 std::cout、std::vector、std::sort。有了 using namespace std;，直接写 cout、vector、sort——简洁得多。

I/O 加速行

ios_base::sync_with_stdio(false);
cin.tie(NULL);

这两行让 cin 和 cout 快得多。没有它们，读取大量输入可能慢 10 倍，即使算法正确也可能导致「超时（TLE）」。每次都要加上它们。

🐛 常见错误： 加了这两行后，不要混用 cin/cout 和 scanf/printf。选一种风格坚持用。

2.1.3 变量与数据类型

变量是内存中一个有名字的存储位置。C++ 中每个变量都有一个类型——类型告诉计算机需要分配多少内存，以及里面会存什么数据。

🧠 思维模型：变量就像带标签的盒子

当你写：   int score = 100;

计算机做了三件事：
  1. 创建一个足以容纳整数的盒子（4 字节）
  2. 在盒子上贴上标签 "score"
  3. 把数字 100 放进盒子

竞赛编程必备类型

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

int main() {
    // int：整数，范围：-2,147,483,648 到 +2,147,483,647（约 ±20 亿）
    int apples = 42;
    int temperature = -5;

    // long long：大整数，范围：约 ±9.2 × 10^18
    long long population = 7800000000LL;  // LL 后缀表示「这是 long long 字面量」
    long long trillion = 1000000000000LL;

    // double：小数/分数
    double pi = 3.14159265358979;
    double percentage = 99.5;

    // bool：只有 true 或 false
    bool isRaining = true;
    bool finished = false;

    // char：单个字符（以 0-255 的数字存储）
    char grade = 'A';     // 单引号表示字符
    char newline = '\n';  // 特殊字符：换行符

    // string：字符序列
    string name = "Alice";         // 双引号表示字符串
    string greeting = "Hello!";

    // 打印所有变量：
    cout << "苹果数量: " << apples << "\n";
    cout << "人口: " << population << "\n";
    cout << "圆周率: " << pi << "\n";
    cout << "在下雨: " << isRaining << "\n";  // true 打印 1，false 打印 0
    cout << "成绩: " << grade << "\n";
    cout << "姓名: " << name << "\n";

    return 0;
}

图示：C++ 数据类型参考

如何选择正确的类型

变量命名规则

C++ 对变量名有严格规定。掌握这些规则很关键——命名不当会导致 bug，非法名字则无法编译。

形式规则（编译器强制执行）

✅ 合法名称必须：

• 以字母（a-z、A-Z）或下划线 _ 开头
• 只包含字母、数字（0-9）和下划线
• 不能是 C++ 保留关键字

❌ 以下名称无法编译：

⚠️ 区分大小写！ score、Score 和 SCORE 是三个完全不同的变量。这是常见 bug 来源——命名时保持一致。

常见命名风格

C++ 中有几种广泛使用的命名规范。竞赛编程中不必只选一种，但了解它们有助于读懂别人的代码：

竞赛编程中最常用驼峰式和单字母名称。公司的生产代码中，根据风格指南通常用 snake_case 或 camelCase。

命名最佳实践

1. 有描述性——从名字就能看出用途：

// ✅ 好——一眼就知道每个变量存什么
int numCows = 5;
long long totalMilk = 0;
string cowName = "Bessie";
int maxScore = 100;

// ❌ 差——语法正确但令人困惑
int x = 5;            // x 是什么？计数？下标？值？
long long t = 0;      // t 是什么？时间？总计？临时变量？
string n = "Bessie";  // n 通常表示「数字」——用来存名字很误导！

2. 只在含义显而易见时使用单字母名称：

// ✅ 可接受——这些是公认的惯例
for (int i = 0; i < n; i++) { ... }    // i、j、k 用于循环下标
int n, m;                                // n = 计数，m = 第二维
cin >> n >> m;                           // 竞赛编程中人人都这样写

// ❌ 令人困惑——单字母但没有明确惯例
int q = 5;   // q 是计数？查询数？系数？
char z = 'A'; // 为什么用 z？

3. 常量用全大写，方便识别：

const int MAX_N = 200005;        // 数组最大长度
const int MOD = 1000000007;      // 取模常量
const long long INF = 1e18;      // 用于比较的「无穷大」
const double PI = 3.14159265359; // 数学常数

4. 避免外形相似的名称：

// ❌ 容易混淆
int total1 = 10;
int totall = 20;  // 这是「total-L」还是手误的「total-1」？

int O = 0;        // 字母 O 看起来像数字 0
int l = 1;        // 小写 L 看起来像数字 1

// ✅ 更好的替代
int totalA = 10;
int totalB = 20;

5. 不要用下划线加大写字母开头：

// ❌ 能编译，但被 C++ 标准保留
int _Score = 100;   // _X 形式的名称被编译器/库保留
int __value = 42;   // 双下划线开头始终保留

// ✅ 安全替代
int score = 100;
int myValue = 42;

竞赛编程 vs 生产代码的命名对比

💡 本书中： 我们会混用两种风格——讲解时用描述性名称保持清晰，解题时用简短名称。关键原则：看到变量名就应该立刻知道它存的是什么。

深入了解：char、string 与字符-整数转换

我们已经简要介绍了 char 和 string。由于许多 USACO 题目涉及字符处理、数字提取和字符串操作，让我们深入看看这两种重要类型。

char 与 ASCII——每个字符都是一个数字

C++ 中的 char 以 1 字节整数（0-255）存储。每个字符按照 ASCII 表（美国信息交换标准代码）映射到一个数字。不需要背整张表，但记住几个关键范围非常有用：

关键关系：
• 'a' - 'A' = 32     （大小写字母差值）
• '0' 的 ASCII 值是 48（不是 0！）
• 数字、大写字母、小写字母各自在连续范围内

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

int main() {
    char ch = 'A';

    // char 本质上是整数——可以打印其数值
    cout << ch << "\n";        // 打印：A（字符形式）
    cout << (int)ch << "\n";   // 打印：65（ASCII 值）

    // 可以对 char 做算术！
    char next = ch + 1;       // 'A' + 1 = 66 = 'B'
    cout << next << "\n";     // 打印：B

    // 比较 char（比较 ASCII 值）
    cout << ('a' < 'z') << "\n";   // 1（真，因为 97 < 122）
    cout << ('A' < 'a') << "\n";   // 1（真，因为 65 < 97）

    return 0;
}

char ↔ int 转换——最常用的技巧

竞赛编程中，你需要频繁地在字符数字和整数值之间转换。以下是完整指南：

1. 数字字符 → 整数值（例如 '7' → 7）

char ch = '7';
int digit = ch - '0';    // '7' - '0' = 55 - 48 = 7
cout << digit << "\n";   // 打印：7

// 这行得通是因为数字字符 '0'~'9' 的 ASCII 值是连续的：
// '0'=48, '1'=49, ..., '9'=57
// 所以 ch - '0' 正好是实际数值（0~9）

2. 整数值 → 数字字符（例如 7 → '7'）

int digit = 7;
char ch = '0' + digit;   // 48 + 7 = 55 = '7'
cout << ch << "\n";      // 打印：7（字符 '7'）

// 仅对数字 0~9 有效

3. 大小写互转

char upper = 'C';
char lower = upper + 32;           // 'C'(67) + 32 = 'c'(99)
cout << lower << "\n";            // 打印：c

// 更易读的写法：
char lower2 = upper - 'A' + 'a';  // 'C'-'A' = 2，'a'+2 = 'c'
cout << lower2 << "\n";           // 打印：c

// 反向：小写 → 大写
char ch = 'f';
char upper2 = ch - 'a' + 'A';    // 'f'-'a' = 5，'A'+5 = 'F'
cout << upper2 << "\n";           // 打印：F

// 使用内置函数（更推荐，可读性更好）：
cout << (char)toupper('g') << "\n";  // 打印：G
cout << (char)tolower('G') << "\n";  // 打印：g

4. 判断字符类型（USACO 中非常实用）

char ch = '5';

// 判断是否为数字
if (ch >= '0' && ch <= '9') {
    cout << "是数字！\n";
}

// 判断是否为大写字母
if (ch >= 'A' && ch <= 'Z') {
    cout << "大写字母！\n";
}

// 判断是否为小写字母
if (ch >= 'a' && ch <= 'z') {
    cout << "小写字母！\n";
}

// 或使用内置函数：
// isdigit(ch), isupper(ch), islower(ch), isalpha(ch), isalnum(ch)
if (isdigit(ch)) cout << "数字！\n";
if (isalpha(ch)) cout << "字母！\n";

5. 经典模式：从字符串中提取数字

string s = "abc123def";
int sum = 0;
for (char ch : s) {
    if (ch >= '0' && ch <= '9') {
        sum += ch - '0';  // 将数字字符转为整数并累加
    }
}
cout << "各位数字之和：" << sum << "\n";  // 1+2+3 = 6

string 详细指南

string 是 C++ 的内置文本类型。与单个 char 不同，string 存储一串字符，并提供许多实用操作。

基本操作：

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

int main() {
    // 创建字符串
    string s1 = "Hello";
    string s2 = "World";
    string empty = "";           // 空字符串
    string repeated(5, 'x');     // "xxxxx"——5 个 'x'

    // 长度
    cout << s1.size() << "\n";   // 5（等同于 s1.length()）

    // 拼接
    string s3 = s1 + " " + s2;  // "Hello World"
    s1 += "!";                   // s1 变为 "Hello!"

    // 访问单个字符（从 0 开始，与数组相同）
    cout << s3[0] << "\n";      // 'H'
    cout << s3[6] << "\n";      // 'W'

    // 修改单个字符
    s3[0] = 'h';                // "hello World"

    // 比较（字典序）
    cout << ("apple" < "banana") << "\n";   // 1（真）
    cout << ("abc" == "abc") << "\n";       // 1（真）
    cout << ("abc" < "abd") << "\n";        // 1（真，逐字符比较）

    return 0;
}

遍历字符串：

string s = "USACO";

// 方法一：下标循环
for (int i = 0; i < (int)s.size(); i++) {
    cout << s[i] << " ";  // U S A C O
}
cout << "\n";

// 方法二：范围 for 循环（更简洁）
for (char ch : s) {
    cout << ch << " ";    // U S A C O
}
cout << "\n";

// 方法三：引用范围 for（可就地修改）
for (char& ch : s) {
    ch = tolower(ch);     // 将每个字符转为小写
}
cout << s << "\n";        // "usaco"

常用 string 函数：

string s = "Hello, World!";

// 子串：s.substr(起始位置, 长度)
string sub = s.substr(7, 5);     // "World"（从第 7 个字符开始取 5 个）
string sub2 = s.substr(7);       // "World!"（从第 7 个到结尾）

// 查找：s.find("文本")——返回下标，找不到返回 string::npos
size_t pos = s.find("World");    // 7（注意类型是 size_t，不是 int！）
if (s.find("xyz") == string::npos) {
    cout << "未找到！\n";
}

// 追加
s.append(" Hi");                 // "Hello, World! Hi"
// 等价于：s += " Hi";

// 插入
s.insert(5, "!!");               // "Hello!!, World! Hi"

// 删除：s.erase(起始位置, 个数)
s.erase(5, 2);                   // 从第 5 位删除 2 个字符

// 替换：s.replace(起始位置, 个数, "新文本")
string msg = "I love cats";
msg.replace(7, 4, "dogs");       // "I love dogs"

从输入读取字符串：

// cin >> 读取一个单词（遇到空白字符停止）
string word;
cin >> word;    // 输入 "Hello World" → word = "Hello"

// getline 读取整行（包含空格）
string line;
getline(cin, line);   // 输入 "Hello World" → line = "Hello World"

// ⚠️ 注意：cin >> 之后，调用 getline 前先 cin.ignore()！
int n;
cin >> n;
cin.ignore();          // 消耗残留的 '\n'
string fullLine;
getline(cin, fullLine); // 现在可以正确读取

string 与数字互转：

// 字符串 → 整数
string numStr = "42";
int num = stoi(numStr);         // stoi = "string to int" → 42
long long big = stoll("123456789012345"); // stoll = "string to long long"

// 字符串 → 浮点数
double d = stod("3.14");       // stod = "string to double" → 3.14

// 整数 → 字符串
int x = 255;
string s = to_string(x);       // "255"
string s2 = to_string(3.14);   // "3.140000"

char 数组（C 风格字符串）——了解即可

在 C（以及旧式 C++ 代码）中，字符串以以 '\0' 结尾的 char 数组存储。竞赛编程中你很少需要用到它（改用 string），但应该能认出它：

// C 风格字符串（char 数组）
char greeting[] = "Hello";  // 实际存储：H e l l o \0（共 6 个字符！）
// '\0'（空字符）标记字符串结束

// 警告：必须确保数组足够大以容纳字符串 + '\0'
char name[20];              // 最多可存 19 个字符 + '\0'

// char 数组与 string 互转
string s = greeting;        // char 数组 → string（自动转换）
// string → char 数组：使用 s.c_str() 获得 const char*

为什么竞赛编程中 string 比 char[] 更好：

⚡ USACO 专业技巧： 除非题目明确要求 char 数组，否则始终用 string。字符串操作更简洁、更安全、更易调试。char 数组在竞赛编程中唯一常见的使用场景是用 scanf/printf 读取超大输入以提速——但加上 sync_with_stdio(false) 后，string + cin/cout 对 99% 的 USACO 题目已经足够快。

快速参考：字符/字符串速查表

⚠️ 整数溢出——竞赛编程中的头号 Bug

当一个数超过它所属类型的范围时会发生什么？

// 把 int 想象成一个从 -2,147,483,648 到 2,147,483,647 的表盘
// 当你超过最大值，它会回绕到最小值！

int x = 2147483647;  // int 的最大值
cout << x << "\n";   // 打印：2147483647
x++;                 // 加 1……会发生什么？
cout << x << "\n";   // 打印：-2147483648（溢出！回绕了！）

这就像老式汽车里程表到了 999999 又回到 000000。

如何避免溢出：

int a = 1000000000;    // 10 亿——int 能放下
int b = 1000000000;    // 10 亿——int 能放下
// int wrong = a * b;  // 溢出！a*b = 10^18，int 放不下

long long correct = (long long)a * b;  // 乘之前把其中一个转成 long long
cout << correct << "\n";  // 1000000000000000000 ✓

// 经验法则：如果 N 最大为 10^9，你又需要将两个这样的值相乘，就用 long long

⚡ 专业技巧： 拿不准时，用 long long。它比 int 稍慢，但能防止难以发现的溢出 bug。

2.1.4 用 cin 和 cout 进行输入输出

用 cout 打印输出

int score = 95;
string name = "Alice";

cout << "分数：" << score << "\n";          // 分数：95
cout << name << " 得了 " << score << "\n"; // Alice 得了 95

// "\n" vs endl
cout << "第一行" << "\n";   // 快——只是一个换行符
cout << "第二行" << endl;   // 慢——清空缓冲区并换行

⚡ 专业技巧： 始终用 "\n" 而不是 endl。endl 会清空输出缓冲区，比 "\n" 慢得多。对于输出量大的题目，使用 endl 可能导致超时！

用 cin 读取输入

int n;
cin >> n;    // 从输入读取一个整数

string s;
cin >> s;    // 读取一个单词（遇到空白字符停止——空格、制表符、换行）

double x;
cin >> x;    // 读取一个小数

cin >> 会自动跳过空白字符。这意味着空格、制表符和换行都被同等对待。因此以下两种输入格式的处理方式完全相同：

输入格式一（同一行）：  42 hello 3.14
输入格式二（分多行）：
42
hello
3.14

两种都用以下代码处理：

int a; string b; double c;
cin >> a >> b >> c;  // 无论格式如何都能读取这三个值

读取多个值——最常见的 USACO 模式

USACO 题目几乎都以「读取 N，然后读取 N 个值」开头。方法如下：

典型 USACO 输入：
5          ← 第一行：N（元素个数）
10 20 30 40 50   ← 后续行：N 个值

int n;
cin >> n;              // 读取 N

for (int i = 0; i < n; i++) {
    int x;
    cin >> x;          // 读取每个元素
    cout << x * 2 << "\n";  // 处理它
}

复杂度分析：

• 时间：O(N)——读取 N 个数，每个 O(1) 处理
• 空间：O(1)——只有一个变量 x，不存储所有数据

对于输入 5\n10 20 30 40 50，会打印：

20
40
60
80
100

读取完整的一行（包含空格）

有时输入的一行包含多个单词。cin >> 每次只读一个单词，所以要用 getline：

string fullName;
getline(cin, fullName);  // 读取整行，包括空格
cout << "姓名：" << fullName << "\n";

🐛 常见 Bug： 混用 cin >> 和 getline 会出问题。cin >> n 之后，缓冲区里还残留一个 \n。这时调用 getline 会读到那个空行而不是下一行。修复方法：在 cin >> 之后、getline 之前调用 cin.ignore()。

控制小数输出精度

double y = 3.14159;

cout << y << "\n";                            // 3.14159（默认）
cout << fixed << setprecision(2) << y << "\n"; // 3.14（恰好 2 位小数）
cout << fixed << setprecision(6) << y << "\n"; // 3.141590（6 位小数）

2.1.5 基本算术

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

int main() {
    int a = 17, b = 5;

    cout << a + b << "\n";   // 22  （加法）
    cout << a - b << "\n";   // 12  （减法）
    cout << a * b << "\n";   // 85  （乘法）
    cout << a / b << "\n";   // 3   （整数除法——截断向零！）
    cout << a % b << "\n";   // 2   （取模——整除后的余数）

    // 整数除法示例：
    // 17 ÷ 5 = 3 余 2
    // 因此：17 / 5 = 3，17 % 5 = 2

    double x = 17.0, y = 5.0;
    cout << x / y << "\n";   // 3.4（操作数是 double 时进行实数除法）

    // 复合赋值运算符：
    int n = 10;
    n += 5;    // 等同于：n = n + 5   → n 现在是 15
    n -= 3;    // 等同于：n = n - 3   → n 现在是 12
    n *= 2;    // 等同于：n = n * 2   → n 现在是 24
    n /= 4;    // 等同于：n = n / 4   → n 现在是 6
    n++;       // 等同于：n = n + 1   → n 现在是 7
    n--;       // 等同于：n = n - 1   → n 现在是 6

    cout << n << "\n";  // 6

    return 0;
}

🤔 为什么整数除法会截断？

当两个操作数都是整数时，C++ 执行整数除法——直接丢弃小数部分。17 / 5 得 3，不是 3.4。这是有意为之，而且非常有用（例如：找出某个东西属于哪个「组」）。

// 200 分钟等于几小时？
int minutes = 200;
int hours = minutes / 60;     // 200 / 60 = 3（不是 3.33…）
int remaining = minutes % 60; // 200 % 60 = 20
cout << hours << " 小时 " << remaining << " 分钟\n";  // 3 小时 20 分钟

// 要得到小数结果，至少一个操作数必须是 double：
int a = 7, b = 2;
cout << a / b << "\n";           // 3    （整数除法）
cout << (double)a / b << "\n";   // 3.5  （先把 a 转成 double）
cout << a / (double)b << "\n";   // 3.5  （先把 b 转成 double）
cout << 7.0 / 2 << "\n";        // 3.5  （字面量 7.0 是 double）

2.1.6 你的第一个 USACO 风格程序

让我们把所有内容综合起来，写一个读取输入、产生输出的完整程序——就像真正的 USACO 题目。

题目： 读取两个整数 N 和 M，打印它们的和、差、积、整数商和余数。

分析思路：

1. 需要两个变量存储 N 和 M
2. 用 cin 读取
3. 用 cout 打印每个结果
4. N 和 M 可能很大，应该用 long long 吗？安全起见用它。

💡 新手解题流程：

遇到题目时，别急着写代码。先用自然语言想清楚步骤：

1. 理解题目：输入是什么？输出是什么？约束是什么？
2. 手动推演样例：用样例输入，手算出输出，确认自己理解了题目
3. 考虑数据范围：N 和 M 最大多少？会不会溢出？
4. 写伪代码：读取 → 计算 → 输出
5. 翻译成 C++：将伪代码逐行转化为真实代码

本题：读取两个数 → 执行五种运算 → 输出五个结果。非常直接！

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, m;
    cin >> n >> m;  // 在同一行读取两个数

    cout << n + m << "\n";  // 和
    cout << n - m << "\n";  // 差
    cout << n * m << "\n";  // 积
    cout << n / m << "\n";  // 整数商
    cout << n % m << "\n";  // 余数

    return 0;
}

复杂度分析：

• 时间：O(1)——只有固定次数的算术运算
• 空间：O(1)——只有两个变量

样例输入：

17 5

样例输出：

22
12
85
3
2

⚠️ 第 2.1 章常见错误

本章总结

📌 核心要点

❓ 常见问题

Q1：bits/stdc++.h 会拖慢编译速度吗？

A：是的，编译时间可能增加 1-2 秒。但竞赛中编译时间不计入时限，不影响结果。生产项目中不要用它。

Q2：默认用 int 还是 long long？

A：经验法则——拿不准就用 long long。它比 int 稍慢（在现代 CPU 上几乎感受不到），但能防止溢出。特别注意：两个 int 相乘，结果可能需要 long long。

Q3：USACO 里不能用 scanf/printf 吗？

A：可以用！但加了 sync_with_stdio(false) 后，不能混用 cin/cout 和 scanf/printf。建议新手坚持用 cin/cout，更安全。

Q4：可以省略 return 0; 吗？

A：C++11 及以后，main() 执行到末尾时编译器自动返回 0，技术上可以省略。但写上更清晰。

Q5：代码本地运行正确，USACO 评测却 Wrong Answer，怎么回事？

A：最常见的三个原因：① 整数溢出（本该用 long long 却用了 int）；② 没处理所有边界情况；③ 输出格式错误（多了或少了空格/换行）。

🔗 与后续章节的联系

• 第 2.2 章（控制流）在本章基础上新增 if/else 条件和 for/while 循环，让你能处理「重复 N 次」的任务
• 第 2.3 章（函数与数组）介绍函数（将代码组织成可复用的块）和数组（存储一组数据）——USACO 解题的核心工具
• 第 3.1 章（STL 核心用法）介绍 vector 和 sort 等 STL 工具，大大简化本章手写的逻辑
• 本章学到的整数溢出预防技巧会贯穿全书，特别在第 3.2 章（前缀和）和第 6.1-6.3 章（DP）中反复用到

练习题

按顺序完成所有题目——难度逐渐递增。每题都有完整题解，尝试自己解决后再查看。

每道题只需新增 1-3 行代码，帮助你练习输入 C++ 代码和运行程序。

热身 2.1.1 — 个人问候 编写一个程序，精确打印以下内容（换成你自己的名字）：

Hello, Alice!
My favorite number is 7.
I am learning C++.

（所有值可以硬编码——不需要读取输入。）

思路： 用 cout 打印三行。无需读取输入。

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

int main() {
    cout << "Hello, Alice!\n";
    cout << "My favorite number is 7.\n";
    cout << "I am learning C++.\n";
    return 0;
}

关键点：

• 每条 cout 语句以 ;\n" 结尾——\n 产生换行
• 也可以将多个 << 连在一条 cout 上
• 没有输入时不需要 cin

热身 2.1.2 — 五行数字 打印数字 1 到 5，每行一个。用恰好 5 条独立的 cout 语句（还没学循环——第 2.2 章会讲）。

思路： 五条独立的 cout 语句，每条打印一个数字。

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

int main() {
    cout << 1 << "\n";
    cout << 2 << "\n";
    cout << 3 << "\n";
    cout << 4 << "\n";
    cout << 5 << "\n";
    return 0;
}

关键点：

• cout << 1 << "\n" 打印数字 1 后跟换行
• 第 2.2 章会学用循环来做这件事——但手动写对小数量完全没问题

热身 2.1.3 — 翻倍 从输入读取一个整数，打印它的 2 倍。

样例输入： 7 样例输出： 14

思路： 读入变量，乘以 2，打印。

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

int main() {
    int n;
    cin >> n;
    cout << n * 2 << "\n";
    return 0;
}

关键点：

• cin >> n 读取一个整数存入 n
• 可以直接在 cout 里做算术：n * 2 先计算，再打印
• 若 n 可能很大（最大 10^9），用 long long n，因为 n * 2 可能溢出 int

热身 2.1.4 — 两数之和 读取同一行上的两个整数，打印它们的和。

样例输入： 15 27 样例输出： 42

思路： 读取两个整数，相加，打印。

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

int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b << "\n";
    return 0;
}

关键点：

• cin >> a >> b 在一条语句中读取两个值——无论它们在同一行还是不同行都有效
• 在同一行声明两个变量：int a, b; 等价于 int a; int b;

热身 2.1.5 — 打招呼 读取一个单词（名字，不含空格），打印 Hi, [name]!

样例输入： Bob 样例输出： Hi, Bob!

思路： 读取字符串，嵌入问候语中打印。

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

int main() {
    string name;
    cin >> name;
    cout << "Hi, " << name << "!\n";
    return 0;
}

关键点：

• string name; 声明一个存储文本的变量
• cin >> name 读取一个单词（遇到第一个空格停止）
• 注意 cout 的链式写法：字符串字面量 + 变量 + 字符串字面量

这些题需要综合运用输入、算术和输出。编码前先想清楚数学关系。

题目 2.1.6 — 年龄换算 读取一个人的整岁年龄，打印其大约的天数（按每年 365 天计算，不考虑闰年）。

样例输入： 15 样例输出： 5475

思路： 年龄乘以 365。由于年龄 × 365 不会超过 int 范围（最大约 150 岁 → 150×365 = 54750，远小于 int 上限），用 int 即可。

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

int main() {
    int years;
    cin >> years;
    cout << years * 365 << "\n";
    return 0;
}

关键点：

• years * 365 按整数计算——这里不存在溢出风险
• 如果还要换算成小时、分钟、秒，为安全起见改用 long long

题目 2.1.7 — 秒数转换 读取秒数 S（1 ≤ S ≤ 10^9），转换为小时、分钟和剩余秒数。

样例输入： 3661 样例输出：

1 hours
1 minutes
1 seconds

思路： 使用整数除法和取模。先除以 3600 得小时数，余数（mod 3600）再除以 60 得分钟数，最后剩余的是秒数。

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

int main() {
    long long s;
    cin >> s;

    long long hours = s / 3600;         // 每小时 3600 秒
    long long remaining = s % 3600;     // 去掉完整小时后剩余的秒数
    long long minutes = remaining / 60; // 每分钟 60 秒
    long long seconds = remaining % 60; // 去掉完整分钟后剩余的秒数

    cout << hours << " hours\n";
    cout << minutes << " minutes\n";
    cout << seconds << " seconds\n";

    return 0;
}

关键点：

• 用 long long 是因为 S 最大 10^9（int 也够，但 long long 是好习惯）
• 核心思路：s % 3600 得到去掉完整小时后的秒数，再除以 60 得分钟
• 验证：3661 → 3661/3600=1 小时，3661%3600=61，61/60=1 分钟，61%60=1 秒 ✓

题目 2.1.8 — 矩形 读取矩形的长 L 和宽 W，打印它的面积和周长。

样例输入： 6 4 样例输出：

Area: 24
Perimeter: 20

思路： 面积 = L × W，周长 = 2 × (L + W)。

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

int main() {
    long long L, W;
    cin >> L >> W;

    cout << "Area: " << L * W << "\n";
    cout << "Perimeter: " << 2 * (L + W) << "\n";

    return 0;
}

关键点：

• 运算顺序：2 * (L + W)——括号确保先加 L+W，再乘以 2
• 使用 long long 以防 L、W 较大（若 L、W 最大 10^9，L*W 最大 10^18）

题目 2.1.9 — 温度转换 读取摄氏温度，打印对应的华氏温度。公式：F = C × 9/5 + 32

样例输入： 100 样例输出： 212.00

思路： 套用公式。需要小数输出，用 double。陷阱：9/5 整数运算结果是 1，不是 1.8！

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

int main() {
    double celsius;
    cin >> celsius;

    double fahrenheit = celsius * 9.0 / 5.0 + 32.0;

    cout << fixed << setprecision(2) << fahrenheit << "\n";

    return 0;
}

关键点：

• 用 9.0 / 5.0（或 9.0/5）而不是 9/5——后者是整数除法，结果是 1 而不是 1.8！
• fixed << setprecision(2) 强制输出恰好 2 位小数
• 验证：100°C → 100 × 9.0/5.0 + 32 = 180 + 32 = 212 ✓

题目 2.1.10 — 硬币计数 读取四个整数：25 分硬币（quarters）、10 分硬币（dimes）、5 分硬币（nickels）和 1 分硬币（pennies）的数量，打印总面值（单位：分）。

样例输入：

3 2 1 4

（3 枚 25 分，2 枚 10 分，1 枚 5 分，4 枚 1 分）

样例输出： 104

思路： 每种硬币数量乘以面值，全部相加。

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

int main() {
    int quarters, dimes, nickels, pennies;
    cin >> quarters >> dimes >> nickels >> pennies;

    int total = quarters * 25 + dimes * 10 + nickels * 5 + pennies * 1;

    cout << total << "\n";

    return 0;
}

关键点：

• 每种硬币乘以面值：quarters=25，dimes=10，nickels=5，pennies=1
• 验证：3×25 + 2×10 + 1×5 + 4×1 = 75 + 20 + 5 + 4 = 104 ✓
• 若硬币数量很大，改用 long long

🏆 挑战题

这些题需要更多思考——特别是数据类型和解题方法。

挑战 2.1.11 — 溢出探测器 读取两个整数 A 和 B（各最大 10^9），用两种方式计算它们的乘积：int 类型和 long long 类型，各打印一次结果。观察溢出时的差异。

样例输入： 1000000000 3 样例输出：

int product: -1294967296
long long product: 3000000000

（int 结果因溢出而错误；long long 结果正确。）

思路： 以 long long 读入两个数，然后两种方式各算一次乘积——一次强转为 int，一次用 long long。直观展示溢出效果。

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

int main() {
    long long a, b;
    cin >> a >> b;

    // 先转成 int 再乘，强制触发整数溢出
    int int_product = (int)a * (int)b;

    // long long 乘法——值最大 10^9 时不会溢出
    long long ll_product = a * b;

    cout << "int product: " << int_product << "\n";
    cout << "long long product: " << ll_product << "\n";

    return 0;
}

关键点：

• (int)a * (int)b——两个操作数都转成 int 再乘，乘法在 int 范围内溢出
• a * b（a、b 是 long long）——乘法在 long long 空间内进行，不溢出
• 10^9 × 3 的实际结果是 3×10^9，但 int 最大约 2.147×10^9 < 3×10^9，溢出后得到 -1294967296
• 教训： 当任意一个值可能达到约 10^5 或更大时，乘法时始终用 long long

挑战 2.1.12 — USACO 风格大数相乘 给定两个整数 N 和 M（1 ≤ N, M ≤ 10^9），打印它们的乘积。（看似简单，但必须用 long long。）

样例输入： 1000000000 1000000000 样例输出： 1000000000000000000

思路： N 和 M 各自能放进 int，但 N × M = 10^18——超出 int 上限（约 2.1×10^9），勉强放进 long long（上限约 9.2×10^18）。必须用 long long。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, m;
    cin >> n >> m;

    cout << n * m << "\n";

    return 0;
}

关键点：

• 用 long long 变量读取是关键——cin >> n 可以处理最大 9.2×10^18 的值
• 若用 int 变量：int n, m; cin >> n >> m; cout << n * m;——这会静默溢出，输出错误答案
• 做 USACO 题时，始终检查约束：若 N 最大 10^9，且可能要算 N × N，就需要 long long

挑战 2.1.13 — 象限问题 (USACO 2016 February Bronze) 读取两个非零整数 x 和 y，判断点 (x, y) 在坐标平面的哪个象限：

• 第一象限：x > 0 且 y > 0
• 第二象限：x < 0 且 y > 0
• 第三象限：x < 0 且 y < 0
• 第四象限：x > 0 且 y < 0

只打印象限数字：1、2、3 或 4。

样例输入 1： 3 5 → 输出： 1 样例输入 2： -1 2 → 输出： 2 样例输入 3： -4 -7 → 输出： 3 样例输入 4： 8 -3 → 输出： 4

思路： 判断 x 和 y 的正负。x 和 y 正负的每种组合恰好对应一个象限。使用 if/else-if 链（第 2.2 章会完整讲，但这里很直接）。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int x, y;
    cin >> x >> y;

    if (x > 0 && y > 0) {
        cout << 1 << "\n";
    } else if (x < 0 && y > 0) {
        cout << 2 << "\n";
    } else if (x < 0 && y < 0) {
        cout << 3 << "\n";
    } else {  // x > 0 && y < 0
        cout << 4 << "\n";
    }

    return 0;
}

关键点：

• && 运算符表示「且」——两个条件都必须为真
• 题目保证 x ≠ 0 且 y ≠ 0，无需处理这些边界情况
• 四种情况互斥（对任意输入恰好一种为真），else-if 链完美适用
• 可以用公式简化，但显式 if/else 更清晰，速度一样快

第 2.2 章：控制流

2.2.0 什么是「控制流」？

到目前为止，我们写的每个程序都是从上到下执行的——第 1 行、第 2 行、第 3 行，结束。就像从头到尾读一本书。

但真正的程序需要做决策并重复操作。这就是「控制流」的含义——控制执行的流（顺序）。

想象一本「选择你的冒险」书：

• 有时书上说「如果你想和龙战斗，翻到第 47 页；否则翻到第 52 页」
• 有时书上说「重复这一段，直到你逃出地牢」

C++ 通过以下方式提供了恰好对应的功能：

• if/else —— 根据条件做决策
• for/while 循环 —— 重复执行一段代码

这是控制流的总览：

在循环图示中：程序不断回到「步骤 2」，直到条件变为假，才退出到「步骤 3」。

2.2.1 if 语句

if 语句让你的程序做决策：「如果这个条件为真，就执行这件事。」

基本 if

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

int main() {
    int score;
    cin >> score;

    if (score >= 90) {
        cout << "优秀！\n";
    }

    cout << "完成。\n";  // 无论 score 是多少都会执行
    return 0;
}

score 为 95：打印「优秀！」然后「完成。」 score 为 80：只打印「完成。」（if 块被跳过）

if / else

int score;
cin >> score;

if (score >= 60) {
    cout << "通过\n";
} else {
    cout << "不通过\n";
}

else 块仅在 if 条件为假时执行。两个块中恰好只有一个会运行。

if / else if / else 链

需要检查多个条件时：

int score;
cin >> score;

if (score >= 90) {
    cout << "A\n";
} else if (score >= 80) {
    cout << "B\n";
} else if (score >= 70) {
    cout << "C\n";
} else if (score >= 60) {
    cout << "D\n";
} else {
    cout << "F\n";
}

C++ 从上到下按顺序检查这些条件，运行第一个为真的分支。一旦运行了一个块，就会跳过后面所有的 else if/else 块。

若 score = 85：

1. 85 >= 90？否 → 跳过
2. 85 >= 80？是 → 打印「B」，然后跳过后续所有 else-if

🤔 为什么这样有效？ 当我们到达 else if (score >= 80) 时，我们已经知道 score < 90（如果它 ≥ 90，第一个条件早就捕获了）。每个 else if 隐式假设所有前面的条件都为假。

比较运算符

逻辑运算符（组合条件）

int x, y;
cin >> x >> y;

if (x > 0 && y > 0) {
    cout << "两者都为正数\n";
}

if (x < 0 || y < 0) {
    cout << "至少有一个是负数\n";
}

bool done = false;
if (!done) {
    cout << "还在进行中……\n";
}

🐛 常见 Bug：= vs ==

这是新手（甚至有经验的程序员）最常犯的错误之一：

int x = 5;

// 危险的 BUG：
if (x = 10) {   // 这是把 10 赋值给 x，不是比较！
                 // x 变为 10，由于 10 不为零，这个条件永远为真
    cout << "x 是 10\n";  // 总是执行，即使 x 最初是 5！
}

// 正确写法：
if (x == 10) {  // 这才是比较 x 和 10
    cout << "x 是 10\n";  // 只有 x 真的等于 10 时才执行
}

= 运算符是赋值（存储一个值）；== 运算符是比较（检查两个值是否相等）。两者看起来相似，但功能完全不同。

⚡ 专业技巧： 有些程序员写 10 == x 而不是 x == 10——如果不小心写了 = 而不是 ==，就变成了 10 = x，会是编译错误（不能对字面量赋值）。这叫「尤达条件式」。

嵌套 if 语句

可以在 if 语句里再放 if 语句：

int age, income;
cin >> age >> income;

if (age >= 18) {
    cout << "成年人\n";
    if (income > 50000) {
        cout << "高收入成年人\n";
    } else {
        cout << "普通收入成年人\n";
    }
} else {
    cout << "未成年人\n";
}

注意：每个 else 匹配最近的、还没有 else 的 if。

2.2.2 while 循环

while 循环在条件为真时一直重复执行一段代码。条件变为假后，执行继续到循环之后。

while (条件) {
    循环体（反复执行）
}

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

int main() {
    int i = 1;             // 1. 循环前初始化
    while (i <= 5) {       // 2. 检查条件——若为假则跳过循环
        cout << i << "\n"; // 3. 执行循环体
        i++;               // 4. 更新——非常重要！忘了这步 → 死循环
    }
    // 循环后：i = 6，条件 6 <= 5 为假，循环退出
    return 0;
}

输出：

1
2
3
4
5

🐛 常见 Bug：死循环

如果忘了更新变量（上面的第 4 步），条件永远不会变为假，循环就会一直运行！

int i = 1;
while (i <= 5) {
    cout << i << "\n";
    // BUG：忘了 i++——这会永远打印「1」！
}

如果程序卡住了，按 Ctrl+C 强制停止。

什么时候用 while vs for

• 当事先不知道需要迭代多少次时，用 while
• 当知道次数时，用 for（下一节介绍）

while 的经典使用场景：读取直到满足某个条件。

// 常见 USACO 模式：读取直到输入结束
int x;
while (cin >> x) {    // cin >> x 在输入耗尽时返回 false
    cout << x * 2 << "\n";
}

do-while 循环

do-while 循环至少执行一次循环体，然后再检查条件：

int n;
do {
    cin >> n;
} while (n <= 0);   // 一直重新读，直到用户输入正数

当你想在判断是否重复之前先执行某件事时，这很有用。竞赛编程中不常见，但值得了解。

2.2.3 for 循环

for 循环是竞赛编程中最常用的循环。它将初始化、条件检查和更新打包在一行：

for (初始化; 条件; 更新) {
    循环体
}

等价于：

初始化;
while (条件) {
    循环体
    更新;
}

图示：for 循环流程图

流程图展示了执行过程：初始化只运行一次，之后每次迭代前检查条件，条件为假时退出循环。

常见 for 循环模式

// 从 0 数到 9（竞赛编程标准模式）
for (int i = 0; i < 10; i++) {
    cout << i << " ";
}
// 打印：0 1 2 3 4 5 6 7 8 9

// 从 1 数到 n（包含）
int n = 5;
for (int i = 1; i <= n; i++) {
    cout << i << " ";
}
// 打印：1 2 3 4 5

// 倒数
for (int i = 10; i >= 1; i--) {
    cout << i << " ";
}
// 打印：10 9 8 7 6 5 4 3 2 1

// 以 2 为步长
for (int i = 0; i <= 10; i += 2) {
    cout << i << " ";
}
// 打印：0 2 4 6 8 10

🧠 循环追踪：精确理解执行过程

学习循环时，手动追踪它们。方法如下：

代码： for (int i = 0; i < 4; i++) cout << i * i << " ";

先在纸上追踪循环，再运行——这能建立直觉并帮你发现 bug。

最常见的 USACO 循环模式

读取 N 个数并逐一处理：

int n;
cin >> n;

for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    // 在这里处理 x
    cout << x * 2 << "\n";
}

⚡ 专业技巧： 竞赛编程中，for (int i = 0; i < n; i++) 以 0 为起点是标准写法。这与数组的索引方式（第 2.3 章）一致，让一切都整齐地对应。

2.2.4 嵌套循环

可以在循环里再放一个循环。内层循环对外层循环的每一次迭代都会完整执行一遍。

// 打印 4×4 乘法表
for (int i = 1; i <= 4; i++) {         // 外层：行
    for (int j = 1; j <= 4; j++) {     // 内层：列
        cout << i * j << "\t";          // \t = 制表符
    }
    cout << "\n";  // 每行结束后换行
}

输出：

1   2   3   4
2   4   6   8
3   6   9   12
4   8   12  16

⚠️ 嵌套循环的时间复杂度

💡 为什么需要关心循环次数？ 竞赛中，你的程序通常需要在 1-2 秒内完成。现代计算机每秒可以执行约 10^8 到 10^9 次简单运算。因此，如果能估算出循环体总共执行多少次，就能判断是否会超时（TLE）。这是「时间复杂度分析」的核心思想——后续章节会深入学习。

单重 N 次循环执行 N 次操作；两层嵌套 N 次循环执行 N × N = N² 次操作。

N = 1000 时两层嵌套是 10^6 次操作——没问题。但 N = 100,000 时是 10^10——太慢了！

🧠 快速经验法则： 看到 N 的范围后，反向利用上表判断最多能用几层嵌套循环。例如：N ≤ 10^5 → 只能用 O(N) 或 O(N log N) 算法；N ≤ 5000 → O(N²) 可以接受。这在 USACO 中极为实用！

2.2.5 switch 语句

当你需要检查一个变量的许多具体值时，switch 比一长串 if/else if 更简洁：

int day;
cin >> day;

switch (day) {
    case 1:
        cout << "星期一\n";
        break;   // 重要：break 退出 switch
    case 2:
        cout << "星期二\n";
        break;
    case 3:
        cout << "星期三\n";
        break;
    case 4:
        cout << "星期四\n";
        break;
    case 5:
        cout << "星期五\n";
        break;
    case 6:
    case 7:
        cout << "周末！\n";  // case 6 和 7 共用这段代码
        break;
    default:
        cout << "无效的日期\n";  // 没有 case 匹配时执行
}

什么时候用 switch vs if-else

🐛 常见 Bug：忘记 break —— 没有 break，执行会「穿透」到下一个 case！

int x = 2;
switch (x) {
    case 1:
        cout << "one\n";
    case 2:
        cout << "two\n";   // 这会执行
    case 3:
        cout << "three\n"; // 这也会执行（穿透！因为 case 2 后没有 break）
}
// 输出：two\nthree\n（出乎意料！）

2.2.6 break 和 continue

break —— 立即退出循环

// 找 1 到 100 中第一个 7 的倍数
for (int i = 1; i <= 100; i++) {
    if (i % 7 == 0) {
        cout << "7 的第一个倍数：" << i << "\n";  // 打印 7
        break;  // 停止搜索——已找到
    }
}

continue —— 跳到下一次迭代

// 打印 1 到 10 中除了 3 的倍数之外的所有数
for (int i = 1; i <= 10; i++) {
    if (i % 3 == 0) {
        continue;  // 跳过本次迭代的剩余部分，直接到 i++
    }
    cout << i << " ";
}
// 输出：1 2 4 5 7 8 10

嵌套循环中的 break

break 只退出最内层的循环。要退出多层，用标志变量：

bool found = false;
int target = 25;

for (int i = 0; i < 10 && !found; i++) {    // 外层循环也检查 !found
    for (int j = 0; j < 10; j++) {
        if (i * j == target) {
            cout << i << " * " << j << " = " << target << "\n";
            found = true;
            break;   // 退出内层循环；外层循环因为 !found 也会退出
        }
    }
}

2.2.7 竞赛编程中的经典循环模式

这些模式几乎出现在每一道 USACO 题解中。熟记它们。

模式一：读取 N 个数，计算总和

int n;
cin >> n;

long long sum = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    sum += x;
}
cout << sum << "\n";

复杂度分析：

• 时间：O(N)——遍历 N 个数，每次 O(1) 处理
• 空间：O(1)——只有一个累加变量 sum

模式二：找最大值（和最小值）

int n;
cin >> n;

int maxVal, minVal;
cin >> maxVal;    // 读第一个元素
minVal = maxVal;  // 最大值和最小值都初始化为第一个元素

for (int i = 1; i < n; i++) {   // 从第二个元素开始（下标 1）
    int x;
    cin >> x;
    if (x > maxVal) maxVal = x;
    if (x < minVal) minVal = x;
}

cout << "最大值：" << maxVal << "\n";
cout << "最小值：" << minVal << "\n";

复杂度分析：

• 时间：O(N)——遍历 N 个数，每次比较 O(1)
• 空间：O(1)——只有 maxVal 和 minVal 两个变量

🤔 为什么初始化为第一个元素？ 不要初始化为 0！万一所有数都是负数呢？初始化为第一个元素保证我们从输入中的真实值开始。

模式三：统计满足条件的数量

int n;
cin >> n;

int count = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x % 2 == 0) {   // 条件：偶数
        count++;
    }
}
cout << "偶数个数：" << count << "\n";

模式四：打印星号三角形

int n;
cin >> n;

for (int row = 1; row <= n; row++) {     // row 从 1 到 n
    for (int col = 1; col <= row; col++) { // 每行打印 row 个星号
        cout << "*";
    }
    cout << "\n";  // 每行结束后换行
}

n=4 时输出：

*
**
***
****

模式五：计算各位数字之和

int n;
cin >> n;

int digitSum = 0;
while (n > 0) {
    digitSum += n % 10;  // 最后一位数字
    n /= 10;             // 删除最后一位
}
cout << digitSum << "\n";

追踪 n = 12345：

n=12345: digitSum += 5, n 变为 1234
n=1234:  digitSum += 4, n 变为 123
n=123:   digitSum += 3, n 变为 12
n=12:    digitSum += 2, n 变为 1
n=1:     digitSum += 1, n 变为 0
n=0: 循环退出。digitSum = 15 ✓

2.2.8 完整示例：USACO 风格题目

题目： 你有 N 头奶牛，每头都有一个产奶评分。找出评分最高的奶牛的评分，并统计产奶量高于平均水平的奶牛数量。

数据规模： 1 ≤ N ≤ 10⁵，0 ≤ 产奶评分 ≤ 10⁶。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 我们需要存储所有值来与平均值比较
    //（第 2.3 章学数组/向量——这里先用 vector 预览）

    // 第一遍：找总和和最大值
    long long sum = 0;
    int maxMilk = 0;
    vector<int> milk(n);   // 存储所有值（第 2.3 章预览）

    for (int i = 0; i < n; i++) {
        cin >> milk[i];
        sum += milk[i];
        if (milk[i] > maxMilk) maxMilk = milk[i];
    }

    double avg = (double)sum / n;

    // 第二遍：统计高于平均值的数量
    int aboveAvg = 0;
    for (int i = 0; i < n; i++) {
        if (milk[i] > avg) aboveAvg++;
    }

    cout << "最大值：" << maxMilk << "\n";
    cout << "高于平均值：" << aboveAvg << "\n";

    return 0;
}

样例输入：

5
10 20 30 40 50

样例输出：

最大值：50
高于平均值：2

（平均值为 30；产奶量 40 和 50 的奶牛高于平均值 → 2 头）

复杂度分析：

• 时间：O(N)——两遍（读取 + 统计），各 O(N)，总计 O(2N) = O(N)
• 空间：O(N)——使用 vector<int> milk(n) 存储所有数据

⚠️ 第 2.2 章常见错误

本章总结

📌 核心要点

🧩 五种经典循环模式快速参考

❓ 常见问题

Q1：for 和 while 可以互换吗？什么时候该用哪个？

A：是的，任何 for 循环都可以改写成 while，反之亦然。经验法则：知道迭代次数（如「循环 N 次」）用 for；不知道次数（如「读到输入结束」）用 while。竞赛中大约 90% 的情况用 for。

Q2：嵌套循环可以套多少层？有上限吗？

A：语法上没有上限，但实际中超过 3 层就需要谨慎。两层嵌套是 O(N²)，三层是 O(N³)。当 N ≥ 1000 时，三层嵌套很容易超时。如果发现需要超过 3 层嵌套，通常意味着需要更高效的算法（后续章节会讲）。

Q3：break 只退出最内层循环，怎么一次退出多层？

A：两种常用方法：① 用 bool found = false 标志变量，让外层循环也检查 !found；② 将嵌套循环放在函数里，用 return 直接退出。方法①更常见——参见 2.2.6 节的完整示例。

Q4：switch 和 if-else if 哪个更快？

A：case 数量少（< 10）时，性能几乎一样。switch 的优势在于代码可读性，不是速度。竞赛中两种都可以自由选择。如果条件涉及范围比较（如 x > 10），必须用 if-else。

Q5：程序本地输出正确，提交后却超时（TLE），怎么办？

A：第一步：估算算法复杂度。查看 N 的范围 → 用本章的「嵌套循环复杂度表」估算总操作次数 → 若超过 10^8，就需要优化。常见优化策略：减少循环层数、用排序+二分查找替代暴力搜索（第 3.3 章）、用前缀和替代重复求和（第 3.2 章）。

🔗 与后续章节的联系

• 第 2.3 章（函数与数组）让你把本章的循环模式封装成函数，并用数组存储数据集合
• 第 3.2 章（数组与前缀和）教你把 O(N²) 区间求和查询优化到 O(N) 预处理 + O(1) 每次查询——这是「嵌套循环太慢」问题的解决方案之一
• 第 3.3 章（排序与搜索）教你二分查找，把本章 O(N) 线性搜索优化到 O(log N)
• 本章学到的五种经典循环模式（求和、找最大/最小、计数、嵌套遍历、数字处理）是本书所有算法的基础构件
• 嵌套循环复杂度分析是理解时间复杂度（贯穿全书的主题）的第一步

练习题

热身 2.2.1 — 数到十 打印 1 到 10，每行一个数字。用 for 循环。

思路： 从 1 到 10（包含）的 for 循环。

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

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << i << "\n";
    }
    return 0;
}

关键点：

• i <= 10（而不是 i < 10）因为我们要包含 10
• 也可以写 for (int i = 1; i < 11; i++)——效果相同

热身 2.2.2 — 偶数 打印 2 到 20 的所有偶数，每行一个。

思路： 两种方案——步长为 2 循环，或每次循环检查是否为偶数。

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

int main() {
    // 方案一：步长为 2
    for (int i = 2; i <= 20; i += 2) {
        cout << i << "\n";
    }
    return 0;
}

关键点：

• i += 2 每次递增 2 而不是通常的 1
• 替代方案：for (int i = 1; i <= 20; i++) { if (i % 2 == 0) cout << i << "\n"; }

热身 2.2.3 — 正负零 读取一个整数，正数打印 Positive，负数打印 Negative，零打印 Zero。

样例输入： -5 → 输出： Negative

思路： 用三路 if/else if/else 覆盖所有情况。

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

int main() {
    int n;
    cin >> n;

    if (n > 0) {
        cout << "Positive\n";
    } else if (n < 0) {
        cout << "Negative\n";
    } else {
        cout << "Zero\n";
    }

    return 0;
}

关键点：

• 末尾的 else 精确捕获 n == 0（因为上面两个条件覆盖了 n>0 和 n<0）

热身 2.2.4 — 3 的乘法表 打印 3 的前 10 个倍数（即 3、6、9、……、30），每行一个。

思路： 从 1 循环到 10，每次打印 i*3。

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

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << i * 3 << "\n";
    }
    return 0;
}

关键点：

• 替代方案：for (int i = 3; i <= 30; i += 3)——效果相同

热身 2.2.5 — 五数之和 读取恰好 5 个整数（可以在同一行或不同行），打印它们的和。

样例输入： 3 7 2 8 5 → 输出： 25

思路： 循环读取 5 次，累加求和。

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

int main() {
    long long sum = 0;
    for (int i = 0; i < 5; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    cout << sum << "\n";
    return 0;
}

关键点：

• sum 用 long long 以防整数较大
• 因为题目说「恰好 5 个整数」，循环读取恰好 5 次

题目 2.2.6 — FizzBuzz 经典编程挑战：打印 1 到 100 的数字，但：

• 如果能被 3 整除，打印 Fizz
• 如果能被 5 整除，打印 Buzz
• 如果能同时被 3 和 5 整除，打印 FizzBuzz

输出开头几行：

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

思路： 循环 1 到 100。对每个数检查整除性——先检查同时整除的情况（被 3 和 5 整除），否则会被单独的 Fizz 或 Buzz 分支先捕获。

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

int main() {
    for (int i = 1; i <= 100; i++) {
        if (i % 3 == 0 && i % 5 == 0) {
            cout << "FizzBuzz\n";
        } else if (i % 3 == 0) {
            cout << "Fizz\n";
        } else if (i % 5 == 0) {
            cout << "Buzz\n";
        } else {
            cout << i << "\n";
        }
    }
    return 0;
}

关键点：

• 先检查 i % 3 == 0 && i % 5 == 0——如果先检查 i % 3 == 0，15 就会打印「Fizz」而永远到不了 FizzBuzz 分支
• 同时被 3 和 5 整除的数就是被 15 整除：i % 15 == 0 也有效

题目 2.2.7 — N 中最小值 读取 N（1 ≤ N ≤ 1000），然后读取 N 个整数，打印最小值。

样例输入：

5
8 3 7 1 9

样例输出： 1

思路： 用读取的第一个值初始化最小值，每次看到更小的就更新。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int first;
    cin >> first;
    int minVal = first;  // 初始化为第一个元素

    for (int i = 1; i < n; i++) {   // 读取剩余 n-1 个元素
        int x;
        cin >> x;
        if (x < minVal) {
            minVal = x;
        }
    }

    cout << minVal << "\n";
    return 0;
}

关键点：

• 将 minVal 初始化为读取的第一个元素（不是 0 或 INT_MAX），然后在循环中处理剩余元素
• 替代方案：用 INT_MAX 作为初始值——保证大于任何 int，第一个元素一定会更新它

题目 2.2.8 — 统计正数 读取 N（1 ≤ N ≤ 1000），然后读取 N 个整数，打印其中严格正数（> 0）的个数。

样例输入：

6
3 -1 0 5 -2 7

样例输出： 3

思路： 维护一个计数器，满足条件（x > 0）时递增。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int count = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > 0) {
            count++;
        }
    }

    cout << count << "\n";
    return 0;
}

关键点：

• count 从 0 开始，只在 x > 0 时递增
• 0 不是正数（也不是负数——它是零），所以 x > 0 正确地排除了它

题目 2.2.9 — 星号三角形 读取 N，打印一个 N 行的直角三角形，第 i 行有 i 个星号。

样例输入： 4

样例输出：

*
**
***
****

思路： 嵌套循环——外层遍历行，内层打印对应数量的星号。

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

int main() {
    int n;
    cin >> n;

    for (int row = 1; row <= n; row++) {
        for (int star = 1; star <= row; star++) {
            cout << "*";
        }
        cout << "\n";
    }

    return 0;
}

关键点：

• 第 1 行 1 个星号，第 2 行 2 个，……，第 N 行 N 个
• 内层循环对每个 row 值恰好执行 row 次
• 使用 string 的替代方案：cout << string(row, '*') << "\n";——创建 row 个 * 的字符串

题目 2.2.10 — 各位数字之和 读取正整数 N（1 ≤ N ≤ 10^9），打印其各位数字之和。

样例输入： 12345 → 样例输出： 15 样例输入： 9999 → 样例输出： 36

思路： 用取模技巧。N % 10 得到最后一位。N / 10 删除最后一位。重复直到 N 变为 0。

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

int main() {
    int n;
    cin >> n;

    int digitSum = 0;
    while (n > 0) {
        digitSum += n % 10;  // 加上最后一位
        n /= 10;             // 删除最后一位
    }

    cout << digitSum << "\n";
    return 0;
}

关键点：

• n % 10 提取个位数（如 12345 % 10 = 5）
• n /= 10 是整数除法，删除最后一位（如 12345 / 10 = 1234）
• 循环持续到 n = 0（所有数字都已提取）
• 追踪：12345 → +5 → 1234 → +4 → 123 → +3 → 12 → +2 → 1 → +1 → 0。总和 = 15 ✓

🏆 挑战题

挑战 2.2.11 — 考拉兹序列 从 N 开始的考拉兹序列规则如下：

• N 是偶数：下一项 = N / 2
• N 是奇数：下一项 = N × 3 + 1
• N = 1 时停止

读取 N，打印整个序列（包括 N 和 1），以及到达 1 需要的步数。

样例输入： 6 样例输出：

6 3 10 5 16 8 4 2 1
Steps: 8

思路： 用 while 循环，不断应用规则直到到达 1，同时计数步数。

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

int main() {
    long long n;
    cin >> n;

    int steps = 0;
    cout << n;         // 打印起始数字

    while (n != 1) {
        if (n % 2 == 0) {
            n = n / 2;
        } else {
            n = n * 3 + 1;
        }
        cout << " " << n;  // 打印下一个数字
        steps++;
    }
    cout << "\n";
    cout << "Steps: " << steps << "\n";

    return 0;
}

关键点：

• 用 long long——即使从小数开始，序列中间值也可能很大（如 N=27 会到达 9232！）
• 考拉兹猜想称这个序列总会到达 1，但对所有 N 尚未被证明
• 循环前打印 N（作为起始值），之后每步打印新值

挑战 2.2.12 — 质数判断 读取 N（2 ≤ N ≤ 10^6），若 N 是质数打印 prime，否则打印 composite。

质数是只有 1 和它本身两个因数的数。

样例输入： 17 → 输出： prime 样例输入： 100 → 输出： composite

思路： 试除法——检查 2 到 √N 中有没有能整除 N 的数。如果没有，N 是质数。只需检查到 √N，因为若 N = a×b 且 a > √N，则 b < √N（早就找到了）。

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

int main() {
    int n;
    cin >> n;

    bool isPrime = true;

    if (n < 2) {
        isPrime = false;
    } else {
        // 检查 2 到 sqrt(n) 的因数
        for (int i = 2; (long long)i * i <= n; i++) {
            if (n % i == 0) {
                isPrime = false;
                break;  // 找到因数，无需继续
            }
        }
    }

    cout << (isPrime ? "prime" : "composite") << "\n";
    return 0;
}

关键点：

• 用 i * i <= n 而不是 i <= sqrt(n)，避免浮点精度问题（也稍快）
• (long long)i * i 防止 i 较大时溢出（如 i = 1000000，i*i = 10^12）
• break 找到任意因数后立即退出——无需继续检查
• 时间复杂度：O(√N)，处理 N 最大 10^6 非常轻松（√10^6 = 1000 次迭代）

挑战 2.2.13 — 评分最高的奶牛 读取 N（1 ≤ N ≤ 1000），然后读取 N 对（奶牛名字，评分）。找出评分最高的奶牛并打印其名字。

样例输入：

4
Bessie 95
Elsie 82
Moo 95
Daisy 88

样例输出： Bessie （若有并列，打印最先出现的那头。）

思路： 跟踪目前见过的最佳评分和名字，只在严格更高时更新。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    string bestName;
    int bestRating = -1;  // 初始化为 -1，任何真实评分都高于它

    for (int i = 0; i < n; i++) {
        string name;
        int rating;
        cin >> name >> rating;

        if (rating > bestRating) {
            bestRating = rating;
            bestName = name;
        }
    }

    cout << bestName << "\n";
    return 0;
}

关键点：

• 初始化 bestRating = -1（或 INT_MIN），让第一头奶牛始终成为新的最佳
• 用 >（严格大于）而非 >=，这样并列时保留最先出现的（题目要求）
• cin >> name >> rating 从同一行读取字符串和整数——完全有效

第 2.3 章：函数与数组

随着程序越来越大，你需要组织代码的方式（函数）和存储数据集合的方式（数组和向量）。本章介绍这两者——竞赛编程中最重要的两个工具。

2.3.1 函数——是什么，为什么需要

🍕 食谱类比

函数就像一份披萨食谱：

- 输入（参数）：   食材——面粉、奶酪、番茄
- 过程（函数体）：烹饪步骤
- 输出（返回值）：做好的披萨

就像你可以用一份食谱做很多张披萨，
你可以用不同的输入多次调用一个函数。

pizza("薄底", "培根")  → 一张披萨
pizza("厚底", "蘑菇")  → 另一张披萨

没有函数，如果你需要在程序的五个地方计算「这个数是不是质数」，你就得把同样的 10 行代码复制粘贴五次。然后如果发现了 bug，就要在五个地方全部修复！

什么时候写函数

以下情况使用函数：

1. 程序中某段逻辑重复了 3 次以上
2. 某段代码做的是一件清晰命名的事（如「检查是否质数」「计算距离」）
3. 你的 main 变得太长、不好读

函数的基本语法

返回类型 函数名(参数1类型 参数1, 参数2类型 参数2, ...) {
    // 函数体
    return 值;  // 必须与返回类型匹配；void 函数可省略
}

你的第一批函数

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

// ---- 函数定义（必须在使用前定义，或使用前置声明）----

// 接收一个整数，返回它的平方
int square(int x) {
    return x * x;
}

// 接收两个整数，返回较大的那个
int maxOf(int a, int b) {
    if (a > b) return a;
    else return b;
}

// void 函数：执行某件事但不返回值
void printSeparator() {
    cout << "====================\n";
}

// ---- 主函数 ----
int main() {
    cout << square(5) << "\n";       // 以 x=5 调用 square，打印 25
    cout << square(12) << "\n";      // 以 x=12 调用 square，打印 144

    cout << maxOf(7, 3) << "\n";     // 打印 7
    cout << maxOf(-5, -2) << "\n";   // 打印 -2

    printSeparator();                // 打印分隔线
    cout << "完成！\n";
    printSeparator();

    return 0;
}

🤔 为什么函数要在 main 之前？

C++ 从上到下读取你的文件。当它看到 square(5) 这样的调用时，需要已经知道 square 是什么。如果 square 在 main 之后定义，编译器会说「我从没听说过 square！」

方案一： 把所有函数定义在 main 之上（最简单）。

方案二： 使用函数原型——前置声明，告诉编译器「这个函数存在，我之后再定义」：

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

int square(int x);       // 原型——只有签名，没有函数体
int maxOf(int a, int b); // 原型

int main() {
    cout << square(5) << "\n";   // OK！编译器知道 square 存在
    return 0;
}

// 完整定义可以在 main 之后
int square(int x) {
    return x * x;
}

int maxOf(int a, int b) {
    return (a > b) ? a : b;
}

2.3.2 void 函数 vs 返回值函数

void 函数：执行操作，不返回值

// void 函数执行某个动作
void printLine(int n) {
    for (int i = 0; i < n; i++) {
        cout << "-";
    }
    cout << "\n";
}

// 调用 void 函数——直接调用，不要尝试接收返回值
printLine(10);    // 打印：----------
printLine(20);    // 打印：--------------------

返回值函数：计算并返回一个值

// 返回 x 的绝对值
int absoluteValue(int x) {
    if (x < 0) return -x;
    return x;
}

// 调用返回值函数——把结果存入变量或直接使用
int result = absoluteValue(-7);
cout << result << "\n";           // 7
cout << absoluteValue(-3) << "\n"; // 3（直接使用）

多个 return 语句

函数可以有多个 return 语句——执行到第一个就停止：

string classify(int n) {
    if (n < 0) return "负数";   // n < 0 时从这里退出
    if (n == 0) return "零";    // n == 0 时从这里退出
    return "正数";              // 其他情况从这里退出
}

cout << classify(-5) << "\n";   // 负数
cout << classify(0) << "\n";    // 零
cout << classify(3) << "\n";    // 正数

2.3.3 按值传递 vs 按引用传递

向函数传递变量时有两种方式。理解这一点至关重要。

按值传递（默认）：函数得到一个副本

void addOne_byValue(int x) {
    x++;  // 修改的是局部副本——原变量不变
    cout << "函数内部：" << x << "\n";  // 6
}

int main() {
    int n = 5;
    addOne_byValue(n);
    cout << "函数之后：" << n << "\n";   // 还是 5！原变量未改变
    return 0;
}

可以把它想成复印件：函数对复印件进行操作，对复印件的修改不影响原件。

按引用传递（&）：函数操作原变量

void addOne_byRef(int& x) {  // & 表示「原变量的引用」
    x++;  // 直接修改原变量
    cout << "函数内部：" << x << "\n";  // 6
}

int main() {
    int n = 5;
    addOne_byRef(n);
    cout << "函数之后：" << n << "\n";   // 现在是 6！原变量被改变了
    return 0;
}

什么时候用哪种

通过引用返回多个值

C++ 函数只能 return 一个值。但可以通过引用参数「返回」多个值：

// 同时计算商和余数
void divmod(int a, int b, int& quotient, int& remainder) {
    quotient = a / b;
    remainder = a % b;
}

int main() {
    int q, r;
    divmod(17, 5, q, r);  // q 和 r 被函数修改
    cout << "17 / 5 = " << q << " 余 " << r << "\n";
    // 打印：17 / 5 = 3 余 2
    return 0;
}

2.3.4 递归

递归函数是调用自身的函数。它非常适合可以拆解成同类问题的更小版本的问题。

经典示例：阶乘

5! = 5 × 4 × 3 × 2 × 1 = 120
   = 5 × (4!)              ← 同样的问题，更小的输入！

💡 递归思维三步法：

1. 找「自相似性」： 原问题能否拆解为同类型的更小问题？5! = 5 × 4!，4! 和 5! 是同一类型 ✓
2. 确定边界条件： 最小的情况是什么？0! = 1，不能再拆解
3. 写递推步骤： n! = n × (n-1)!，用更小的输入调用自身

这个思维过程在**图论算法（第 5.1 章）和动态规划（第 6.1-6.3 章）**中会反复用到。

int factorial(int n) {
    if (n == 0) return 1;            // 边界条件：停止递归
    return n * factorial(n - 1);    // 递推步骤：缩小到更小的问题
}

追踪 factorial(4)：

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * (1 * factorial(0))))
= 4 * (3 * (2 * (1 * 1)))   ← 边界条件！
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24  ✓

每个递归函数都需要：

1. 边界条件 —— 停止递归（防止无限递归）
2. 递推步骤 —— 用更小的输入调用自身

🐛 常见 Bug： 忘记边界条件 → 无限递归 → 「栈溢出」崩溃！

📌 名词预告： 递归是后面一大类算法的地基——5.2 章的 DFS（走迷宫/探房间）、回溯（「选择 → 递归 → 撤销」，枚举所有排列与组合）和第 6 部分的动态规划，全是「函数调用自己处理更小的问题」。现在只需要把阶乘这种一层的递归想明白。

2.3.5 数组——固定大小的集合

🏠 邮箱类比

数组就像街道上一排邮箱：
- 所有邮箱大小相同（相同类型）
- 每个都有门号（下标，从 0 开始）
- 可以通过门号直接找到任意邮箱

图示：数组内存布局

数组在内存中是连续存储的，每个元素紧挨着前一个，因此支持 O(1) 随机访问。

数组基础

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

int main() {
    // 声明一个有 5 个整数的数组（元素未初始化——是垃圾值！）
    int arr[5];

    // 逐一赋值
    arr[0] = 10;
    arr[1] = 20;
    arr[2] = 30;
    arr[3] = 40;
    arr[4] = 50;

    // 同时声明和初始化
    int nums[5] = {1, 2, 3, 4, 5};

    // 全部初始化为零
    int zeros[100] = {};          // 所有 100 个元素 = 0
    int zeros2[100];
    fill(zeros2, zeros2 + 100, 0); // 另一种方式

    // 访问和打印
    cout << arr[2] << "\n";       // 30

    // 遍历数组
    for (int i = 0; i < 5; i++) {
        cout << nums[i] << " ";   // 1 2 3 4 5
    }
    cout << "\n";

    return 0;
}

🐛 差一错误——头号数组 Bug

数组是从 0 开始索引的：如果你声明 int arr[5]，合法下标是 0, 1, 2, 3, 4，不存在 arr[5]！

int arr[5] = {10, 20, 30, 40, 50};

// 错误：循环从 i=0 到 i=5 包含——下标 5 不存在！
for (int i = 0; i <= 5; i++) {   // BUG：<= 5 应改为 < 5
    cout << arr[i];               // i=5 时崩溃或打印垃圾值
}

// 正确：循环从 i=0 到 i=4（i < 5 确保 i 永远到不了 5）
for (int i = 0; i < 5; i++) {    // i 的值：0, 1, 2, 3, 4 ✓
    cout << arr[i];               // 始终有效
}

这就是「差一错误」——越过末尾一个元素。这是竞赛编程中最常见的数组 bug。

🤔 为什么从 0 开始？ C++ 从 C 继承了这个设计，而 C 的设计贴近硬件。下标实际上是从数组起点的偏移量。第一个元素在偏移量 0 处（从起点无偏移）。

大数组用全局变量

main 里的局部变量存在「栈」上，空间有限（约 1-8 MB）。竞赛编程中 N 最大可达 10^6，需要用全局数组（存在不同的内存区域，空间大得多）：

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

const int MAXN = 1000001;  // 最大长度 + 1（常见惯例）
int arr[MAXN];              // 全局声明——大数组安全
// 全局数组会自动初始化为 0！

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    return 0;
}

⚡ 专业技巧： 全局数组会自动初始化为 0。局部数组不会——它们在赋值前包含垃圾值！

2.3.6 常见数组算法

求和、最大值、最小值

int n;
cin >> n;

vector<int> arr(n);    // 马上学 vector；用法与数组相同
for (int i = 0; i < n; i++) cin >> arr[i];

// 求和
long long sum = 0;
for (int i = 0; i < n; i++) sum += arr[i];
cout << "总和：" << sum << "\n";

// 最大值（初始化为第一个元素！）
int maxVal = arr[0];
for (int i = 1; i < n; i++) {
    if (arr[i] > maxVal) maxVal = arr[i];
}
cout << "最大值：" << maxVal << "\n";

// 最小值（同理）
int minVal = arr[0];
for (int i = 1; i < n; i++) {
    minVal = min(minVal, arr[i]);  // min() 是内置函数
}
cout << "最小值：" << minVal << "\n";

复杂度分析：

• 时间：O(N)——每个算法只需一次遍历
• 空间：O(1)——只需几个额外变量（不计输入数组本身）

翻转数组

int arr[] = {1, 2, 3, 4, 5};
int n = 5;

// 从两端向中间交换元素
for (int i = 0, j = n - 1; i < j; i++, j--) {
    swap(arr[i], arr[j]);  // swap() 是内置函数
}
// arr 现在是 {5, 4, 3, 2, 1}

复杂度分析：

• 时间：O(N)——每对元素交换一次，共 N/2 次
• 空间：O(1)——原地交换，不需要额外数组

二维数组

二维数组就像一张表格或网格，非常适合地图、棋盘、矩阵：

int grid[3][4];  // 3 行 4 列

// 填入 i * 10 + j
for (int r = 0; r < 3; r++) {
    for (int c = 0; c < 4; c++) {
        grid[r][c] = r * 10 + c;
    }
}

// 打印
for (int r = 0; r < 3; r++) {
    for (int c = 0; c < 4; c++) {
        cout << grid[r][c] << "\t";
    }
    cout << "\n";
}

输出：

0   1   2   3
10  11  12  13
20  21  22  23

2.3.7 向量（vector）——动态数组

数组有一个大限制：大小必须在编译时确定（或事先声明得足够大）。向量解决了这个问题——在程序运行时可以按需增减大小。

数组 vs 向量对比

向量基础

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

int main() {
    // 创建空向量
    vector<int> v;

    // 用 push_back 在末尾添加元素
    v.push_back(10);    // v = [10]
    v.push_back(20);    // v = [10, 20]
    v.push_back(30);    // v = [10, 20, 30]

    // 按下标访问（与数组相同，从 0 开始）
    cout << v[0] << "\n";     // 10
    cout << v[1] << "\n";     // 20

    // 常用函数
    cout << v.size() << "\n"; // 3（元素个数）
    cout << v.front() << "\n"; // 10（第一个元素）
    cout << v.back() << "\n";  // 30（最后一个元素）
    cout << v.empty() << "\n"; // 0（false——不为空）

    // 删除最后一个元素
    v.pop_back();   // v = [10, 20]

    // 清空所有元素
    v.clear();      // v = []
    cout << v.empty() << "\n"; // 1（true——现在为空）

    return 0;
}

创建带初始值的向量

vector<int> zeros(10, 0);       // 十个 0：[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
vector<int> ones(5, 1);         // 五个 1：[1, 1, 1, 1, 1]
vector<int> primes = {2, 3, 5, 7, 11};  // 从列表初始化
vector<int> empty;              // 空向量

遍历向量

vector<int> v = {10, 20, 30, 40, 50};

// 方法一：下标循环（与数组相同）
for (int i = 0; i < (int)v.size(); i++) {
    cout << v[i] << " ";
}
cout << "\n";

// 方法二：范围 for 循环（更简洁，推荐）
for (int x : v) {
    cout << x << " ";
}
cout << "\n";

// 方法三：引用范围 for（需要修改时使用）
for (int& x : v) {
    x *= 2;  // 将每个元素就地翻倍
}

🤔 为什么下标循环用 (int)v.size()？ v.size() 返回的是无符号整数。把 int i 和无符号值比较，C++ 有时会产生意外行为（尤其是 i 为负时）。转成 (int) 是安全习惯。

USACO 中使用向量的标准模式

int n;
cin >> n;

vector<int> arr(n);         // 创建大小为 n 的向量
for (int i = 0; i < n; i++) {
    cin >> arr[i];          // 读入每个位置
}

// 现在处理 arr...
sort(arr.begin(), arr.end());  // 升序排序

二维向量

int rows = 3, cols = 4;
vector<vector<int>> grid(rows, vector<int>(cols, 0));  // 3×4 的全 0 网格

// 访问：grid[r][c]
grid[1][2] = 42;
cout << grid[1][2] << "\n";  // 42

2.3.8 向函数传递数组和向量

数组

向函数传递数组时，函数收到的是第一个元素的指针。函数内部的修改会影响原数组：

void fillSquares(int arr[], int n) {  // 数组参数的 arr[] 语法
    for (int i = 0; i < n; i++) {
        arr[i] = i * i;   // 修改的是原数组！
    }
}

int main() {
    int arr[5] = {0};
    fillSquares(arr, 5);
    // arr 现在是 {0, 1, 4, 9, 16}
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
    cout << "\n";
    return 0;
}

向量

向量传递给函数时默认是复制（大向量很慢！）。用 & 按引用传递：

// 按值传递——复制整个向量（大向量时很慢）
void printVec(vector<int> v) {
    for (int x : v) cout << x << " ";
}

// 按引用传递——不复制，可修改原向量（用于输出参数）
void sortVec(vector<int>& v) {
    sort(v.begin(), v.end());
}

// 按 const 引用传递——不复制，不可修改（只读时最佳）
void printVecFast(const vector<int>& v) {
    for (int x : v) cout << x << " ";
}

⚡ 专业技巧： 对于只读（不修改）的向量参数，始终写 const vector<int>&。这既避免了复制，也向读者表明函数不会修改向量。

⚠️ 第 2.3 章常见错误

本章总结

📌 核心要点

❓ 常见问题

Q1：数组和向量哪个更好？

A：竞赛编程中两者都常用。经验法则：大小固定且已知时，全局数组最简单；大小动态变化或需要传给函数时，用 vector。很多选手默认用 vector，因为它更灵活、更不容易出错。

Q2：递归深度有限制吗？会崩溃吗？

A：有。每次函数调用都在栈上分配空间，默认栈大小约 1-8 MB。实际上，约 10^4 到 10^5 层递归是安全的。超出后程序会以「栈溢出」崩溃。竞赛中如果递归深度可能超过 10^4，考虑改用迭代（循环）方式。

Q3：什么时候用按引用传递（&）？

A：两种情况：① 需要在函数内部修改原变量；② 参数是大对象（如 vector 或 string），想避免复制开销。对于 int、double 这样的小类型，复制开销可忽略不计，按值传递即可。

Q4：函数可以返回数组或向量吗？

A：数组不能直接返回，但 vector 可以！vector<int> solve() { ... return result; } 完全有效。现代 C++ 编译器会优化返回过程（称为 RVO），实际上不会复制整个向量。

Q5：为什么前缀和数组多一个索引？prefix[n+1] 而不是 prefix[n]？

A：prefix[0] = 0 是一个「哨兵值」，使得公式 prefix[R+1] - prefix[L] 在所有情况下都有效。没有这个哨兵，查询 [0, R] 时 L=0 需要特殊处理。这是一个非常常见的编程技巧：用额外的哨兵值简化边界处理。

🔗 与后续章节的联系

• 第 3.1 章（STL 核心用法）将介绍 sort、binary_search、pair 等工具，让你用一行代码完成本章手动实现的操作
• 第 3.2 章（前缀和）将深入探讨题目 2.3.10 中引入的前缀和技术，包括二维前缀和和差分数组
• 第 5.1 章（图的基础）将以 2.3.4 节的递归基础为起点，讲解 DFS 和 BFS 等图遍历算法
• 第 6.1-6.3 章（动态规划）：「把大问题拆解成小问题」的核心思想与递归密切相关；本章的递归思维是重要的基础
• 本章学到的函数封装和数组/向量操作将在后续每一章中持续使用

练习题

热身 2.3.1 — 平方函数 编写一个函数 int square(int x)，返回 x²。在 main 中读取一个整数并打印其平方。

样例输入： 7 → 样例输出： 49

思路： 把函数写在 main 之上，用输入调用它。

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

int square(int x) {
    return x * x;
}

int main() {
    int n;
    cin >> n;
    cout << square(n) << "\n";
    return 0;
}

关键点：

• 函数定义在 main 之上，编译器才能识别
• return x * x;——C++ 计算 x * x 并返回结果
• 若 x 可能很大（如最大 10^9），用 long long（x² 最大 10^18）

热身 2.3.2 — 两数之大 编写函数 int myMax(int a, int b)，返回两个整数中较大的。在 main 中读取两个整数并打印较大值。

样例输入： 13 7 → 样例输出： 13

思路： 比较 a 和 b，返回较大的那个。

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

int myMax(int a, int b) {
    if (a > b) return a;
    return b;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << myMax(a, b) << "\n";
    return 0;
}

关键点：

• C++ 有内置的 max(a, b) 函数——但自己写一遍有助于理解概念
• 三目运算符替代方案：return (a > b) ? a : b;

热身 2.3.3 — 倒序数组 声明一个恰好有 5 个整数的数组：{1, 2, 3, 4, 5}。倒序打印（不需要输入）。

期望输出：

5 4 3 2 1

思路： 从下标 4 循环到 0（倒序）。

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

int main() {
    int arr[5] = {1, 2, 3, 4, 5};

    for (int i = 4; i >= 0; i--) {
        cout << arr[i];
        if (i > 0) cout << " ";
    }
    cout << "\n";

    return 0;
}

关键点：

• 从下标 n-1 = 4 循环到 0（包含），使用 i--
• if (i > 0) cout << " " 避免末尾多一个空格——不过对 USACO 来说末尾空格通常可以接受

热身 2.3.4 — 向量求和 创建一个向量，用 push_back 依次加入 10、20、30、40、50，然后打印它们的总和。

期望输出： 150

思路： 创建空向量，push 5 个值，循环求和。

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

int main() {
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    long long sum = 0;
    for (int x : v) {
        sum += x;
    }

    cout << sum << "\n";
    return 0;
}

关键点：

• 范围 for for (int x : v) 遍历所有元素
• 一行替代方案：accumulate(v.begin(), v.end(), 0LL)

热身 2.3.5 — Hello N 次 编写一个 void 函数 sayHello(int n)，打印「Hello!」恰好 n 次。读取 n 后从 main 调用它。

样例输入： 3 样例输出：

Hello!
Hello!
Hello!

思路： 一个内含 for 循环的 void 函数。

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

void sayHello(int n) {
    for (int i = 0; i < n; i++) {
        cout << "Hello!\n";
    }
}

int main() {
    int n;
    cin >> n;
    sayHello(n);
    return 0;
}

关键点：

• void 表示函数不返回任何值——不需要 return 值;（可以用裸 return; 提前退出）
• sayHello 参数中的 n 是 main 中 n 的独立副本（按值传递）

题目 2.3.6 — 倒序输出 读取 N（1 ≤ N ≤ 100），然后读取 N 个整数，倒序打印。

样例输入：

5
1 2 3 4 5

样例输出： 5 4 3 2 1

思路： 存入向量，然后从最后一个下标到第一个倒序打印。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    for (int i = n - 1; i >= 0; i--) {
        cout << arr[i];
        if (i > 0) cout << " ";
    }
    cout << "\n";

    return 0;
}

关键点：

• vector<int> arr(n) 创建大小为 n 的向量（初始全为零）
• 就像数组一样读入 arr[i]
• 从 n-1 循环到 0（包含）打印

题目 2.3.7 — 动态平均值 读取 N（1 ≤ N ≤ 100），然后逐个读取 N 个整数。每读入一个整数后，打印当前已读所有整数的平均值（保留 2 位小数）。

样例输入：

4
10 20 30 40

样例输出：

10.00
15.00
20.00
25.00

思路： 维护累计和，每次新读入后除以已读个数。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
        double avg = (double)sum / i;
        cout << fixed << setprecision(2) << avg << "\n";
    }

    return 0;
}

关键点：

• 每次新元素读入后更新 sum；i 是已读元素个数
• (double)sum / i——先强转为 double 再除，得到小数结果
• fixed << setprecision(2) 强制输出恰好 2 位小数

题目 2.3.8 — 频率统计 读取 N（1 ≤ N ≤ 100）个整数，每个整数在 1 到 10 之间。打印 1 到 10 中每个值出现的次数。

样例输入：

7
3 1 2 3 3 1 7

样例输出：

1 appears 2 times
2 appears 1 times
3 appears 3 times
4 appears 0 times
5 appears 0 times
6 appears 0 times
7 appears 1 times
8 appears 0 times
9 appears 0 times
10 appears 0 times

思路： 用数组（或向量）作为「计数器」——下标 1 到 10 存储对应值的计数。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int freq[11] = {};  // 下标 0-10；我们用 1-10。全部初始化为 0。

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        freq[x]++;    // 值 x 的计数加一
    }

    for (int v = 1; v <= 10; v++) {
        cout << v << " appears " << freq[v] << " times\n";
    }

    return 0;
}

关键点：

• freq[x]++ 是非常常见的模式——用值作为频率数组的下标
• 声明 freq[11]，下标 0-10，使 freq[10]（表示值 10）有效
• int freq[11] = {}——= {} 将所有元素初始化为零

题目 2.3.9 — 两数之和 读取 N（1 ≤ N ≤ 100）个整数和目标值 T。如果数组中任意两个不同元素相加等于 T，打印 YES，否则打印 NO。

样例输入：

5 9
1 4 5 6 3

（N=5，T=9，然后是数组） 样例输出： YES（因为 4+5=9 或 3+6=9）

思路： 检查所有满足 i < j 的对 (i, j)，若任意一对之和等于 T，打印 YES。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, t;
    cin >> n >> t;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    bool found = false;
    for (int i = 0; i < n && !found; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == t) {
                found = true;
                break;
            }
        }
    }

    cout << (found ? "YES" : "NO") << "\n";

    return 0;
}

关键点：

• 内层循环从 j = i + 1 开始，避免同一元素使用两次，也避免重复检查相同的对
• break + 外层循环的 && !found 条件确保找到匹配后立即停止
• 这是 O(N²)——对 N ≤ 100 完全够用。N 最大 10^5 时，需要用集合（第 3.1 章）

题目 2.3.10 — 前缀和 读取 N（1 ≤ N ≤ 1000），然后读取 N 个整数。再读取 Q 个查询（1 ≤ Q ≤ 1000），每个查询有两个整数 L 和 R（0-indexed，包含两端）。对每个查询打印下标 L 到 R 的元素之和。

样例输入：

5
1 2 3 4 5
3
0 2
1 3
2 4

样例输出：

6
9
12

为什么不对每次查询直接求和？ 暴力法：每次查询从 L 循环到 R，时间复杂度 O(N)，所有查询总计 O(N×Q)。当 N=10^5，Q=10^5 时是 10^{10} 次操作——远超时限。

优化思路： 预处理一次，O(N)；之后每次查询只需 O(1)。总计 O(N+Q)，快得多！这就是前缀和的核心思想（第 3.2 章深入讲解）。

思路： 构建前缀和数组，prefix[i] = arr[0..i-1] 的和。则 L 到 R 的和 = prefix[R+1] - prefix[L]，每次查询 O(1)。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<long long> arr(n), prefix(n + 1, 0);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        prefix[i + 1] = prefix[i] + arr[i];  // 构建前缀和
    }
    // prefix[0] = 0
    // prefix[1] = arr[0]
    // prefix[2] = arr[0] + arr[1]
    // prefix[i] = arr[0] + arr[1] + ... + arr[i-1]

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        // l 到 r（含）的和 = prefix[r+1] - prefix[l]
        cout << prefix[r + 1] - prefix[l] << "\n";
    }

    return 0;
}

关键点：

• prefix[i] = 前 i 个元素之和（prefix[0] = 0 是哨兵）
• arr[L..R] 的和 = prefix[R+1] - prefix[L]——减去 L 之前的部分
• 用样例验证：arr=[1,2,3,4,5]，prefix=[0,1,3,6,10,15]。查询 [0,2]：prefix[3]-prefix[0]=6-0=6 ✓

复杂度分析：

• 时间：O(N + Q)——预处理 O(N) + 每次查询 O(1) × Q
• 空间：O(N)——前缀和数组占 N+1 的空间

💡 暴力 vs 优化： 暴力 O(N×Q) vs 前缀和 O(N+Q)。N=Q=10^5 时，前者需 10^{10} 次操作（超时），后者只需 2×10^5 次操作（瞬间）。

🏆 挑战题

挑战 2.3.11 — 数组旋转 读取 N（1 ≤ N ≤ 1000）和 K（0 ≤ K < N），再读取 N 个整数。打印向右旋转 K 位后的数组（最后 K 个元素移到最前面）。

样例输入：

5 2
1 2 3 4 5

样例输出： 4 5 1 2 3

思路： 新数组在位置 i 的元素原来在位置 (i - K + N) % N。等价地，从下标 N-K 开始打印，循环回绕。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    // 从下标 (n - k) % n 开始打印 n 个元素，循环回绕
    for (int i = 0; i < n; i++) {
        int idx = (n - k + i) % n;
        cout << arr[idx];
        if (i < n - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

关键点：

• 右旋 K 位：后 K 个元素先输出，再输出前 N-K 个
• (n - k + i) % n 将新位置 i 映射到旧位置——% n 处理回绕
• 验证：n=5，k=2。i=0: idx=(5-2+0)%5=3 → arr[3]=4。i=1: idx=4 → arr[4]=5。i=2: idx=0 → arr[0]=1。正确！

挑战 2.3.12 — 合并有序数组 读取 N₁，然后 N₁ 个已排序的整数；读取 N₂，然后 N₂ 个已排序的整数。打印合并后的有序数组。

样例输入：

3
1 3 5
4
2 4 6 8

样例输出： 1 2 3 4 5 6 8

思路： 双指针——一个指向每个数组的当前位置。每步取两个当前元素中较小的。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n1;
    cin >> n1;
    vector<int> a(n1);
    for (int i = 0; i < n1; i++) cin >> a[i];

    int n2;
    cin >> n2;
    vector<int> b(n2);
    for (int i = 0; i < n2; i++) cin >> b[i];

    // 双指针合并
    int i = 0, j = 0;
    vector<int> result;

    while (i < n1 && j < n2) {
        if (a[i] <= b[j]) {
            result.push_back(a[i++]);  // 取 a，i 前进
        } else {
            result.push_back(b[j++]);  // 取 b，j 前进
        }
    }
    // 某个数组可能还有剩余元素
    while (i < n1) result.push_back(a[i++]);
    while (j < n2) result.push_back(b[j++]);

    for (int idx = 0; idx < (int)result.size(); idx++) {
        cout << result[idx];
        if (idx < (int)result.size() - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

关键点：

• 双指针 i 和 j 同步扫描数组 a 和 b
• 始终取当前较小的元素——维持有序性
• while 循环结束后，某个数组可能还有剩余元素——直接追加

挑战 2.3.13 — 气味距离 （USACO Bronze 风格）

N 头奶牛站成一排，每头奶牛有位置 p[i] 和气味半径 s[i]。如果两头奶牛之间的距离不超过它们半径之和，它们就能互相闻到对方。读取 N，然后 N 对（位置，半径），打印能互相闻到的奶牛对数。

样例输入：

4
1 2
5 1
8 3
15 1

样例输出： 1

（对 (1,2)：距离=|5-8|=3，半径和=1+3=4，3≤4，YES。其余对距离均超过半径和，总计 1。）

思路： 检查所有满足 i < j 的对，对每对计算距离并与半径和比较。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<long long> pos(n), rad(n);
    for (int i = 0; i < n; i++) {
        cin >> pos[i] >> rad[i];
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            long long dist = abs(pos[i] - pos[j]);
            long long sumRad = rad[i] + rad[j];
            if (dist <= sumRad) {
                count++;
            }
        }
    }

    cout << count << "\n";
    return 0;
}

关键点：

• 检查满足 i < j 的对，避免同一对计数两次
• abs(pos[i] - pos[j]) 计算位置间的绝对距离
• 使用 long long 以防位置和半径较大

第 2.4 章：结构体与类

竞赛编程中，你经常需要把相关数据组合在一起——例如，一个点有 x 和 y，一条边有两个端点和权重，一名学生有姓名和成绩。C++ 提供了 struct 和 class 来把数据（和行为）绑定成单一类型。本章涵盖两者，重点关注竞赛编程中最重要的内容。

2.4.1 为什么要把数据组合在一起？

🎒 背包类比

想象你要去旅行。你可以把每件东西分别拿着：
  - 左手：护照
  - 右手：手机
  - 口袋：钱包
  - 嘴里：机票 😬

或者，把所有东西放进一个背包：
  - backpack.passport ✅
  - backpack.phone ✅
  - backpack.wallet ✅
  - backpack.ticket ✅

struct/class 就是那个背包——把相关的东西组合在一个名字下。

没有结构体，如果你想存储 1000 名学生的名字和成绩，需要两个独立的数组：

string names[1000];
int scores[1000];
// 你必须手动保持下标同步——容易出错！

有了结构体，干净而安全：

struct Student {
    string name;
    int score;
};
Student students[1000];  // 每个学生自带名字和成绩

2.4.2 结构体基础

定义结构体

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

struct Point {
    int x;
    int y;
};  // <-- 别忘了分号！

int main() {
    Point p;       // 声明一个 Point 变量
    p.x = 3;       // 用点号（.）访问成员
    p.y = 7;
    cout << "(" << p.x << ", " << p.y << ")" << endl;  // (3, 7)
    return 0;
}

初始化方式

// 方式一：聚合初始化（C++11，竞赛中最常用）
Point p1 = {3, 7};

// 方式二：指定初始化（C++20）
Point p2 = {.x = 3, .y = 7};

// 方式三：逐字段赋值
Point p3;
p3.x = 3;
p3.y = 7;

💡 竞赛技巧： 竞赛编程中，聚合初始化 {val1, val2, ...} 是最常用的风格——输入快，读起来简洁。

带构造函数的结构体

可以定义构造函数让创建实例更简洁：

struct Point {
    int x, y;

    // 构造函数
    Point(int _x, int _y) : x(_x), y(_y) {}
};

int main() {
    Point p(3, 7);  // 调用构造函数
    cout << p.x << " " << p.y << endl;  // 3 7
}

⚠️ 警告： 一旦定义了自定义构造函数，就不能再用 Point p;（无参数）了，除非同时提供默认构造函数或给参数设默认值。

struct Point {
    int x, y;

    Point() : x(0), y(0) {}            // 默认构造函数
    Point(int _x, int _y) : x(_x), y(_y) {}  // 有参构造函数
};

Point p1;       // OK——使用默认构造函数，x=0, y=0
Point p2(3, 7); // OK——使用有参构造函数

2.4.3 结构体在竞赛编程中的应用

存储图论问题中的边

struct Edge {
    int from, to, weight;
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].from >> edges[i].to >> edges[i].weight;
    }
}

自定义比较来排序结构体

这在 USACO 题目中极为常见。你经常需要按某个特定字段排序。

方法一：在结构体内重载 operator<

struct Event {
    int start, end;

    // 按结束时间排序（贪心调度）
    bool operator<(const Event& other) const {
        return end < other.end;
    }
};

int main() {
    vector<Event> events = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 8}, {5, 9}};
    sort(events.begin(), events.end());  // 自动使用 operator<

    for (auto& e : events) {
        cout << "[" << e.start << ", " << e.end << "] ";
    }
}

方法二：lambda 比较器（更灵活）

struct Event {
    int start, end;
};

int main() {
    vector<Event> events = {{1, 4}, {3, 5}, {0, 6}, {5, 7}};

    // 按开始时间排序
    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
        return a.start < b.start;
    });
}

方法三：编写比较函数

bool compareByEnd(const Event& a, const Event& b) {
    return a.end < b.end;
}

sort(events.begin(), events.end(), compareByEnd);

💡 竞赛技巧： 对大多数 USACO 题，方法一（运算符重载）在只有一种自然排序顺序时最简洁。当同一程序需要多种不同排序顺序时，用方法二（lambda）。

多关键字排序

有时需要先按一个字段排序，再用另一个字段打破平局：

struct Student {
    string name;
    int score;

    bool operator<(const Student& other) const {
        if (score != other.score) return score > other.score;  // 高分优先
        return name < other.name;  // 分数相同时按姓名字典序
    }
};

或用 tie() 写法更简洁：

struct Student {
    string name;
    int score;

    bool operator<(const Student& other) const {
        // 按分数降序，再按姓名升序
        return tie(other.score, name) < tie(score, other.name);
    }
};

💡 tie() 技巧： tie() 创建一个元组用于字典序比较。调换元素顺序可反转该字段的排序方向。这是竞赛编程中非常常见的技巧。

在集合和映射中使用结构体

如果想把结构体作为 set 或 map 的键，必须定义 operator<：

struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        return tie(x, y) < tie(other.x, other.y);
    }
};

set<Point> visited;
visited.insert({1, 2});
visited.insert({3, 4});

if (visited.count({1, 2})) {
    cout << "已访问过！" << endl;
}

在优先队列中使用结构体

struct State {
    int dist, node;

    // 最小堆：希望 dist 最小的在顶部
    // priority_queue 默认是最大堆，所以反转比较
    bool operator>(const State& other) const {
        return dist > other.dist;
    }
};

// 用 operator> 实现最小堆
priority_queue<State, vector<State>, greater<State>> pq;
pq.push({0, 1});   // 距离 0，节点 1
pq.push({5, 2});   // 距离 5，节点 2

auto top = pq.top();  // {0, 1}——距离最小

2.4.4 struct vs class——有什么区别？

实际情况是：struct 和 class 在 C++ 中几乎完全相同。唯一区别是默认访问级别：

// 这两个功能上完全相同：

struct PointS {
    int x, y;  // 默认 public
};

class PointC {
public:          // 必须显式声明为 public
    int x, y;
};

什么时候用哪个？

💡 竞赛惯例： 竞赛编程中，始终用 struct。它更简单、更简短，而且几乎从不需要私有成员。几乎每个竞赛选手的代码里都是 struct。

2.4.5 类——完整视角

尽管 struct 足以应付竞赛编程，理解 class 对更广泛的 C++ 知识很有价值。

访问修饰符

class BankAccount {
private:    // 只能在类内部访问
    double balance;

public:     // 可以从任何地方访问
    BankAccount(double initial) : balance(initial) {}

    void deposit(double amount) {
        if (amount > 0) {
            balance += amount;
        }
    }

    void withdraw(double amount) {
        if (amount > 0 && amount <= balance) {
            balance -= amount;
        }
    }

    double getBalance() const {
        return balance;
    }
};

int main() {
    BankAccount acc(100.0);
    acc.deposit(50.0);
    acc.withdraw(30.0);
    cout << acc.getBalance() << endl;  // 120.0

    // acc.balance = 999999;  // 错误！balance 是私有的
}

为什么需要封装？

想象一台自动贩卖机：

- 公共接口：投币、按按钮、取饮料
- 私有内部：硬币计数器、库存、温控系统

你通过公共按钮与机器交互。
你不能直接伸手取饮料。

封装保护数据不被滥用。

竞赛编程中不需要这种级别的保护——代码速度更重要。但在软件工程中，它能防止大型代码库中的 bug。

成员函数（方法）

struct 和 class 都可以有成员函数：

struct Rect {
    int width, height;

    int area() const {
        return width * height;
    }

    int perimeter() const {
        return 2 * (width + height);
    }

    bool contains(int x, int y) const {
        return x >= 0 && x < width && y >= 0 && y < height;
    }
};

int main() {
    Rect r = {10, 5};
    cout << "面积：" << r.area() << endl;      // 50
    cout << "周长：" << r.perimeter() << endl;  // 30
    cout << r.contains(3, 4) << endl;            // 1（true）
}

💡 方法名后的 const： 方法名后的 const 关键字表示「这个方法不修改对象」。如果方法只读取数据，始终标记为 const——这是良好实践，在使用 const 引用时也是必须的。

2.4.6 竞赛编程中的进阶结构体模式

pair——内置的「两字段结构体」

C++ 提供了 pair 作为只需要两个字段时的轻量替代：

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

int main() {
    pair<int, int> p = {3, 7};
    cout << p.first << " " << p.second << endl;  // 3 7

    // pair 有内置比较（字典序）
    vector<pair<int, int>> v = {{3, 1}, {1, 5}, {3, 0}, {1, 2}};
    sort(v.begin(), v.end());
    // 结果：{1, 2}, {1, 5}, {3, 0}, {3, 1}

    // 可以用 make_pair 或直接用花括号
    auto q = make_pair(10, 20);
}

什么时候用 pair vs 自定义 struct：

tuple——内置的「N 字段结构体」

tuple<int, string, double> t = {42, "Alice", 3.14};
cout << get<0>(t) << endl;  // 42
cout << get<1>(t) << endl;  // Alice

// 结构化绑定（C++17）——更简洁
auto [id, name, gpa] = t;
cout << name << " 的 GPA 是 " << gpa << endl;

💡 竞赛技巧： 超过 2 个字段时，带名称的 struct 几乎总是比 tuple 更易读。pair 可以随意用，但能用 struct 时就别用 tuple。

含 array 或 vector 成员的结构体

struct Graph {
    int n;
    vector<vector<int>> adj;

    Graph(int _n) : n(_n), adj(_n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(1, 2);

    for (int v : g.adj[1]) {
        cout << v << " ";  // 0 2
    }
}

2.4.7 常见错误

❌ 错误一：忘记 } 后的分号

struct Point {
    int x, y;
}   // ← 缺少分号！

int main() { ... }
// 编译器给出令人困惑的错误，指向 main()

修复： 结构体/类定义的右花括号后始终加 ;。

❌ 错误二：运算符重载中忘记 const

struct Point {
    int x, y;
    // 错误——缺少 const
    bool operator<(const Point& other) {  // ← 在某些 STL 容器中无法工作
        return tie(x, y) < tie(other.x, other.y);
    }
};

修复： 比较运算符始终标记为 const：

bool operator<(const Point& other) const {  // ✅
    return tie(x, y) < tie(other.x, other.y);
}

❌ 错误三：使用未初始化的结构体成员

struct State {
    int dist, node;
};

State s;
cout << s.dist;  // 未定义行为！可能是任意值

修复： 始终初始化，或提供默认值：

struct State {
    int dist = 0;
    int node = 0;
};

❌ 错误四：优先队列中 operator< 方向搞反

struct State {
    int dist;
    // 想实现最小堆，你可能会这样写：
    bool operator<(const State& other) const {
        return dist < other.dist;  // 这会得到最大堆！（与你想要的相反）
    }
};

修复： 对 priority_queue 实现最小堆，要么反转比较，要么用 greater<>：

// 方案 A：反转 operator<
bool operator<(const State& other) const {
    return dist > other.dist;  // dist 更大的优先级更低 → 最小堆
}
priority_queue<State> pq;

// 方案 B：定义 operator> 并使用 greater<>
bool operator>(const State& other) const {
    return dist > other.dist;
}
priority_queue<State, vector<State>, greater<State>> pq;

2.4.8 练习题

🟢 题目一：学生排名

读取 n 名学生（姓名和成绩），按成绩降序排序，打印排名。

数据规模： 1 ≤ n ≤ 10⁵，姓名长度 ≤ 20，0 ≤ 成绩 ≤ 100。

输入：
3
Alice 85
Bob 92
Charlie 85

输出：
1. Bob 92
2. Alice 85
3. Charlie 85

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

struct Student {
    string name;
    int score;

    bool operator<(const Student& other) const {
        if (score != other.score) return score > other.score;
        return name < other.name;
    }
};

int main() {
    int n;
    cin >> n;
    vector<Student> students(n);
    for (int i = 0; i < n; i++) {
        cin >> students[i].name >> students[i].score;
    }
    sort(students.begin(), students.end());
    for (int i = 0; i < n; i++) {
        cout << i + 1 << ". " << students[i].name << " " << students[i].score << "\n";
    }
}

🟢 题目二：最近点对（一维）

给定数轴上 n 个点，找距离最小的点对。

数据规模： 2 ≤ n ≤ 10⁵，坐标为不超过 10⁹ 绝对值的整数。

输入：
5
7 1 4 9 2

输出：
1
（点 1 和点 2 之间）

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

struct PointVal {
    int val, originalIndex;

    bool operator<(const PointVal& other) const {
        return val < other.val;
    }
};

int main() {
    int n;
    cin >> n;
    vector<PointVal> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].val;
        points[i].originalIndex = i;
    }
    sort(points.begin(), points.end());

    int minDist = INT_MAX;
    int bestI = 0, bestJ = 1;
    for (int i = 0; i + 1 < n; i++) {
        int d = points[i + 1].val - points[i].val;
        if (d < minDist) {
            minDist = d;
            bestI = i;
            bestJ = i + 1;
        }
    }
    cout << minDist << "\n";
    cout << "（点 " << points[bestI].val << " 和点 " << points[bestJ].val << " 之间）\n";
}

🟡 题目三：区间调度（贪心）

给定 n 个区间 [start, end]，找不重叠区间的最大数量。

数据规模： 1 ≤ n ≤ 10⁵，0 ≤ start ≤ end ≤ 10⁹。

输入：
6
1 4
3 5
0 6
5 7
3 8
5 9

输出：
3

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

struct Interval {
    int start, end;

    bool operator<(const Interval& other) const {
        return end < other.end;
    }
};

int main() {
    int n;
    cin >> n;
    vector<Interval> intervals(n);
    for (int i = 0; i < n; i++) {
        cin >> intervals[i].start >> intervals[i].end;
    }
    sort(intervals.begin(), intervals.end());

    int count = 0, lastEnd = -1;
    for (auto& it : intervals) {
        if (it.start >= lastEnd) {
            count++;
            lastEnd = it.end;
        }
    }
    cout << count << "\n";
}

📋 本章总结

🎯 竞赛编程核心要点

1. 竞赛中始终用 struct —— 更简单、更简短
2. 掌握 operator< 重载 —— 几乎每道 USACO 题都会用到
3. 多关键字排序用 tie() —— 简洁且不易出错
4. 记得 const —— STL 兼容性的要求
5. 初始化你的成员 —— 避免未定义行为
6. 2 个字段用 pair，3 个及以上用自定义 struct —— 好的经验法则

📖 第 2.5 章：分类讨论与矩形几何

2.5.0 从一道题出发：贴错的告示牌

先看一道 USACO 2021 Dec Bronze「Air Cownditioning」风格的入门真题——矩形版的它几乎年年出现：

📋 题目：告示牌（Billboard） 农夫 John 在墙上贴了两块矩形告示牌，给出两块的左下角和右上角坐标。 谷仓门也在一块矩形区域内。问：两块告示牌被门挡住之后，还剩多少可见面积？ 数据范围： 所有坐标为整数，0 ≤ x, y ≤ 1000，且每个矩形满足 x1 < x2、y1 < y2。 （USACO 2018 Feb Bronze P2 原题就是三块矩形互相遮挡的版本。）

牌1: (1,2)–(6,14)   牌2: (11,2)–(16,14)   门: (7,2)–(13,10)

先试试你会的方法

思路 1：面积相加减？ 总可见 = 牌1面积 + 牌2面积 − 被挡部分。但「牌1被门挡了多少」——两个矩形的遮挡关系有好几种：完全不相交、擦个边角、部分重叠、完全盖住……直接凭感觉写 if，十有八九漏掉「刚好贴边」的情况。

思路 2：逐格判断？ 坐标范围如果是 10⁹，不能开数组也不能逐点扫。

关键观察： 「牌和门的相对位置」看似有无穷种，其实每一种都能用 min/max 统一表达：

• 交集的左边界 = 两矩形左边界的较大者 max(l1, l2)
• 交集的右边界 = 两矩形右边界的较小者 min(r1, r2)
• 若 右边界 ≤ 左边界，交集为空——「不相交」这种情形被一个 if 自然覆盖！

这就是本章两大主题的缩影：

1. 分类讨论：像「牌和门怎么重叠」这种多情形问题，先画图列全所有情形，再写代码——不遗漏、不重复；
2. 矩形几何：相交、覆盖、面积，全部归结为 min/max 与乘法。

拆解这道题需要回答的问题

学习目标（学完本章你将能够）：

1. 识别需要分类讨论的题目，系统枚举所有情形
2. 用「先画图、再列边界、最后写代码」的方法避免漏情况
3. 处理坐标轴上的矩形交叉、覆盖、面积问题
4. 判断两个矩形是否相交，计算交集面积
5. 用差分思想处理网格上的矩形覆盖计数
6. 读懂并实现 USACO Bronze 中常见的矩形覆盖题

2.5.1 分类讨论（Casework）

什么是分类讨论？

当问题的答案取决于若干个「互斥情形」时，需要逐一枚举每种情形，分别处理。

举几个简单例子：

• 一个数是正数、负数还是零？
• 两个区间是不相交、刚好相接，还是有重叠？
• 一个点在矩形内部、边界上，还是外部？
• 一个矩形是否被另一个矩形挡住了一部分？

这些问题都有一个共同点：不能只写一个公式就结束，而是要先判断当前输入属于哪一种情况。

核心原则：

1. 完备性：不遗漏任何情形。
2. 互斥性：不同情形之间最好不要重叠；如果会重叠，要明确优先级。
3. 边界验证：特别检查 等于、刚好接触、刚好覆盖 这些边界值。

分类讨论的通用步骤

做分类讨论题时，可以按照下面四步来：

1. 画图：把题目中的对象画出来，比如区间、矩形、运动方向。
2. 找边界：思考什么时候答案会发生变化，例如两个区间端点相等时。
3. 列情况：把所有可能情况列出来，尽量保证没有遗漏。
4. 写条件：把每种情况翻译成 C++ 的 if / else if / else。

例如：

if (第一种情况) {
    // 处理第一种情况
} else if (第二种情况) {
    // 处理第二种情况
} else {
    // 剩余情况
}

这里最后的 else 很重要，它经常用于兜底：当前面所有明确列出的情况都不满足时，就进入最后一种情况。

示例：一维区间分类

题目描述：

给定两个闭区间 [a, b] 和 [c, d]，其中 a <= b，c <= d。请判断这两个区间的关系：

1. 完全不相交：两个区间之间有空隙。
2. 仅端点相接：两个区间只有一个端点相同，没有长度上的重叠。
3. 一个包含另一个：其中一个区间完全覆盖另一个区间。
4. 部分重叠：两个区间有公共部分，但谁也没有完全包含谁。

先不要急着写代码，可以先画图：

接下来把图翻译成条件。

关键边界：< 和 == 的区别

• 如果 b < c，说明 [a,b] 在 [c,d] 左边，并且中间有空隙。
• 如果 b == c，说明两个区间只在一个点相接。
• 如果 b > c，说明它们至少在横轴上有重叠或包含关系。

因此，在分类时，通常要先处理更特殊的情况，比如「完全不相交」和「端点相接」。

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

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;  // 区间 [a,b] 和 [c,d]

    // 如果输入不保证左端点 <= 右端点，可以先修正
    if (a > b) swap(a, b);
    if (c > d) swap(c, d);

    if (b < c || d < a) {
        cout << "完全不相交\n";
    } else if (b == c || d == a) {
        cout << "仅端点相接\n";
    } else if (a <= c && d <= b) {
        cout << "[c,d] 在 [a,b] 内部（或相等）\n";
    } else if (c <= a && b <= d) {
        cout << "[a,b] 在 [c,d] 内部（或相等）\n";
    } else {
        cout << "部分重叠\n";
    }
    return 0;
}

初学者常见疑问：为什么顺序很重要？

在 if / else if 中，程序会从上到下检查条件，遇到第一个满足的条件就执行，不会再继续检查后面的条件。

例如两个区间 [1, 5] 和 [1, 5]：

• 它既满足 [c,d] 在 [a,b] 内部。
• 也满足 [a,b] 在 [c,d] 内部。

这种情况并不是错误，而是说明两个区间相等。我们只要在题目要求的分类里确定一个输出即可。

💡 如果题目对「完全相等」有单独要求，就应该在包含判断之前先写 if (a == c && b == d)。

分类讨论的技巧

技巧 1：排序后减少情形数

对输入排序，可以将多种对称情形合并：

// 例：确保 a <= b（避免分别处理 a<b 和 a>b 两种情形）
if (a > b) swap(a, b);

技巧 2：用 min/max 简化区间操作

如果只关心两个区间的重叠长度，可以不必列出所有关系，而是直接算交集。

// 两区间 [a,b] 和 [c,d] 的交集长度
long long overlap = max(0LL, min(b, d) - max(a, c));

这个公式的含义是：

• 交集左端点是两个左端点中较大的那个：max(a, c)。
• 交集右端点是两个右端点中较小的那个：min(b, d)。
• 如果右端点小于等于左端点，说明没有正长度重叠。

注意：上面公式适合把区间看成 [a,b) 和 [c,d) 这种「左闭右开」长度模型。若是闭区间并且要统计整数点个数，公式会略有不同。

技巧 3：画图 + 列举边界

分类讨论题必须动手画图，列出所有边界情况逐一验证。至少要检查：

• 完全分离
• 刚好相接
• 部分重叠
• 一个完全包含另一个
• 两者完全相等

技巧 4：优先写「容易判断的反面」

有些题目直接判断「相交」比较麻烦，但判断「不相交」很简单。

例如两个区间不相交只有两种情况：

b <= c || d <= a

那么相交就是它的反面：

!(b <= c || d <= a)

矩形相交也会用到同样的思想。

USACO Bronze 典型：方向判断

题目描述（USACO 风格）：

一头奶牛站在二维平面上，初始位置是 (0, 0)，初始方向朝北。接下来会给出 N 条指令，每条指令可能是下面三种之一：

1. left：原地向左转 90 度。
2. right：原地向右转 90 度。
3. forward D：沿当前朝向前进 D 步。

请输出执行完所有指令后，奶牛的最终坐标。

这个题看起来像模拟题，但本质上也需要分类讨论：

• 当前方向是北、东、南、西中的哪一个？
• 当前指令是左转、右转，还是前进？
• 如果前进，不同方向对应的 x、y 变化不同。

朴素写法：直接分类讨论

最直观的写法是：

if (dir == "N") y += d;
else if (dir == "S") y -= d;
else if (dir == "E") x += d;
else if (dir == "W") x -= d;

这种写法容易理解，但如果转向逻辑也都用字符串分类，代码会比较长。

更简洁的写法：方向编号

我们可以把四个方向按顺时针编号：

0: North
1: East
2: South
3: West

这样右转就是编号 +1，左转就是编号 -1。为了避免出现负数，可以写成：

// 左转：dir - 1
// 加 4 是为了避免负数，再对 4 取模
(dir + 3) % 4

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

int main() {
    // 方向编码：0=N, 1=E, 2=S, 3=W
    // dx/dy 对应四个方向的位移
    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};
    
    int x = 0, y = 0, dir = 0;  // 初始位置和方向
    int n; cin >> n;
    
    while (n--) {
        string cmd; cin >> cmd;
        if (cmd == "left") {
            dir = (dir + 3) % 4;   // 左转 = (dir-1+4)%4
        } else if (cmd == "right") {
            dir = (dir + 1) % 4;   // 右转
        } else {
            int d; cin >> d;
            x += dx[dir] * d;
            y += dy[dir] * d;
        }
    }
    
    cout << x << " " << y << "\n";
    return 0;
}

2.5.2 矩形几何

坐标系中的矩形表示

竞赛中的矩形通常是轴对齐矩形，也就是矩形的边和坐标轴平行。它一般用两个对角顶点表示：

• 左下角：(x1, y1)
• 右上角：(x2, y2)

通常满足：

x1 < x2, y1 < y2

画出来是这样：

y
↑
y2 +----------+
   |          |
y1 +----------+→ x
   x1        x2

如果题目没有保证 x1 < x2、y1 < y2，读入后要先修正：

if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);

面积为什么是 (x2 - x1) * (y2 - y1)？

矩形的宽度是横坐标差：

width = x2 - x1

矩形的高度是纵坐标差：

height = y2 - y1

所以面积是：

area = (x2 - x1) * (y2 - y1)

例如矩形 (1, 2) 到 (4, 6)：

• 宽度：4 - 1 = 3
• 高度：6 - 2 = 4
• 面积：3 * 4 = 12

一个重要习惯：把矩形看成半开区间

在很多竞赛题里，矩形 (x1, y1, x2, y2) 表示：

x1 <= x < x2
y1 <= y < y2

也就是左边界和下边界算进去，右边界和上边界不算进去。这样做的好处是：

• 面积正好是 (x2 - x1) * (y2 - y1)。
• 两个矩形只在边界接触时，交集面积是 0。
• 用差分数组统计格子时更方便。

例如矩形 (0,0)-(2,2) 覆盖的是下面 4 个 1×1 小格子：

(0,1) (1,1)
(0,0) (1,0)

它的面积是 2 * 2 = 4。

两矩形是否相交

关键规则： 两矩形不相交，当且仅当一个矩形完全在另一个的左边、右边、下边或上边。

也就是说，如果出现下面任意一种情况，它们就没有正面积交集：

1. A 在 B 的左边：ax2 <= bx1
2. B 在 A 的左边：bx2 <= ax1
3. A 在 B 的下边：ay2 <= by1
4. B 在 A 的下边：by2 <= ay1

用图理解其中一种：

A 在 B 左边：

A             B
+---+         +---+
|   |         |   |
+---+         +---+
ax2 <= bx1

所以判断相交时，可以先判断「不相交」，再取反。

// 矩形 A: (ax1,ay1)-(ax2,ay2)
// 矩形 B: (bx1,by1)-(bx2,by2)
bool intersects(long long ax1, long long ay1, long long ax2, long long ay2,
                long long bx1, long long by1, long long bx2, long long by2) {
    // A 完全在 B 左边 or 右边 or 下边 or 上边
    if (ax2 <= bx1 || bx2 <= ax1 || ay2 <= by1 || by2 <= ay1)
        return false;
    return true;
}

💡 这里使用 <=，表示两个矩形如果只是边贴边，没有面积重叠，就不算相交。

交集面积

计算两个矩形的交集，可以把问题拆成两个一维问题：

• x 方向的重叠长度
• y 方向的重叠长度

交集矩形的左下角和右上角分别是：

交集左下角：max(两个左边界), max(两个下边界)
交集右上角：min(两个右边界), min(两个上边界)

对应到代码就是：

long long intersection_area(long long ax1, long long ay1, long long ax2, long long ay2,
                            long long bx1, long long by1, long long bx2, long long by2) {
    long long ix1 = max(ax1, bx1);
    long long iy1 = max(ay1, by1);
    long long ix2 = min(ax2, bx2);
    long long iy2 = min(ay2, by2);

    if (ix2 <= ix1 || iy2 <= iy1) return 0;  // 不相交，或只是边界相接
    return (ix2 - ix1) * (iy2 - iy1);
}

逐步追踪示例：

矩形 A: (1,1)-(4,4)
矩形 B: (2,2)-(6,5)

第 1 步：求交集左下角
x = max(1,2) = 2
y = max(1,2) = 2
所以左下角是 (2,2)

第 2 步：求交集右上角
x = min(4,6) = 4
y = min(4,5) = 4
所以右上角是 (4,4)

第 3 步：求面积
宽 = 4 - 2 = 2
高 = 4 - 2 = 2
面积 = 2 * 2 = 4

再看一个没有面积重叠的例子：

矩形 A: (0,0)-(2,2)
矩形 B: (2,0)-(4,2)

它们只是边界接触。
交集宽度 = min(2,4) - max(0,2) = 2 - 2 = 0
所以交集面积是 0。

两矩形的并集面积

两个矩形的并集面积，指的是至少被其中一个矩形覆盖的面积。

如果直接写：

并集面积 = A 的面积 + B 的面积

会出现一个问题：重叠部分被算了两次。

所以要把重叠部分减掉一次：

并集面积 = A 的面积 + B 的面积 - A 与 B 的交集面积

这就是最简单的容斥思想。

long long union_area(long long ax1, long long ay1, long long ax2, long long ay2,
                     long long bx1, long long by1, long long bx2, long long by2) {
    long long areaA = (ax2 - ax1) * (ay2 - ay1);
    long long areaB = (bx2 - bx1) * (by2 - by1);
    long long inter = intersection_area(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2);
    return areaA + areaB - inter;
}

举例：

矩形 A 面积 = 12
矩形 B 面积 = 10
重叠面积 = 4

如果直接相加：12 + 10 = 22，重叠部分多算了一次。
正确答案：12 + 10 - 4 = 18

💡 对两个矩形求并集面积时，这个公式很好用；但如果是三个或更多矩形，重叠关系会更复杂，通常要用扫描线、差分数组或更系统的容斥方法。

矩形内点的判断

判断一个点和矩形的关系时，要先看题目要求：

• 如果题目问点是否在矩形「内部或边界上」，使用 <=。
• 如果题目只问点是否在严格内部，使用 <。
• 如果题目要把边界单独分类，就要分别判断「边界」和「内部」。

bool point_in_rect(long long px, long long py,
                   long long x1, long long y1, long long x2, long long y2) {
    return x1 <= px && px <= x2 && y1 <= py && py <= y2;
}

例如矩形 (0,0)-(3,2)：

• 点 (1,1) 在内部。
• 点 (0,1) 在左边界上。
• 点 (3,2) 在右上角边界上。
• 点 (4,1) 在外部。

进阶：N 个矩形的覆盖面积（差分法）

当有大量矩形叠加时，如果逐个格子暴力标记，有时会比较慢；如果坐标范围不大，可以用二维差分数组统计每个格子被覆盖的次数。

先理解一维差分

假设有一个数组，我们想让区间 [l, r) 全部加 1，可以这样做：

diff[l]++;
diff[r]--;

最后从左到右做前缀和，就能知道每个位置被加了多少次。

二维差分是同样的思想，只是从「线段」变成「矩形」。

二维差分如何给矩形加 1？

如果要给矩形 [x1, x2) × [y1, y2) 覆盖区域加 1，做四个角的修改：

diff[y1][x1]++;
diff[y1][x2]--;
diff[y2][x1]--;
diff[y2][x2]++;

可以把它理解为：

• 从左下角开始加上影响。
• 到右边界之后取消影响。
• 到上边界之后取消影响。
• 右上角被取消了两次，所以要补回来一次。

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

const int MAX_COORD = 1000;                 // 坐标范围假设为 0~1000
int diff[MAX_COORD + 2][MAX_COORD + 2];     // 多开空间，方便处理 x2/y2

// 给矩形 [x1,x2) × [y1,y2) 覆盖区域 +1
void add_rect(int x1, int y1, int x2, int y2) {
    diff[y1][x1]++;
    diff[y1][x2]--;
    diff[y2][x1]--;
    diff[y2][x2]++;
}

int main() {
    int n;
    cin >> n;

    while (n--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        add_rect(x1, y1, x2, y2);
    }

    // 二维前缀和还原每个格子的覆盖次数
    for (int y = 0; y <= MAX_COORD; y++) {
        for (int x = 0; x <= MAX_COORD; x++) {
            if (y > 0) diff[y][x] += diff[y - 1][x];
            if (x > 0) diff[y][x] += diff[y][x - 1];
            if (y > 0 && x > 0) diff[y][x] -= diff[y - 1][x - 1];
        }
    }

    // 统计被至少一个矩形覆盖的 1×1 格子
    // 左下角最大只能到 (999,999)，因为格子 [999,1000) 才是最后一格
    long long covered = 0;
    for (int y = 0; y < MAX_COORD; y++) {
        for (int x = 0; x < MAX_COORD; x++) {
            if (diff[y][x] > 0) covered++;
        }
    }

    cout << covered << "\n";
    return 0;
}

为什么统计的是格子，不是点？

坐标范围是 0~1000 时，格子通常是：

横坐标区间：[0,1), [1,2), ..., [999,1000)
纵坐标区间：[0,1), [1,2), ..., [999,1000)

所以共有 1000 × 1000 个 1×1 格子。数组下标 diff[y][x] 可以理解为左下角是 (x,y) 的那个小格子的覆盖次数。

⚠️ 常见错误

调试建议

写完矩形题后，可以自己构造下面几组数据检查：

1. 完全不相交：答案应该是 0。
2. 刚好边界相接：交集面积也应该是 0。
3. 一个矩形完全包含另一个矩形：交集面积应该等于小矩形面积。
4. 两个矩形完全相同：交集面积应该等于任意一个矩形的面积。
5. 只有部分重叠：手算一次宽度、高度，再和程序输出对比。

本章小结

本章最重要的思想可以总结为三句话：

1. 分类讨论先画图：不要凭感觉写条件，先把所有情况画出来。
2. 矩形问题拆成两个方向：分别处理 x 方向和 y 方向，再把结果合起来。
3. 覆盖问题优先想差分：当矩形很多、坐标范围不大时，二维差分比逐块暴力更清晰。

常用公式：

// 矩形面积
area = (x2 - x1) * (y2 - y1);

// 两矩形交集边界
ix1 = max(ax1, bx1);
iy1 = max(ay1, by1);
ix2 = min(ax2, bx2);
iy2 = min(ay2, by2);

// 两矩形交集面积
intersection = max(0LL, ix2 - ix1) * max(0LL, iy2 - iy1);

💪 练习题

🟢 题目 1：矩形相交判断

题目描述：

给定两个轴对齐矩形 A 和 B。每个矩形用四个整数表示：

x1 y1 x2 y2

其中 (x1, y1) 是矩形左下角，(x2, y2) 是矩形右上角，并且 x1 < x2、y1 < y2。

数据范围： -10⁹ ≤ x, y ≤ 10⁹（坐标绝对值可达 10⁹，交集面积需用 long long）。

请判断两个矩形是否存在正面积交集：

• 如果存在，输出交集面积。
• 如果不存在，输出 0。

注意：如果两个矩形只是边界相接，例如一个矩形的右边界等于另一个矩形的左边界，那么交集面积为 0。

输入格式：

ax1 ay1 ax2 ay2
bx1 by1 bx2 by2

输出格式：

一个整数，表示两个矩形的交集面积

样例输入：

1 1 4 4
2 2 6 5

样例输出：

4

样例解释：

两个矩形的交集是 (2,2)-(4,4)，宽度为 2，高度为 2，面积为 4。

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

int main() {
    long long ax1, ay1, ax2, ay2;
    long long bx1, by1, bx2, by2;
    cin >> ax1 >> ay1 >> ax2 >> ay2;
    cin >> bx1 >> by1 >> bx2 >> by2;

    long long ix1 = max(ax1, bx1);
    long long iy1 = max(ay1, by1);
    long long ix2 = min(ax2, bx2);
    long long iy2 = min(ay2, by2);

    if (ix2 <= ix1 || iy2 <= iy1) {
        cout << 0 << "\n";
    } else {
        cout << (ix2 - ix1) * (iy2 - iy1) << "\n";
    }

    return 0;
}

🟡 题目 2：奶牛放牧区域（USACO Bronze 风格）

题目描述：

农夫 John 有 N 块矩形牧场。每块牧场的边都与坐标轴平行，且坐标都是 0~1000 之间的整数。

数据范围： 1 ≤ N ≤ 1000，0 ≤ x1 < x2 ≤ 1000，0 ≤ y1 < y2 ≤ 1000。

每块牧场用左下角 (x1, y1) 和右上角 (x2, y2) 表示。它覆盖所有满足下面条件的 1×1 小格子：

x1 <= x < x2
y1 <= y < y2

如果多块牧场重叠，重叠部分只计算一次。请你求出被至少一块牧场覆盖的总格数，也就是覆盖总面积。

输入格式：

N
x1 y1 x2 y2
x1 y1 x2 y2
...

输出格式：

一个整数，表示被覆盖的 1×1 格子数量

样例输入：

3
0 0 2 2
1 1 3 3
4 4 5 5

样例输出：

8

样例解释：

• 第一块牧场面积是 4。
• 第二块牧场面积是 4。
• 它们重叠了 1 个格子。
• 第三块牧场面积是 1。
• 总覆盖面积是 4 + 4 - 1 + 1 = 8。

思路： 用差分数组标记每个 1×1 格子被覆盖的次数，最后统计覆盖次数 >= 1 的格子数。

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

int diff[1002][1002];

int main() {
    int n;
    cin >> n;

    while (n--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        // 给矩形 [x1,x2) × [y1,y2) 加 1
        diff[y1][x1]++;
        diff[y1][x2]--;
        diff[y2][x1]--;
        diff[y2][x2]++;
    }

    long long ans = 0;
    for (int y = 0; y <= 1000; y++) {
        for (int x = 0; x <= 1000; x++) {
            if (y > 0) diff[y][x] += diff[y - 1][x];
            if (x > 0) diff[y][x] += diff[y][x - 1];
            if (y > 0 && x > 0) diff[y][x] -= diff[y - 1][x - 1];

            // 只统计左下角为 (x,y) 的 1×1 格子，最大到 (999,999)
            if (x < 1000 && y < 1000 && diff[y][x] > 0) ans++;
        }
    }

    cout << ans << "\n";
    return 0;
}

🔴 题目 3：矩形分类问题（综合）

题目描述：

给定一个轴对齐矩形和 N 个点。请判断每个点与矩形的关系：

1. 如果点在矩形四条边上，输出 边界。
2. 如果点在矩形内部，但不在边界上，输出 内部。
3. 如果点不在矩形内部，也不在边界上，输出 外部。

矩形由左下角 (x1, y1) 和右上角 (x2, y2) 给出，保证 x1 < x2、y1 < y2。

数据范围： -10⁹ ≤ 矩形坐标 ≤ 10⁹，1 ≤ N ≤ 10⁵，-10⁹ ≤ px, py ≤ 10⁹。

输入格式：

x1 y1 x2 y2
N
px py
px py
...

输出格式：

对每个点输出一行：边界、内部 或 外部。

样例输入：

0 0 4 3
5
1 1
0 2
4 3
5 1
2 3

样例输出：

内部
边界
边界
外部
边界

样例解释：

• (1,1) 的横纵坐标都严格在矩形范围内，所以是内部。
• (0,2) 在左边界上。
• (4,3) 是右上角顶点，属于边界。
• (5,1) 在矩形外部。
• (2,3) 在上边界上。

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

int main() {
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int n;
    cin >> n;

    while (n--) {
        long long px, py;
        cin >> px >> py;

        bool on_vertical_edge = (px == x1 || px == x2) && (y1 <= py && py <= y2);
        bool on_horizontal_edge = (py == y1 || py == y2) && (x1 <= px && px <= x2);
        bool on_edge = on_vertical_edge || on_horizontal_edge;

        bool inside = x1 < px && px < x2 && y1 < py && py < y2;

        if (on_edge) cout << "边界\n";
        else if (inside) cout << "内部\n";
        else cout << "外部\n";
    }

    return 0;
}

🔴 题目 4：USACO Bronze — 遮挡广告牌

题目描述：

一面墙上贴了两块广告牌，随后一辆卡车停在墙前，挡住了其中一部分区域。广告牌和卡车在墙上的投影都可以看作轴对齐矩形。

现在给出：

1. 第一块广告牌的矩形坐标。
2. 第二块广告牌的矩形坐标。
3. 卡车遮挡区域的矩形坐标。

请计算两块广告牌仍然可见的总面积。

注意：

• 两块广告牌之间不会相互遮挡。
• 卡车可能不遮挡某块广告牌。
• 卡车可能只遮挡广告牌的一部分。
• 卡车也可能完全遮挡某块广告牌。
• 如果卡车只和广告牌边界接触，不会减少可见面积。

数据范围（与 USACO 2018 Feb Bronze 原题一致）： 所有坐标为整数，0 ≤ x, y ≤ 1000，且每个矩形满足 x1 < x2、y1 < y2。

输入格式：

三行，每行 4 个整数：

x1 y1 x2 y2
x1 y1 x2 y2
x1 y1 x2 y2

分别表示广告牌 1、广告牌 2、卡车遮挡区域。每个矩形都由左下角和右上角表示。

输出格式：

一个整数，表示两块广告牌仍然可见的总面积

样例输入：

1 2 3 5
6 0 10 4
2 1 8 3

样例输出：

17

样例解释：

广告牌 1 的面积是 (3 - 1) * (5 - 2) = 6。卡车与广告牌 1 的交集是 (2,2)-(3,3)，面积是 1，所以广告牌 1 可见面积是 5。

广告牌 2 的面积是 (10 - 6) * (4 - 0) = 16。卡车与广告牌 2 的交集是 (6,1)-(8,3)，面积是 4，所以广告牌 2 可见面积是 12。

总可见面积是 5 + 12 = 17。

核心思路： 分类讨论 + 容斥。总面积 = 广告牌1面积 + 广告牌2面积 - 广告牌1被卡车遮挡面积 - 广告牌2被卡车遮挡面积。每块广告牌与卡车的遮挡面积用矩形交集公式计算。

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

// 计算两个矩形的交集面积
ll inter_area(ll ax1, ll ay1, ll ax2, ll ay2,
              ll bx1, ll by1, ll bx2, ll by2) {
    ll ix1 = max(ax1, bx1), iy1 = max(ay1, by1);
    ll ix2 = min(ax2, bx2), iy2 = min(ay2, by2);
    if (ix2 <= ix1 || iy2 <= iy1) return 0;
    return (ix2 - ix1) * (iy2 - iy1);
}

int main() {
    ll a1x1, a1y1, a1x2, a1y2;  // 广告牌1
    ll a2x1, a2y1, a2x2, a2y2;  // 广告牌2
    ll tx1, ty1, tx2, ty2;       // 卡车
    cin >> a1x1 >> a1y1 >> a1x2 >> a1y2;
    cin >> a2x1 >> a2y1 >> a2x2 >> a2y2;
    cin >> tx1 >> ty1 >> tx2 >> ty2;

    ll area1 = (a1x2 - a1x1) * (a1y2 - a1y1);
    ll area2 = (a2x2 - a2x1) * (a2y2 - a2y1);
    ll covered1 = inter_area(a1x1, a1y1, a1x2, a1y2, tx1, ty1, tx2, ty2);
    ll covered2 = inter_area(a2x1, a2y1, a2x2, a2y2, tx1, ty1, tx2, ty2);

    cout << area1 + area2 - covered1 - covered2 << "\n";
    return 0;
}

复杂度分析： 时间 O(1)，空间 O(1)。只需计算几个矩形的面积和交集，常数时间完成。

💡 章节联系： 矩形几何是 USACO Bronze 的高频题型之一（约占 15%），常与前缀和（差分数组）结合。掌握后可直接用于解决「覆盖面积」「重叠判断」等问题。

📖 第 2.6 章：位运算

🎯 学习目标

学完本章后，你将能够：

1. 看懂一个整数的二进制表示，并知道每一位像一个「开关」
2. 使用六种位运算符进行高效整数操作
3. 用位运算检查、设置、清除、翻转二进制位
4. 用整数作为「集合」（状压表示）进行集合运算
5. 枚举一个整数所有子集（状压 DP 基础）
6. 理解常见的位运算技巧（lowbit、快速判断 2 的幂等）

2.6.1 为什么要学位运算？

计算机存整数时，底层不是十进制的 0, 1, 2, 3...，而是一串二进制位。例如：

十进制 13 = 二进制 1101

可以把 1101 想成 4 个小灯泡：

位置：   3 2 1 0
二进制： 1 1 0 1
含义：   开 开 关 开

每一位都有自己的价值：

所以 13 = 8 + 4 + 1。

位运算就是直接操作这些小灯泡。普通加减乘除是对整个数字做运算；位运算是对数字内部的每一盏灯单独操作。

竞赛中的典型应用：

一个最小例子：为什么 x & 1 能判断奇偶？

一个数是否为奇数，只看二进制的最后一位：

12 = 1100，最后一位是 0，所以是偶数
13 = 1101，最后一位是 1，所以是奇数

1 的二进制只有最后一位是 1：

13 & 1
1101
0001
----
0001  -> 结果不是 0，所以 13 是奇数

12 & 1
1100
0001
----
0000  -> 结果是 0，所以 12 是偶数

这就是位运算的思维方式：不看整个数，只盯住你关心的那一位。

2.6.2 六种基本位运算符

直觉记忆

AND  &：两个都是1才得1（取交集：都有才保留）
OR   |：有一个是1就得1（取并集：有一个就保留）
XOR  ^：不同为1，相同为0（取差集/翻转：不一样才保留）
NOT  ~：0变1，1变0（取补集）

一位一位地算，别整串一起看

初学位运算时，最容易犯的错误是把 1100 & 1010 当成普通数字计算。实际上它是「同一列对同一列」计算：

  1100
& 1010
------
  1000

从右到左逐列看：

同理，| 是「只要有一个 1 就亮」，^ 是「两边不一样才亮」。

左移和右移：把灯泡整体搬家

<< 和 >> 不改变每一位本身，而是把整排二进制位往左或往右移动。

1       = 0001
1 << 1  = 0010 = 2
1 << 2  = 0100 = 4
1 << 3  = 1000 = 8

所以 1 << k 表示：只让第 k 位亮起来。

这也是后面所有模板的基础：

1 << k

可以理解成一个「只选中第 k 位的小工具」。

2.6.3 常用位操作模板

先记住一个核心工具：

1 << k

它表示一个只有第 k 位是 1 的数字。注意第 k 位从右往左数，并且从 0 开始：

k:       3 2 1 0
1 << 0 = 0 0 0 1
1 << 1 = 0 0 1 0
1 << 2 = 0 1 0 0
1 << 3 = 1 0 0 0

假设 x = 13 = 1101，我们想操作第 2 位，可以先造出面具 1 << 2 = 0100。后面所有操作，都是让 x 和这个面具做运算。

1. 检查第 k 位是否为 1

问题： 给你一个整数 x，怎样知道它的第 k 位是不是亮着？

bool check(int x, int k) {
    return (x >> k) & 1;
}

这段代码分成两步：

1. x >> k：把第 k 位移动到最右边。
2. & 1：只检查最右边这一位是不是 1。

为什么要移动到最右边？因为最右边最容易检查。只要和 1 做 &，就能保留最后一位，其他位都会变成 0。

假设：

x = 13 = 1101
k = 2

第 2 位是从右往左数的第三位：

位置：   3 2 1 0
x：      1 1 0 1
             ↑
          第 2 位

计算过程：

x >> 2：
1101 >> 2 = 0011

再 & 1：
0011
0001
----
0001

结果是 1，说明 13 的第 2 位是亮着的。

如果检查第 1 位：

x >> 1：
1101 >> 1 = 0110

再 & 1：
0110
0001
----
0000

结果是 0，说明第 1 位没有亮。

2. 将第 k 位设为 1（置位）

问题： 怎样把某一盏灯打开？如果它本来就是开的，就保持打开。

int set_bit(int x, int k) {
    return x | (1 << k);
}

这里的关键是 |：只要两边有一个是 1，结果就是 1。

所以我们先用 1 << k 做一个只在第 k 位为 1 的面具，再用 | 把这一位打开。

假设：

x = 13 = 1101
k = 1
mask = 1 << 1 = 0010

计算：

  1101
| 0010
------
  1111 = 15

第 1 位原来是 0，现在被打开了。

如果这一位本来就是 1，也不会有问题：

x = 13 = 1101
k = 2
mask = 0100

  1101
| 0100
------
  1101

第 2 位本来就是 1，置位后仍然是 1。

3. 将第 k 位设为 0（清位）

问题： 怎样把某一盏灯关掉？如果它本来就是关的，就保持关闭。

int clear_bit(int x, int k) {
    return x & ~(1 << k);
}

这段代码看起来比置位难一点，因为多了一个 ~。我们一步一步拆开：

1. 1 << k：制造一个只有第 k 位是 1 的面具。
2. ~(1 << k)：把面具反过来，让第 k 位变成 0，其他位变成 1。
3. x & ~(1 << k)：用 & 保留其他位，同时把第 k 位变成 0。

假设：

x = 13 = 1101
k = 2

先得到面具：

1 << 2 = 0100

反过来：

~0100 = ...1011

为了方便观察，我们只看最低 4 位，就是：

1011

然后做 &：

  1101
& 1011
------
  1001 = 9

第 2 位被关掉了，其他位保持原样。

如果第 k 位本来就是 0，清位也不会改变它：

x = 13 = 1101
k = 1
mask 反过来后最低 4 位是 1101

  1101
& 1101
------
  1101

4. 翻转第 k 位

问题： 怎样让某一盏灯“反过来”？开着就关掉，关着就打开。

int flip_bit(int x, int k) {
    return x ^ (1 << k);
}

这里用的是 ^。它的规则是：相同得 0，不同得 1。

更适合记成：

某一位 ^ 0：保持不变
某一位 ^ 1：发生翻转

所以 x ^ (1 << k) 的意思是：只让第 k 位和 1 做异或，其他位和 0 做异或，因此只有第 k 位会翻转。

例 1：把第 1 位从 0 翻成 1。

x = 13 = 1101
k = 1
mask = 0010

  1101
^ 0010
------
  1111 = 15

例 2：把第 2 位从 1 翻成 0。

x = 13 = 1101
k = 2
mask = 0100

  1101
^ 0100
------
  1001 = 9

所以翻转不是固定变成 1，也不是固定变成 0，而是：原来是什么，就变成相反的状态。

5. 判断一个数是否是 2 的幂

问题： 怎样快速判断 x 是不是 1, 2, 4, 8, 16... 这样的数？

bool is_power_of_two(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

先观察 2 的幂在二进制中的样子：

它们都有一个共同特点：二进制里只有一个 1。

再看 x - 1 会发生什么。以 x = 8 为例：

x     = 1000
x - 1 = 0111

做 &：

  1000
& 0111
------
  0000

结果是 0，说明 8 只有一个 1，所以它是 2 的幂。

再看一个不是 2 的幂的数，比如 12：

x     = 1100
x - 1 = 1011

  1100
& 1011
------
  1000

结果不是 0，说明 12 不只一个 1，所以不是 2 的幂。

为什么还要写 x > 0？因为 0 不是 2 的幂。如果不加这个条件，0 & -1 也会得到 0，容易误判。

6. 获取最低有效位：lowbit

问题： 怎样找到一个数从右往左数，第一盏亮着的灯？

int lowbit(int x) {
    return x & (-x);
}

lowbit(x) 返回的不是第几个位置，而是这一位对应的数值。

例如：

x = 12 = 1100

从右往左看：

位置：   3 2 1 0
x：      1 1 0 0
           ↑
      最右边的 1 在第 2 位

第 2 位的价值是 4，所以：

lowbit(12) = 4

用补码计算就是：

12 的二进制：  0000 1100
-12（补码）：  1111 0100
12 & (-12)：   0000 0100 = 4

这在树状数组中很常见。你可以暂时先记住：lowbit(x) 能拿到 x 最右边那个 1 代表的值。

7. 清除最低有效位

问题： 怎样把最右边那个 1 删除掉？

int clear_lowest(int x) {
    return x & (x - 1);
}

它和判断 2 的幂用的是同一个核心技巧。

假设：

x = 12 = 1100
x - 1 = 11 = 1011

计算：

  1100
& 1011
------
  1000 = 8

可以看到，x 最右边的那个 1 被清掉了。

再来一个例子：

x = 10 = 1010
x - 1 = 9 = 1001

  1010
& 1001
------
  1000 = 8

这件事有什么用？如果我们不断清除最低位的 1，就能统计一个数里面有多少个 1。

8. 统计二进制中 1 的个数：popcount

问题： 怎样知道一个整数的二进制里有几盏灯亮着？

C++ 提供了内置函数：

int count_ones(int x) {
    return __builtin_popcount(x);
}

例如：

x = 13 = 1101

里面有三位是 1，所以：

count_ones(13) = 3

如果不用内置函数，也可以用刚才的 clear_lowest 思想手写：

int count_ones_manual(int x) {
    int cnt = 0;
    while (x) {
        x &= x - 1;
        cnt++;
    }
    return cnt;
}

以 x = 13 = 1101 为例：

第 1 次：1101 -> 1100，cnt = 1
第 2 次：1100 -> 1000，cnt = 2
第 3 次：1000 -> 0000，cnt = 3

循环结束时，说明所有 1 都被清掉了，所以原来一共有 3 个 1。

常用模板汇总

前面我们已经把每个函数都单独拆开讲过了。真正写题时，可以把下面这组函数当成工具箱：

// ===== 单个位的操作（第 k 位，从 0 开始计数）=====

// 检查第 k 位是否为 1
bool check(int x, int k) { return (x >> k) & 1; }

// 将第 k 位设为 1（置位）
int set_bit(int x, int k) { return x | (1 << k); }

// 将第 k 位设为 0（清位）
int clear_bit(int x, int k) { return x & ~(1 << k); }

// 翻转第 k 位（0→1，1→0）
int flip_bit(int x, int k) { return x ^ (1 << k); }


// ===== 常用技巧 =====

// 判断 x 是否为 2 的幂（且 x > 0）
bool is_power_of_two(int x) { return x > 0 && (x & (x - 1)) == 0; }

// 获取最低有效位（lowbit，树状数组核心）
int lowbit(int x) { return x & (-x); }

// 清除最低有效位
int clear_lowest(int x) { return x & (x - 1); }

// 统计 x 中 1 的个数（popcount）
int count_ones(int x) { return __builtin_popcount(x); }     // 内置函数
// 或手动：
int count_ones_manual(int x) {
    int cnt = 0;
    while (x) { x &= x - 1; cnt++; }  // 每次清除最低位的1
    return cnt;
}

本节总结

2.6.4 用整数表示集合（状压）

当元素数量 N ≤ 30 时，可以用一个 int 整数的 N 个二进制位表示一个集合。

编码规则： 第 i 个元素在集合中 ↔ 第 i 位为 1。

把集合想象成签到表

如果有 5 个学生，编号为 0, 1, 2, 3, 4，我们可以用 5 个开关表示他们有没有被选中：

学生编号： 4 3 2 1 0
是否选中： 1 0 1 0 1

这表示选中了学生 {0, 2, 4}。写成二进制就是 10101，十进制是 21。

这样做的好处是：一个整数就能保存一个集合，而且加入、删除、检查元素都能用 O(1) 完成。

// 集合 {0, 2, 4} 表示为：
// 二进制：10101 = 21

int S = 0;           // 空集
S = set_bit(S, 0);   // 加入元素 0：S = 00001 = 1
S = set_bit(S, 2);   // 加入元素 2：S = 00101 = 5
S = set_bit(S, 4);   // 加入元素 4：S = 10101 = 21

// 检查元素 2 是否在集合中
bool has2 = check(S, 2);  // true

// 删除元素 2
S = clear_bit(S, 2);      // S = 10001 = 17

// 集合大小
int size = __builtin_popcount(S);  // 2

集合运算

int A = 0b1100;  // {2, 3}
int B = 0b1010;  // {1, 3}

int inter = A & B;    // 交集：0b1000 = {3}
int unio  = A | B;    // 并集：0b1110 = {1, 2, 3}
int diff  = A & ~B;   // 差集 A-B：0b0100 = {2}
int xor_s = A ^ B;    // 对称差：0b0110 = {1, 2}

这些集合运算其实和数学里的集合完全对应：

例如 A = {2, 3}，B = {1, 3}：

A 和 B 都有 3，所以交集是 {3}
A 或 B 出现过 1、2、3，所以并集是 {1,2,3}
A 有但 B 没有的是 2，所以 A-B 是 {2}
只出现一次的是 1 和 2，所以对称差是 {1,2}

2.6.5 枚举所有子集

N 个元素的集合有 2^N 个子集，可以用 for (int s = 0; s < (1 << n); s++) 枚举。

为什么是 2^N？因为每个元素只有两种选择：

不选这个元素 -> 0
选择这个元素 -> 1

如果有 3 个元素，每个元素都有选/不选两种状态，总数就是：

2 × 2 × 2 = 8

也就是 2^3 个子集。

先看 n = 3 的完整例子

所以枚举整数 0 到 2^n - 1，其实就是枚举了所有开关组合，也就是所有子集。

// 枚举 n 个元素的所有子集
void enumerate_subsets(int n) {
    for (int s = 0; s < (1 << n); s++) {
        cout << "子集 " << s << "（二进制 " << bitset<4>(s) << "）：{";
        for (int i = 0; i < n; i++) {
            if (check(s, i)) cout << i << " ";
        }
        cout << "}\n";
    }
}
// enumerate_subsets(3) 输出 2^3 = 8 个子集

枚举某集合 S 的所有子集

有时我们不是枚举全集 {0,1,2,...,n-1} 的所有子集，而是枚举一个已经给定的集合 S 的所有子集。

例如：

S = 10110 = {1,2,4}

我们只想枚举由 {1,2,4} 组成的子集，不能出现元素 0 或 3。

// 枚举 S 的所有非空子集（时间：O(3^n)，见下面说明）
for (int sub = S; sub > 0; sub = (sub - 1) & S) {
    // 处理子集 sub
    // ...
}
// 原理：sub = (sub - 1) & S 每次在 S 的范围内减 1，跳过不属于 S 的位

为什么 sub = (sub - 1) & S 不会跑出 S？

sub - 1 会让二进制发生变化，可能产生一些不属于 S 的 1。再 & S 一次，就像用 S 做过滤器：只有 S 里本来是 1 的位置才能保留下来。

以 S = 10110 为例，枚举过程大致是：

10110
10100
10010
10000
00110
00100
00010

每一步都只使用了 S 中允许的位。

2.6.6 实战例题：状压 + 位运算

前面我们学的是「工具」，这一节开始把工具放进题目里。做位运算题时，可以按照这个顺序思考：

1. 每一位代表什么？ 是一个元素、一个城市，还是一个开关？
2. 1 表示什么，0 表示什么？ 例如 1 表示已选择，0 表示未选择。
3. 要做的操作对应哪个位运算？ 加入用 |，删除用 & ~，检查用 & 或右移。
4. 状态数量有多少？ 如果有 n 个开关，通常会有 2^n 种状态。

例题：集合和问题

给定 N 个数字（N ≤ 20），找有多少个子集的和恰好等于目标值 target。

为什么可以暴力枚举？

N ≤ 20 时，一共有 2^20 = 1,048,576 个子集，大约一百万个。每个子集再扫一遍最多 20 个数，大约两千万次操作，C++ 通常可以接受。

状态设计：

• s 是一个二进制集合。
• s 的第 i 位为 1，表示选择了 a[i]。
• 枚举所有 s，就等于枚举所有可能的选择方案。

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

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    int ans = 0;
    for (int s = 0; s < (1 << n); s++) {
        int sum = 0;
        for (int i = 0; i < n; i++)
            if (check(s, i)) sum += a[i];
        if (sum == target) ans++;
    }
    
    cout << ans << "\n";
}
// 复杂度：O(2^N × N)，N=20 时约 2×10^7，可以通过

例题：旅行商问题（状压 DP 基础）

N 个城市（N ≤ 20），从城市 0 出发经过所有城市恰好一次回到 0，求最短路。

这个题比集合和更难，因为它不仅要记录「访问过哪些城市」，还要记录「现在停在哪个城市」。

状态设计：

dp[mask][v]

含义是：

• mask 表示已经访问过的城市集合。
• v 表示当前所在城市。
• dp[mask][v] 表示在这种情况下的最短距离。

例如 mask = 01011 表示已经访问过城市 {0,1,3}；如果 v = 3，就表示当前停在城市 3。

转移思路：

如果当前在城市 u，下一步可以去一个还没访问过的城市 v。这时：

new_mask = mask | (1 << v);

意思是把城市 v 标记为「已经访问」。

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

int n;
int dist[20][20];
int dp[1 << 20][20];  // dp[mask][v] = 访问了 mask 中的城市，当前在 v，的最短距离

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> dist[i][j];
    
    // 初始化
    for (auto& row : dp) fill(row, row + n, INT_MAX / 2);
    dp[1][0] = 0;  // 从城市 0 出发，mask=1（只访问了0）
    
    // 枚举所有状态
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (dp[mask][u] == INT_MAX / 2) continue;
            if (!check(mask, u)) continue;
            
            // 尝试移动到下一个未访问的城市 v
            for (int v = 0; v < n; v++) {
                if (check(mask, v)) continue;  // 已访问
                int new_mask = set_bit(mask, v);
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    // 所有城市都访问后（mask = (1<<n)-1），回到城市 0
    int ans = INT_MAX;
    int full = (1 << n) - 1;
    for (int u = 1; u < n; u++)
        ans = min(ans, dp[full][u] + dist[u][0]);
    
    cout << ans << "\n";
    // 复杂度：O(2^N × N^2)，N=20 时约 4×10^8（偏大，N=15~18 通常可行）
}

⚠️ 常见错误

💪 练习题

🟢 题目 1：奇偶统计

给定整数 x，输出它的二进制表示中 1 的个数（popcount），以及是否是 2 的幂。

数据规模： 1 ≤ x ≤ 10⁹。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x; cin >> x;
    cout << __builtin_popcount(x) << "\n";
    cout << (x > 0 && (x & (x-1)) == 0 ? "是2的幂" : "不是2的幂") << "\n";
}

🟢 题目 2：位翻转

给定整数 x 和位置数组 k[]，将 x 的这些位翻转后输出结果。

数据规模： 1 ≤ x < 2³¹，1 ≤ M ≤ 100，0 ≤ k[i] < 31。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x, m; cin >> x >> m;
    while (m--) {
        int k; cin >> k;
        x ^= (1 << k);  // XOR 翻转第 k 位
    }
    cout << x << "\n";
}

🟡 题目 3：子集枚举

给定 N 个数字（N ≤ 20），找所有和为偶数的子集数量。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    int cnt = 0;
    for (int s = 0; s < (1 << n); s++) {
        int sum = 0;
        for (int i = 0; i < n; i++)
            if ((s >> i) & 1) sum += a[i];
        if (sum % 2 == 0) cnt++;
    }
    cout << cnt << "\n";
    // 答案总是 2^(n-1)（如果有奇数）
}

🔴 题目 4：最大异或子集

给定 N 个数字（N ≤ 20），选出一个非空子集，使子集内所有数字的异或和最大，输出该最大值。

思路： 枚举所有非空子集，对每个子集计算异或和取最大。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    int ans = 0;
    for (int s = 1; s < (1 << n); s++) {
        int xor_sum = 0;
        for (int i = 0; i < n; i++)
            if ((s >> i) & 1) xor_sum ^= a[i];
        ans = max(ans, xor_sum);
    }
    cout << ans << "\n";
}

进阶（N 较大时）： 用线性基（高斯消元）在 O(N × 30) 内找最大异或值。

🔴 题目 5：USACO Bronze 风格 — 奶牛体操（位运算版）

N 头奶牛（N ≤ 20），K 轮训练。每轮训练中，奶牛按排名从 1 到 N 排列。定义一对奶牛 (i, j) 是「一致的」，若在所有 K 轮中 i 都排在 j 前面。用位运算统计有多少对奶牛是一致的。

输入： 第一行 K N，接下来 K 行每行 N 个整数（1~N 的排列，表示该轮的排名顺序）。

样例输入：

3 4
4 1 2 3
4 1 3 2
4 2 1 3

样例输出： 4

核心思路： 对每头奶牛 i，用一个 N 位整数 before[i] 记录「在某一轮中，哪些奶牛排在 i 前面」。遍历每轮排名，对奶牛 i，排在 i 前面的所有奶牛 j 的第 j 位置 1。K 轮结束后，before[i] 逐位 AND 所有轮的结果——某位保持 1 说明那头奶牛在所有轮中都排在 i 前面。统计所有 before[i] 的 popcount 之和。

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int K, N;
    cin >> K >> N;

    // before[i] 的第 j 位 = 奶牛 j 在所有已完成轮次中是否始终排在 i 前面
    vector<int> before(N, (1 << N) - 1);  // 初始全1，逐轮 AND

    for (int round = 0; round < K; round++) {
        // 读取排名：rank[0]=第1名的奶牛编号...
        vector<int> ranking(N);
        for (int p = 0; p < N; p++) cin >> ranking[p];

        // mask 记录当前已出现的奶牛（排在前面）
        int mask = 0;
        for (int p = 0; p < N; p++) {
            int cow = ranking[p] - 1;  // 转 0-indexed
            before[cow] &= mask;       // AND 上当前排在前面的奶牛集合
            mask |= (1 << cow);        // 将当前奶牛加入已出现集合
        }
    }

    int ans = 0;
    for (int i = 0; i < N; i++)
        ans += __builtin_popcount(before[i]);
    cout << ans << "\n";
}

复杂度分析： 时间 O(K × N)，空间 O(N)。每位用一个 int 做 K 次 AND 操作，非常高效。

💡 章节联系： 位运算是状压 DP（第 6.3 章进阶 DP）的基础工具，也用于树状数组的 lowbit 操作（第 5.7 章）。掌握本章后，你将能读懂绝大多数竞赛代码中的位运算技巧。

本章小结

• 位就是开关：每一位只有 0 和 1 两种状态。
• 1 << k 是核心工具：它能制造一个只选中第 k 位的掩码。
• 单个位操作有固定套路：检查、置位、清位、翻转分别对应不同位运算。
• 状压就是用整数存集合：第 i 位为 1 表示第 i 个元素被选中。
• 枚举子集就是枚举开关组合：0 到 (1 << n) - 1 覆盖了所有选/不选方案。
• 不要只背代码：做题时先问"每一位代表什么"，再选择合适的位运算。

📖 第 2.7 章：指针与内存

很多初学者觉得指针「玄学」「容易崩溃」「能不用就不用」。但真相是：指针是理解 C++ 如何使用内存的钥匙。一旦你建立起「变量住在内存里，每个住处都有门牌号」的图景，指针、引用、数组、动态内存、链表、树——这些后续会反复出现的概念——会突然变得清晰。

本章不要求你成为内存管理专家，而是帮你建立正确的心智模型，并掌握竞赛中真正会用到的指针技能。

2.7.0 从一道题出发：交换为什么没生效

先看一个让无数初学者深夜调试的小程序。它是一道题的雏形，也是一个 Bug：

🐛 题目：交换两头奶牛的位置 农夫 John 要交换奶牛 A 和奶牛 B 的栅栏编号。助手写了一个函数：

void swapPens(int a, int b) {
    int tmp = a;
    a = b;
    b = tmp;
}

int main() {
    int penA = 3, penB = 7;
    swapPens(penA, penB);
    // penA 和 penB 变了吗？
    cout << penA << " " << penB << "\n";  // 输出：3 7 ← 什么都没变！
}

为什么会失败？ 因为函数拿到的是 3 和 7 的复印件——swapPens 把复印件换来换去，原件纹丝不动。函数结束后复印件被销毁，世界毫无变化。

那怎么把「原件」交给函数？直觉上有两条路：

1. 告诉函数原件的「门牌号」，让它直接去那个地址改数据——这就是指针：swapPens(&penA, &penB)，参数类型 int*
2. 给原件起个本地名当别名——这就是引用：swapPens(penA, penB)，参数类型 int&（第 2.3 章你已经用过）

这件小事背后是本章全部内容的主线——「数据住在哪里」和「怎么指到那里」：

拆解这道题需要回答的问题

💡 心智图景先立好：普通变量保存的是数据，指针变量保存的是另一个变量的地址。带着「复印件 vs 门牌号」的问题往下读。

学习目标（学完本章你将能够）：

1. 理解「内存」「地址」「指针」三者的关系，建立正确的心智图景
2. 使用取地址运算符 & 和解引用运算符 *
3. 区分指针和引用，知道各自的适用场景
4. 理解数组名与指针的关系，看懂指针算术
5. 使用 new / delete 进行动态内存分配，并理解什么是内存泄漏
6. 用指针搭建最基础的链表和二叉树节点
7. 知道竞赛中何时该用指针、何时不该用
8. 理解多级指针（int**）的概念，看懂动态二维数组和「指针的指针」
9. 使用指针操作 C 风格字符串（char*），手动实现 strlen / strcpy
10. 了解函数指针的基本语法，看懂回调与自定义排序的底层机制

2.7.1 内存、地址与指针：先建立图景

🏨 旅馆类比

想象计算机内存是一栋有很多房间的旅馆：

• 每个房间就是一个字节（或一组字节）的存储空间
• 每个房间都有一个门牌号——这就是内存地址
• 当你写 int x = 42;，编译器给变量 x 分配了一个房间（比如门牌号 1000），里面放着 42
• 指针就是一张写着「门牌号」的便条。它本身不是房间里的数据，而是「某个房间在哪里」的信息

💡 核心一句话： 普通变量保存的是数据，指针变量保存的是另一个变量的地址。

取地址 & 与解引用 *

C++ 提供两个互为反操作的运算符：

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

int main() {
    int x = 42;

    int* p = &x;   // p 保存 x 的地址（p「指向」x）

    cout << x  << "\n";   // 42      —— x 里的数据
    cout << &x << "\n";   // 0x...   —— x 的地址（每次运行可能不同）
    cout << p  << "\n";   // 0x...   —— 和 &x 相同，p 保存的就是这个地址
    cout << *p << "\n";   // 42      —— 解引用：顺着地址找到 x，读出 42

    *p = 100;             // 通过指针修改 x（顺着门牌号去改房间内容）
    cout << x << "\n";    // 100     —— x 真的被改了！

    return 0;
}

🤔 int* p 中的 * 和 *p 中的 * 是一回事吗？ 不是！这是初学者最大的困惑来源：

• 在声明里，int* p 的 * 表示「p 是一个指向 int 的指针」（类型的一部分）
• 在使用里，*p 的 * 是解引用运算符，表示「取出 p 指向的值」 同一个符号，两种含义，靠上下文区分。

图示：指针指向变量

🎬 互动：一步步看懂 & 与 *

下面这个可视化把「取地址 → 解引用读 → 解引用写」拆成 5 步。点击「下一步」，盯着内存房间和指针箭头，亲眼看到 *p = 100 是如何穿过指针真正改到 x 的：

2.7.2 空指针与 nullptr

一个指针如果还没指向任何有效对象，应该让它指向「空」。现代 C++ 用 nullptr 表示空指针：

int* p = nullptr;   // p 不指向任何东西

if (p == nullptr) {
    cout << "p 是空指针，不能解引用\n";
}

// *p;   // ❌ 危险！解引用空指针 → 程序崩溃（段错误）

⚠️ 不要用旧写法 NULL 或 0。 老代码常写 int* p = NULL;，但 NULL 本质是 0，在重载/模板场景会引起歧义。现代 C++ 一律用 nullptr，类型安全且语义清晰。

🐛 头号崩溃原因： 解引用空指针或「野指针」（指向无效地址的指针）。这是 Segmentation fault（段错误）最常见的来源。永远在解引用前确认指针有效。

🧩 辨析：& 和 * 各有两副面孔

& 和 * 都是「一符多义」，靠上下文区分。初学者把它们彻底分清，指针就懂了一半：

💡 一句话记忆：贴着变量/指针单独出现 → 取地址 / 解引用；夹在两个数中间 → 位与 / 乘法；跟在类型后面 → 引用 / 指针声明。

2.7.3 指针 vs 引用：到底用哪个？

第 2.3 章你已经学过引用（int& r = x;）。引用和指针都能「间接访问」另一个变量，但它们有重要区别。

int x = 10, y = 20;

// ---- 引用 ----
int& r = x;    // r 是 x 的别名，必须在声明时绑定
r = 100;       // 直接改 x，x == 100
// r = y;      // 这不是「让 r 指向 y」，而是把 y 的值赋给 x！
// 引用一旦绑定，终生不能改绑

// ---- 指针 ----
int* p = &x;   // p 指向 x
*p = 100;      // 改 x，x == 100
p = &y;        // OK！指针可以改指向 y
*p = 200;      // 现在改的是 y，y == 200
p = nullptr;   // 指针可以为空

对比表

⚡ 竞赛中的经验法则：

• 优先用引用。 函数传参、避免复制大对象，引用更安全、语法更干净（见第 2.3 章的 const vector<int>&）。
• 需要指针的少数场景： ① 指向的目标需要变化（如遍历链表）；② 需要表示「没有目标」的状态（nullptr，如树的空子节点）；③ 动态分配内存（new）。

2.7.4 指针与数组：它们是亲戚

C++ 中数组和指针关系密切。数组名在大多数场景会「退化」成指向首元素的指针。

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

int main() {
    int arr[5] = {10, 20, 30, 40, 50};

    int* p = arr;        // 等价于 int* p = &arr[0]; 数组名退化为首元素指针

    cout << *p     << "\n";   // 10     —— arr[0]
    cout << *(p+1) << "\n";   // 20     —— arr[1]
    cout << *(p+2) << "\n";   // 30     —— arr[2]

    // 下面四种写法完全等价：
    cout << arr[2]   << "\n"; // 30
    cout << *(arr+2) << "\n"; // 30
    cout << p[2]     << "\n"; // 30
    cout << *(p+2)   << "\n"; // 30

    return 0;
}

🤔 为什么 arr[i] 等价于 *(arr + i)？ 因为下标运算 arr[i] 的本质就是「从首地址 arr 偏移 i 个元素，再解引用」。这也解释了为什么数组下标从 0 开始——下标就是「偏移量」，第一个元素偏移 0。

指针算术

指针 +1 不是地址 +1 字节，而是前进一个元素的大小：

int arr[5] = {10, 20, 30, 40, 50};
int* p = arr;

// 假设 int 占 4 字节，arr 起始地址 1000：
// p   指向 1000（arr[0]）
// p+1 指向 1004（arr[1]）—— 自动跳过一个 int 的 4 字节
// p+2 指向 1008（arr[2]）

int arr[5] = {10, 20, 30, 40, 50};

// 方式一：传统下标
for (int i = 0; i < 5; i++) cout << arr[i] << " ";
cout << "\n";

// 方式二：指针遍历（理解即可，竞赛中很少这么写）
for (int* p = arr; p < arr + 5; p++) {
    cout << *p << " ";
}
cout << "\n";

⚡ 竞赛提示： STL 的 sort(arr, arr + n)、lower_bound(arr, arr + n, x) 中的 arr 和 arr + n 正是「首元素指针」和「尾后指针」。理解了数组退化为指针，就理解了这些函数的参数为什么这么写。

2.7.5 指针作函数参数

第 2.3 章我们用引用实现了「函数修改原变量」。其实用指针也能做到——这是 C 语言的经典写法，在很多底层代码、链表/树操作中仍然常见。

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

// 用指针：传入地址，函数内通过解引用修改原变量
void swapByPointer(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 用引用：更简洁（推荐）
void swapByRef(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

int main() {
    int x = 1, y = 2;

    swapByPointer(&x, &y);   // 必须显式传地址 &x, &y
    cout << x << " " << y << "\n";  // 2 1

    swapByRef(x, y);         // 直接传变量
    cout << x << " " << y << "\n";  // 1 2

    return 0;
}

💡 两者怎么选？ 在 C++ 中，能用引用就用引用（语法干净、不会传空）。需要用指针的典型情况：参数本身可能是 nullptr（「可选」语义），或者你在写链表/树这类天生用指针表达的结构。

2.7.6 动态内存：new 与 delete

到目前为止，我们的数组大小要么编译时确定，要么用 vector。还有第三种方式：在运行时手动向系统申请内存，这叫动态内存分配。

栈内存 vs 堆内存

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

int main() {
    // 动态分配单个 int
    int* p = new int;     // 在堆上申请一个 int
    *p = 42;
    cout << *p << "\n";   // 42
    delete p;             // 用完必须释放！否则内存泄漏

    // 动态分配数组（运行时才知道大小）
    int n;
    cin >> n;
    int* arr = new int[n];   // 堆上申请 n 个 int
    for (int i = 0; i < n; i++) arr[i] = i * i;
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << "\n";
    delete[] arr;            // 释放数组要用 delete[]（带方括号）！

    return 0;
}

⚠️ 三条铁律

1. new 配 delete，new[] 配 delete[]。 申请数组用 new[]，就必须用 delete[] 释放，否则行为未定义。
2. 每个 new 都要有对应的 delete。 否则就是内存泄漏——申请的内存永远还不回去。
3. delete 之后不要再用那个指针（变成「悬空指针」），可以 delete 后立刻 p = nullptr;。

🤔 竞赛里到底用不用 new/delete？ 绝大多数情况：不用！ 竞赛中程序运行完就退出，操作系统会回收所有内存，所以「内存泄漏」通常无害；而且 new/delete 写起来啰嗦、容易出错。

• 需要动态数组？→ 用 vector（自动管理内存，见第 2.3 章）
• 需要动态字符串？→ 用 string 真正会手写 new 的，主要是链表、二叉树这类需要逐个创建节点的结构（见下一节）——而即便如此，很多选手也用数组模拟或静态节点池来避免 new（见第 5.5、5.7 章）。

2.7.7 指针的杀手级应用：链表与树节点

指针真正不可替代的地方，是构建节点之间互相连接的数据结构。最经典的就是链表和树。本节先把链表讲扎实：它为什么存在、和数组有什么不同、怎样遍历、插入、删除，再过渡到树节点。

数组存储 vs 链表存储

数组和链表都能表示「一串元素」，但它们在内存里的组织方式完全不同：

• 数组：元素挨在一起，存放在一段连续内存中。
• 链表：每个元素是一个节点，节点可以分散在内存各处；节点里额外存一个指针，告诉我们「下一个节点在哪里」。

💡 一句话选择： 需要频繁随机访问 → 用数组 / vector；需要频繁在已知位置插入、删除 → 链表更合适。但在竞赛中，真正手写指针链表并不多，更多是用数组模拟链表。

单链表节点：数据 + 指向下一个节点的指针

每个链表节点通常由两部分组成：

struct Node {
    int data;       // 当前节点保存的数据
    Node* next;     // 指向下一个节点；最后一个节点的 next 为 nullptr
};

链表只需要保存一个头指针 head，它指向第一个节点。之后顺着 next 一直走，就能访问整条链：

Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head->next->next = new Node{3, nullptr};
// head -> 1 -> 2 -> 3 -> nullptr

🤔 cur->data 是什么语法？ cur 是指针，cur->data 等价于 (*cur).data，意思是「先顺着指针找到节点，再取它的 data 成员」。-> 是「指针访问成员」的专用运算符，比 (*cur).data 好写。这个语法在链表、树里随处可见。

链表基础操作一：遍历、计数、查找

链表没有下标，不能直接跳到第 i 个元素。它的所有操作都建立在同一个动作上：从 head 出发，沿着 next 一个一个走。

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

struct Node {
    int data;
    Node* next;
};

void printList(Node* head) {
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        cout << cur->data << " ";
    }
    cout << "\n";
}

int length(Node* head) {
    int cnt = 0;
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        cnt++;
    }
    return cnt;
}

Node* findValue(Node* head, int target) {
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        if (cur->data == target) return cur;
    }
    return nullptr;
}

int main() {
    Node* head = new Node{1, nullptr};
    head->next = new Node{2, nullptr};
    head->next->next = new Node{3, nullptr};

    printList(head);                 // 1 2 3
    cout << length(head) << "\n";     // 3
    cout << (findValue(head, 2) != nullptr) << "\n";  // 1

    return 0;
}

⚠️ 链表遍历的核心条件： cur != nullptr。一旦 cur 是空指针，就不能再写 cur->data 或 cur->next，否则会崩溃。

链表基础操作二：插入节点

链表插入的本质是改指针。不要想成「把一排元素往后挪」，链表里没有整体搬移，只有箭头重连。

头插法：插到链表最前面

如果新节点要成为新的第一个节点，只需要让它指向旧头，再更新 head：

void pushFront(Node*& head, int x) {
    Node* node = new Node{x, head};  // 新节点指向旧 head
    head = node;                     // head 改为新节点
}

这里参数写成 Node*& head，意思是「head 指针的引用」。因为函数内部不仅要改节点内容，还要修改外部的 head 本身。

尾插法：插到链表最后面

如果只有 head，每次尾插都要从头走到尾，单次 O(N)。所以实际常维护一个 tail 指针，直接指向最后一个节点：

void pushBack(Node*& head, Node*& tail, int x) {
    Node* node = new Node{x, nullptr};
    if (head == nullptr) {       // 空链表：新节点既是头也是尾
        head = tail = node;
    } else {
        tail->next = node;       // 旧尾巴指向新节点
        tail = node;             // 更新尾指针
    }
}

插到某个节点后面

已知节点 pos，把新节点插到它后面，只需要两步：

void insertAfter(Node* pos, int x) {
    if (pos == nullptr) return;
    Node* node = new Node{x, pos->next};  // 新节点先接住 pos 原来的后继
    pos->next = node;                     // pos 再指向新节点
}

⚠️ 顺序不能反： 必须先让新节点接住 pos->next，再改 pos->next。如果先写 pos->next = node，原来的后半段链表就丢了。

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

struct Node {
    int data;
    Node* next;
};

void pushFront(Node*& head, int x) {
    head = new Node{x, head};
}

void pushBack(Node*& head, Node*& tail, int x) {
    Node* node = new Node{x, nullptr};
    if (head == nullptr) {
        head = tail = node;
    } else {
        tail->next = node;
        tail = node;
    }
}

void insertAfter(Node* pos, int x) {
    if (pos == nullptr) return;
    pos->next = new Node{x, pos->next};
}

void printList(Node* head) {
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        cout << cur->data << " ";
    }
    cout << "\n";
}

int main() {
    Node* head = nullptr;
    Node* tail = nullptr;

    pushBack(head, tail, 1);      // 1
    pushBack(head, tail, 3);      // 1 -> 3
    insertAfter(head, 2);         // 1 -> 2 -> 3
    pushFront(head, 0);           // 0 -> 1 -> 2 -> 3

    printList(head);
    return 0;
}

链表基础操作三：删除节点

单链表删除节点也靠改指针，但有一个限制：要删除某个节点，通常需要知道它的前驱节点。因为前驱节点的 next 要绕过被删除节点，指向后面的节点。

删除头节点

头节点没有前驱，所以要单独处理，并且要修改 head 本身：

void popFront(Node*& head) {
    if (head == nullptr) return;
    Node* old = head;
    head = head->next;
    delete old;
}

删除某个节点后面的节点

已知 pos，删除 pos 后面的节点：

void eraseAfter(Node* pos) {
    if (pos == nullptr || pos->next == nullptr) return;
    Node* victim = pos->next;
    pos->next = victim->next;   // 绕过 victim
    delete victim;              // 释放被删除节点
}

按值删除第一个出现的节点

按值删除时，我们不知道前驱是谁，所以要一边遍历一边维护 prev 和 cur：

bool eraseValue(Node*& head, int target) {
    if (head == nullptr) return false;

    if (head->data == target) {
        popFront(head);
        return true;
    }

    Node* prev = head;
    Node* cur = head->next;
    while (cur != nullptr) {
        if (cur->data == target) {
            prev->next = cur->next;
            delete cur;
            return true;
        }
        prev = cur;
        cur = cur->next;
    }
    return false;
}

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

struct Node {
    int data;
    Node* next;
};

void pushBack(Node*& head, Node*& tail, int x) {
    Node* node = new Node{x, nullptr};
    if (head == nullptr) {
        head = tail = node;
    } else {
        tail->next = node;
        tail = node;
    }
}

void popFront(Node*& head) {
    if (head == nullptr) return;
    Node* old = head;
    head = head->next;
    delete old;
}

bool eraseValue(Node*& head, int target) {
    if (head == nullptr) return false;
    if (head->data == target) {
        popFront(head);
        return true;
    }

    Node* prev = head;
    Node* cur = head->next;
    while (cur != nullptr) {
        if (cur->data == target) {
            prev->next = cur->next;
            delete cur;
            return true;
        }
        prev = cur;
        cur = cur->next;
    }
    return false;
}

void printList(Node* head) {
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        cout << cur->data << " ";
    }
    cout << "\n";
}

void clearList(Node*& head) {
    while (head != nullptr) {
        popFront(head);
    }
}

int main() {
    Node* head = nullptr;
    Node* tail = nullptr;

    for (int x : {1, 2, 3, 4}) pushBack(head, tail, x);
    printList(head);       // 1 2 3 4

    eraseValue(head, 3);
    printList(head);       // 1 2 4

    popFront(head);
    printList(head);       // 2 4

    clearList(head);
    return 0;
}

⚠️ 关于 tail 的细节： 上面的删除示例为了突出核心逻辑，只维护了 head。如果你的程序还保存 tail，删除尾节点时必须同步更新 tail，否则 tail 会变成悬空指针。实际写题时，要么不维护 tail，要么把删除函数也设计成能更新 tail。

链表基础操作复杂度

链表最容易写错的地方

1. 忘记处理空链表： head == nullptr 时不能访问 head->next。
2. 忘记更新 head： 删除或插入到头部时，head 本身会变。
3. 改指针顺序错误： 插入时先保存旧后继，再重连；反转链表时先保存 next，再改 cur->next。
4. 删除后继续使用旧指针： delete victim; 之后 victim 就不能再解引用。
5. 维护 tail 时不同步： 删除尾节点、清空链表时，要让 tail 指向新的尾或 nullptr。

二叉树节点

树是链表思想的自然延伸——每个节点不止一个「下一个」，而是有左右两个孩子指针：

struct TreeNode {
    int val;
    TreeNode* left;    // 左孩子（没有则为 nullptr）
    TreeNode* right;   // 右孩子（没有则为 nullptr）
};

// 创建一个节点
TreeNode* root = new TreeNode{1, nullptr, nullptr};
root->left  = new TreeNode{2, nullptr, nullptr};
root->right = new TreeNode{3, nullptr, nullptr};

//        1
//       / \
//      2   3

🔗 承上启下： 链表和树的完整算法（遍历、插入、删除、BST、平衡）会在 第 5.5 章（二叉树与树算法） 详细展开。本章你要掌握的是「指针如何把节点串起来」以及「插入 / 删除本质上就是重连指针」。

🆚 指针版 vs 数组模拟版（竞赛重点）

竞赛选手往往不用 new，而是用数组下标当「指针」——这叫数组模拟（静态分配 / 节点池）。提前建立这个对照，到第 5.5/5.7 章就不会陌生：

// ---- 指针版 ----
struct Node { int v; Node* nxt; };
Node* head = new Node{1, nullptr};
head->nxt = new Node{2, nullptr};

// ---- 数组模拟版（竞赛常用）----
const int N = 100005;
int val[N], nxt[N], cnt = 0;   // 下标 0 留作「空」，真实节点从 1 开始
int head = 0;                  // 0 表示空链表

int newNode(int v) {           // 「new」一个节点 → 返回下标
    ++cnt;
    val[cnt] = v;
    nxt[cnt] = 0;
    return cnt;
}

void insertAfter(int pos, int id) {
    nxt[id] = nxt[pos];
    nxt[pos] = id;
}

// 建立 1 -> 2
head = newNode(1);
insertAfter(head, newNode(2));

// 遍历：用下标代替指针，0 代替 nullptr
for (int i = head; i != 0; i = nxt[i]) cout << val[i] << " ";

📌 拓展（了解即可）： 工程开发中常用智能指针 unique_ptr / shared_ptr 自动管理内存（离开作用域自动 delete，杜绝泄漏）。但竞赛中几乎不用——它们有额外开销，且竞赛程序结束即回收内存。知道有这回事即可，竞赛里继续用裸指针或数组模拟。

2.7.8 const 与指针：只读保护

const 和指针结合时位置不同，含义不同。这是面试和阅读源码的高频考点：

int x = 10, y = 20;

const int* p1 = &x;   // 指向 const：不能通过 p1 改值，但能改 p1 指向
// *p1 = 99;  ❌ 不能改值
p1 = &y;              // ✓ 能改指向

int* const p2 = &x;   // const 指针：能改值，但不能改指向
*p2 = 99;             // ✓ 能改值
// p2 = &y;  ❌ 不能改指向

const int* const p3 = &x;  // 都不能改

💡 读法口诀： 从右往左读。const int* p 读作「p 是指针，指向 const int」；int* const p 读作「p 是 const 指针，指向 int」。看 const 离谁近就管谁。

2.7.9 多级指针：指向指针的指针

指针本身也是变量，也住在内存的某个房间里。所以——指针也有地址。指向「指针」的指针，就是多级指针，最常见的是二级指针 int**。

为什么需要指向指针的指针？

三个经典场景：

1. 在函数内修改指针本身（比如让一个 int* 参数指向新分配的内存）
2. 动态二维数组（int** 指向一组 int*，每个 int* 再指向一行）
3. 命令行参数 argv（main 的第二个参数就是 char**）

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

// 想让函数修改外部指针的指向？传二级指针！
void allocate(int** pp, int n) {
    *pp = new int[n];   // 通过解引用二级指针，修改外部指针
}

int main() {
    int* arr = nullptr;
    allocate(&arr, 5);  // 传 arr 的地址（int**）
    for (int i = 0; i < 5; i++) arr[i] = i * i;
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
    cout << "\n";
    delete[] arr;
    return 0;
}

💡 也可以用指针的引用（int*&）达到同样效果，语法更干净：

void allocate(int*& p, int n) { p = new int[n]; }

但二级指针是更底层的理解，也是阅读底层代码和旧代码时的常见写法。

动态二维数组

当行数和列数都在运行时才能确定时，可以用 int** 构建二维数组：

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

int main() {
    int n = 3, m = 4;

    // 分配 n 个 int*（每行的指针）
    int** mat = new int*[n];
    for (int i = 0; i < n; i++) {
        mat[i] = new int[m];  // 每行分配 m 个 int
    }

    // 赋值
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            mat[i][j] = i * m + j;

    // 打印
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << setw(3) << mat[i][j];
        cout << "\n";
    }

    // 释放：先释放每一行，再释放行指针数组
    for (int i = 0; i < n; i++) delete[] mat[i];
    delete[] mat;

    return 0;
}

⚡ 竞赛提示： 上面这种 int** 二维数组在竞赛中几乎不用——它要多次 new，内存不连续（缓存不友好），释放也麻烦。竞赛中的动态二维数组一律用 vector<vector<int>>（见第 2.3 章），既安全又简洁。这里展示二级指针主要是帮你建立起「指针的指针」的图景，读到底层代码或旧代码时能看得懂。

图解：二级指针的层级关系

📌 总结一句话： int x → int* p = &x（一级指针，指向变量）→ int** pp = &p（二级指针，指向指针）。每一级解引用 * 就沿着箭头往前走一层：*pp 得到 p，**pp 得到 x。

2.7.10 指针与C风格字符串

在 C++ 诞生之前，C 语言用以 \0（空字符）结尾的字符数组来表示字符串。这种「C风格字符串」的类型是 char* 或 const char*。虽然现代 C++ 中 std::string 是绝对主流，但理解 char* 对阅读底层代码、竞赛模板、以及深化指针理解都很有帮助。

字符串字面量

const char* s = "hello";   // s 指向字符串字面量 "hello\0"
// s[0] = 'H';  ❌ 字符串字面量存在只读区，修改是未定义行为！

⚠️ 字符串字面量 "hello" 的类型是 const char[6]（包含末尾的 \0），存储在只读内存区。所以必须用 const char* 来指向它。老代码可能写 char* s = "hello";，这在现代 C++ 中是不推荐的（甚至可能编译不过）。

用指针遍历C风格字符串

C风格字符串以 \0 结尾，所以遍历时不需要知道长度：

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

// 自己实现 strlen：数到 '\0' 为止
int myStrlen(const char* s) {
    int len = 0;
    while (*s != '\0') {   // 等价于 while (*s)
        len++;
        s++;               // 指针前进到下一个字符
    }
    return len;
}

// 自己实现 strcpy：把 src 复制到 dst
void myStrcpy(char* dst, const char* src) {
    while (*src != '\0') {
        *dst = *src;       // 逐字符复制
        dst++;
        src++;
    }
    *dst = '\0';           // 别忘了末尾的 '\0'！
}

// 更「指针味」的写法——一行搞定：
void myStrcpyV2(char* dst, const char* src) {
    while ((*dst++ = *src++));  // 赋值 + 判断 + 指针前进，一体完成
}

int main() {
    const char* s = "hello";
    cout << myStrlen(s) << "\n";  // 5

    char buf[100];
    myStrcpy(buf, s);
    cout << buf << "\n";          // hello

    return 0;
}

💡 上面「一行搞定」的写法 while ((*dst++ = *src++)); 是经典 C 语言风格的指针练习。它把 赋值、指针前进、判断 压缩成一行，浓缩了指针操作的精华。如果你是初学者，建议先用分步写法理解清楚，再回来看这一行——你会发现指针没那么玄了。

C风格字符串 vs std::string

⚡ 竞赛铁律：优先用 std::string。 只在 main(int argc, char* argv[]) 的命令行参数、或调用某些 C 库函数时才会接触到 char*。本节的目的不是让你回去用 C 风格字符串，而是让你看到时能读懂。

2.7.11 函数指针入门

C++ 中函数也有地址。函数指针就是指向函数的指针——可以像传递数据一样传递「要执行什么操作」。这是回调机制（callback）的基石。

基本语法

函数指针的声明语法有点特别，需要把 * 和函数名用括号括起来：

// 一个函数：输入两个 int，返回 bool
bool cmp(int a, int b) { return a > b; }

// 对应的函数指针类型：bool (*)(int, int)
bool (*fp)(int, int) = cmp;   // fp 指向 cmp
//  ↑     ↑           ↑
// 返回值 指针名(括号必须)  参数类型列表

// 调用函数指针：两种写法等价
cout << fp(3, 5) << "\n";    // false（3 > 5）
cout << (*fp)(3, 5) << "\n"; // false（同上，更明确）

竞赛中的典型应用：自定义排序

std::sort 的第三个参数就是一个函数指针（或函数对象）：

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

bool cmpAbs(int a, int b) {
    return abs(a) < abs(b);  // 按绝对值升序
}

int main() {
    vector<int> a = {-5, 3, -1, 4, -2};
    sort(a.begin(), a.end(), cmpAbs);  // cmpAbs 作为函数指针传入
    for (int x : a) cout << x << " ";  // -1 -2 3 4 -5
    cout << "\n";
    return 0;
}

💡 C++ 中更推荐用 lambda 表达式 或 函数对象（functor） 代替裸函数指针，因为类型更安全、编译器更容易内联优化。但函数指针是理解这些高级特性的基础——lambda 本质上是语法糖，底层仍是函数指针或函数对象。

函数指针数组

当需要在多个操作之间动态选择时，函数指针数组非常有用：

int add(int a, int b) { return a + b; }
int sub(int a, int b) { return a - b; }
int mul(int a, int b) { return a * b; }

int (*ops[3])(int, int) = {add, sub, mul};  // 函数指针数组

int op; cin >> op;
cout << ops[op](10, 5) << "\n";  // 动态选择操作

⚡ 竞赛提示： 函数指针在竞赛中不常用（往往被 lambda、std::function 或直接重载替代），但它是理解回调、事件驱动、以及 qsort 等 C 标准库函数的必备知识。了解即可，不必深入研究。

⚠️ 第 2.7 章常见错误

本章总结

📌 核心要点

❓ 常见问题

Q1：指针这么危险，竞赛里还有必要学吗？

A：有，但要分清主次。90% 的题目你用 vector、string、引用就够了，根本不用裸指针。 但当你做到链表、二叉树、图的链式前向星，或者读别人的模板代码时，不懂指针就寸步难行。本章的目标是让你「看得懂、用得对」，而不是处处手写 new。

Q2：引用和指针，到底优先用哪个？

A：优先引用。 函数传参避免复制 → 用 const T&；要修改原变量 → 用 T&。只有在「目标会变化」（遍历链表）、「可能没有目标」（树的空孩子 nullptr）、「动态分配」（new）这三种情况下才需要指针。

Q3：*p、&x、p->m 老是搞混怎么办？

A：记住三句话：&x 是「x 住在哪」（取地址）；*p 是「顺着 p 去看那个房间」（解引用）；p->m 是「顺着 p 找到结构体，再取它的成员 m」。多写几遍链表遍历的代码，肌肉记忆就建立了。

Q4：竞赛中真的要手动 delete 吗？会不会忘了就丢分？

A：通常不会丢分。 程序结束时操作系统自动回收全部内存，所以竞赛里的内存泄漏一般无害。真正要小心的是运行中反复 new 导致超内存（MLE）——这种情况极少。结论：能用 vector/string 就别手动管理内存。

下面是一个会触发 MLE 的反例——在大循环里反复 new 却从不 delete：

// ❌ 危险：每次循环都在堆上申请，永不释放
for (int i = 0; i < 10000000; i++) {
    int* p = new int[1000];   // 每次 4KB，累计 ~40 GB → MLE！
    // ... 用完 p 却忘了 delete[] p;
}
// ✅ 修复：要么循环外只申请一次复用，要么用完即 delete[] p;，
//         最稳妥是直接用 vector<int> p(1000);（出作用域自动回收）

Q5：为什么有些选手的树/链表代码完全不用指针？

A：他们用数组模拟（也叫静态分配/节点池）：用 int left[N], right[N], val[N]; 三个数组当作节点，用下标当「指针」。这样更快、更不容易出错、还能避免 new 的开销，是竞赛中的主流写法（详见第 5.5、5.7 章）。理解了指针版，再看数组版会更透彻。

Q6：多级指针、函数指针这些东西竞赛中真用得上吗？

A：直接使用不多，但理解后读代码能力大幅提升。 二级指针帮你理解 argv（命令行参数）、动态二维数组的底层；函数指针帮你理解 sort 的自定义比较、qsort 回调。更重要的是，这些概念是后续 STL 函数对象、lambda 表达式等高级特性的基础。一句话：可以不天天写，但不能看不懂。

🔗 与后续章节的联系

• 第 5.5 章（二叉树与树算法）：本章的 TreeNode 结构是树遍历、BST 的起点
• 第 5.6 章（并查集）、第 5.7 章（线段树）：会看到「指针版」与「数组模拟版」两种实现的取舍
• 第 5.1 章（图的基础）：链式前向星本质上是用数组模拟链表来存图
• 本章建立的「内存与地址」心智模型，会让你对 vector 扩容、string 底层、引用传参的理解更深刻

练习题

热身 2.7.1 — 通过指针修改 声明 int x = 5;，定义一个指针 p 指向 x，通过 *p 把 x 改成 99，然后打印 x。

期望输出： 99

思路： 用 &x 给指针赋值，再用 *p 解引用赋值。

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

int main() {
    int x = 5;
    int* p = &x;    // p 指向 x
    *p = 99;        // 通过指针修改 x
    cout << x << "\n";  // 99
    return 0;
}

关键点：

• int* p = &x;——& 取地址
• *p = 99;——* 解引用，改的是 x 本身

热身 2.7.2 — 指针交换 编写函数 void swp(int* a, int* b)，用指针交换两个变量。在 main 中读入两个整数，交换后打印。

样例输入： 3 7 → 样例输出： 7 3

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

void swp(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main() {
    int x, y;
    cin >> x >> y;
    swp(&x, &y);    // 注意要传地址
    cout << x << " " << y << "\n";
    return 0;
}

关键点：

• 函数参数是 int*，调用时必须传地址 &x, &y
• 函数内用 *a、*b 访问原变量

热身 2.7.3 — 数组与指针 声明 int arr[5] = {10,20,30,40,50};，定义指针 p = arr，用 *(p+2) 打印第三个元素。

期望输出： 30

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

int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    int* p = arr;           // 数组名退化为首元素指针
    cout << *(p + 2) << "\n";  // 30，等价于 arr[2]
    return 0;
}

关键点：

• p = arr 等价于 p = &arr[0]
• *(p+2) 等价于 p[2]、arr[2]——指针算术按元素大小前进

题目 2.7.4 — 找最大值并返回指针 读入 N 个整数存入数组，编写函数返回指向最大元素的指针，在 main 中通过该指针打印最大值。

样例输入：

5
3 9 2 9 4

样例输出： 9

思路： 函数遍历数组，记录最大元素的地址并返回。

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

int* findMax(int* arr, int n) {
    int* best = arr;        // 先假设第一个最大
    for (int i = 1; i < n; i++) {
        if (arr[i] > *best) best = &arr[i];
    }
    return best;            // 返回指向最大元素的指针
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int* p = findMax(a.data(), n);  // a.data() 拿到底层数组指针
    cout << *p << "\n";
    return 0;
}

关键点：

• 返回的是「指向数组内某元素」的指针，数组还活着，所以安全（不是返回局部变量地址！）
• a.data()——vector 提供底层连续数组的首指针
• best 始终保存当前最大元素的地址

题目 2.7.5 — 用指针就地翻转数组 读入 N 个整数，用两个指针（一个从头、一个从尾）就地翻转数组并打印。

样例输入：

5
1 2 3 4 5

样例输出： 5 4 3 2 1

思路： 双指针，从两端向中间交换，正是第 2.3 章翻转算法的指针版。

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int* left = &a[0];
    int* right = &a[n - 1];
    while (left < right) {       // 指针可以直接比较大小
        swap(*left, *right);
        left++;
        right--;
    }

    for (int x : a) cout << x << " ";
    cout << "\n";
    return 0;
}

关键点：

• 同一数组内的指针可以用 <、> 比较位置
• left++ / right-- 让指针按元素前进/后退
• 循环条件 left < right 保证在中点相遇时停止

题目 2.7.6 — 手写链表求和 不用 vector，用 struct Node{int data; Node* next;} 手动建立一条包含 N 个整数的链表，遍历求和后打印。

样例输入：

4
10 20 30 40

样例输出： 100

思路： 边读边在尾部接新节点，再从头遍历求和。

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

struct Node {
    int data;
    Node* next;
};

int main() {
    int n;
    cin >> n;

    Node* head = nullptr;
    Node* tail = nullptr;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        Node* node = new Node{x, nullptr};
        if (head == nullptr) {      // 第一个节点
            head = tail = node;
        } else {
            tail->next = node;      // 接到尾部
            tail = node;            // 更新尾指针
        }
    }

    long long sum = 0;
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        sum += cur->data;
    }
    cout << sum << "\n";

    // 释放
    while (head) { Node* t = head; head = head->next; delete t; }

    return 0;
}

关键点：

• 用 head 和 tail 两个指针，尾插法 O(1) 接节点
• cur = cur->next 是链表遍历的标准写法
• 用完逐个 delete（竞赛中可省，程序结束自动回收）

🏆 挑战题

挑战 2.7.7 — 反转链表 （经典面试 & 竞赛基础题）

建立一条链表 1→2→3→4→5，反转它使之变成 5→4→3→2→1，然后打印。要求只用指针操作，不借助数组。

期望输出： 5 4 3 2 1

思路： 三指针法——prev、cur、next。每步把 cur->next 反指向 prev，然后三个指针整体右移。

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

struct Node {
    int data;
    Node* next;
};

int main() {
    // 建立 1→2→3→4→5
    Node* head = nullptr;
    for (int i = 5; i >= 1; i--) {   // 倒着头插，得到正序
        head = new Node{i, head};
    }

    // 反转
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        Node* next = cur->next;  // 1. 先存住下一个
        cur->next = prev;        // 2. 当前节点反指向前一个
        prev = cur;              // 3. prev 前进
        cur = next;              // 4. cur 前进
    }
    head = prev;                 // prev 成为新的头

    // 打印
    for (Node* p = head; p; p = p->next) cout << p->data << " ";
    cout << "\n";

    return 0;
}

关键点：

• 反转链表的核心是「先用 next 备份下一个，再改 cur->next 的指向」，顺序不能乱，否则链断了找不回来
• 三指针 prev / cur / next 同步右移，O(N) 时间、O(1) 额外空间
• 这道题是理解指针操作的「试金石」，务必亲手画图走一遍

挑战 2.7.8 — 检测链表是否有环 （快慢指针经典应用）

给定一条可能成环的链表，判断它是否有环。打印 YES 或 NO。

提示：用「快慢指针」——慢指针每次走 1 步，快指针每次走 2 步。若两者相遇则有环（这叫 Floyd 判圈算法）。

思路： 快慢指针。若无环，快指针会先到达 nullptr；若有环，快指针会在环里追上慢指针。

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

struct Node {
    int data;
    Node* next;
};

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;          // 慢：走 1 步
        fast = fast->next->next;    // 快：走 2 步
        if (slow == fast) return true;  // 相遇 → 有环
    }
    return false;   // fast 到达末尾 → 无环
}

int main() {
    // 构造 1→2→3→4，再让 4 指回 2 形成环
    Node* n1 = new Node{1, nullptr};
    Node* n2 = new Node{2, nullptr};
    Node* n3 = new Node{3, nullptr};
    Node* n4 = new Node{4, nullptr};
    n1->next = n2; n2->next = n3; n3->next = n4;
    n4->next = n2;   // 制造环！

    cout << (hasCycle(n1) ? "YES" : "NO") << "\n";  // YES
    return 0;
}

关键点：

• 循环条件 fast && fast->next 必须双重判空——因为 fast 一次走两步，要确保 fast->next->next 不越过空指针
• 快慢指针是处理链表环、找中点、找倒数第 K 个节点的通用利器
• 若有环，快指针每轮比慢指针多走 1 步，最终必在环内相遇——时间 O(N)，空间 O(1)

挑战 2.7.9 — 奶牛排队（USACO Bronze 风格） （用链表 + 指针模拟动态插队）

Farmer John 的 N 头奶牛排成一队（编号 1..N，从队首到队尾）。接着发生 M 个事件，每个事件形如 x y：表示编号 x 的奶牛插队到编号 y 的奶牛正后方（保证 x、y 不同，且 x 当前在队中、会先被移出原位再插入）。所有事件处理完后，从队首到队尾输出整个队列。

样例输入：

4 2
2 4
1 3

（初始队列 1 2 3 4；事件1：2 插到 4 后 → 1 3 4 2；事件2：1 插到 3 后 → 3 1 4 2）

样例输出： 3 1 4 2

思路： 频繁的「移出 + 插入」正是双向链表的拿手好戏——它能 O(1) 完成任意位置的删除和插入，而数组做这件事要 O(N) 搬移。这里用数组模拟双向链表（竞赛主流写法，呼应 2.7.7 的对照表）：pre[i] 和 nxt[i] 分别存编号 i 左右邻居，用哨兵 0 表示队首之前/队尾之后。

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

const int N = 100005;
int pre[N], nxt[N];   // pre[i]/nxt[i]：编号 i 的前驱/后继；0 为哨兵（队首端/队尾端）

void detach(int x) {          // 把 x 从当前位置摘下
    nxt[pre[x]] = nxt[x];
    pre[nxt[x]] = pre[x];
}
void insertAfter(int y, int x) {  // 把 x 插到 y 的正后方
    int z = nxt[y];           // y 原来的后继
    nxt[y] = x; pre[x] = y;
    nxt[x] = z; pre[z] = x;
}

int main() {
    int n, m;
    cin >> n >> m;

    // 初始队列 1 2 ... n，用哨兵 0 串起两端
    pre[1] = 0; nxt[0] = 1;       // 0 → 1
    for (int i = 1; i < n; i++) { nxt[i] = i + 1; pre[i + 1] = i; }
    nxt[n] = 0; pre[0] = n;       // n → 0（回到哨兵，表示队尾）

    while (m--) {
        int x, y;
        cin >> x >> y;
        detach(x);            // 先把 x 移出原位
        insertAfter(y, x);    // 再插到 y 后面
    }

    // 从哨兵后第一个节点开始，沿 nxt 输出整条队列
    for (int i = nxt[0]; i != 0; i = nxt[i]) {
        cout << i << (nxt[i] ? " " : "\n");
    }
    return 0;
}

关键点：

• 为什么用链表不用数组？ 数组插队要把后面所有元素后移，单次 O(N)，M 次就是 O(NM)；双向链表删除+插入都是 O(1)，总计 O(N+M)，N、M 达 10^5 时差距巨大
• 哨兵 0 让队首/队尾不必特判：nxt[0] 是真正队首，pre[0] 是真正队尾
• 这里以编号本身作下标（编号即「指针」），是数组模拟链表的典型用法——和 2.7.7 的对照表完全一致
• detach 必须在 insertAfter 之前，否则 x 的旧邻居关系还没断开

题目 2.7.10 — 用指针实现 myStrlen （指针遍历C风格字符串的经典练习）

不使用任何库函数，用纯指针操作实现 int myStrlen(const char* s)，返回字符串长度（不含 \0）。在 main 中测试。

期望输出（输入 "hello"）： 5

思路： 指针从首字符出发，逐字符前进，遇到 \0 停止。走过的步数就是长度。

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

int myStrlen(const char* s) {
    int len = 0;
    while (*s != '\0') {  // 等价于 while (*s)
        len++;
        s++;              // 指针前进到下一个字符
    }
    return len;
}

int main() {
    const char* s = "hello";
    cout << myStrlen(s) << "\n";  // 5
    return 0;
}

关键点：

• *s 解引用取当前字符；s++ 让指针前进（指针算术）
• 循环条件 *s != '\0'——C 风格字符串以 \0 标记结尾
• 这个练习让你体会「指针 + 循环 = 字符串操作」的本质

题目 2.7.11 — 用指针实现 myStrcpy （指针赋值的经典练习）

不使用任何库函数，用纯指针操作实现 void myStrcpy(char* dst, const char* src)，将 src 指向的字符串完整复制到 dst。在 main 中测试。

期望输出（输入 "world"）： world

思路： 两个指针同步前进，逐字符赋值，最后手动补 \0。

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

void myStrcpy(char* dst, const char* src) {
    while (*src != '\0') {
        *dst = *src;   // 逐字符赋值
        dst++;
        src++;
    }
    *dst = '\0';       // 别忘了末尾的 '\0'！
}

// 精简版（理解原理后再看）：
void myStrcpyV2(char* dst, const char* src) {
    while ((*dst++ = *src++));  // 赋值 + 判断 + 前进，一体完成
}

int main() {
    const char* src = "world";
    char dst[100];
    myStrcpy(dst, src);
    cout << dst << "\n";  // world
    return 0;
}

关键点：

• const char* src——源字符串用 const 修饰，防止误修改
• 必须手动追加 \0，否则 dst 不是合法的 C 字符串
• 精简版 (*dst++ = *src++) 利用后置 ++：先赋值再指针前进，循环到赋值结果为 \0 时自动停止

题目 2.7.12 — 合并两个有序链表 （经典指针操作，面试高频题）

给定两条升序链表 L1 和 L2，将它们合并成一条新的升序链表并返回头指针。要求只修改指针，不新建节点（即不能用 new）。

样例输入（两条链表）： 1→3→5 和 2→4→6 样例输出： 1 2 3 4 5 6

思路： 用一个「哨兵」哑节点（dummy）简化头处理，维护一个尾指针 tail。每次比较两条链表的当前头节点，把较小的摘下来接到 tail 后面，被摘的那条链表头指针前进。最后把剩余部分直接接上。

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

struct Node {
    int data;
    Node* next;
};

Node* mergeTwoLists(Node* l1, Node* l2) {
    Node dummy{0, nullptr};       // 哑节点，简化头部处理
    Node* tail = &dummy;          // tail 始终指向结果链表的尾

    while (l1 != nullptr && l2 != nullptr) {
        if (l1->data < l2->data) {
            tail->next = l1;      // 摘 l1 当前节点
            l1 = l1->next;        // l1 前进
        } else {
            tail->next = l2;      // 摘 l2 当前节点
            l2 = l2->next;        // l2 前进
        }
        tail = tail->next;        // tail 始终保持在尾部
    }

    // 把剩余的链表直接接上（最多一条非空）
    tail->next = (l1 != nullptr) ? l1 : l2;

    return dummy.next;            // 跳过哑节点，返回真正的头
}

int main() {
    // 构建 L1: 1→3→5
    Node* l1 = new Node{1, new Node{3, new Node{5, nullptr}}};
    // 构建 L2: 2→4→6
    Node* l2 = new Node{2, new Node{4, new Node{6, nullptr}}};

    Node* merged = mergeTwoLists(l1, l2);

    for (Node* p = merged; p; p = p->next)
        cout << p->data << " ";
    cout << "\n";  // 1 2 3 4 5 6

    return 0;
}

关键点：

• 哑节点（dummy node） 是链表题的经典技巧——避免当头节点为空时的特判
• tail 始终保持指向结果链表的最后一个节点，接新节点时 O(1)
• 指针操作的核心：改了 tail->next 后必须同步更新 tail 和被摘链表的头指针
• 这是合并（Merge）、链表归并排序（Merge Sort）的基础子操作

题目 2.7.13 — 找链表的中间节点 （快慢指针的又一经典应用）

给定一条单链表，用快慢指针找到它的中间节点。如果长度为偶数，返回第二个中间节点。

样例输入： 1→2→3→4→5 样例输出： 3（第 3 个节点是中间）

样例输入： 1→2→3→4 样例输出： 3（偶数长度，返回靠后的中间节点）

思路： 慢指针每次走 1 步，快指针每次走 2 步。当快指针到达末尾时，慢指针正好在中点。

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

struct Node {
    int data;
    Node* next;
};

Node* findMiddle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;          // 慢：1 步
        fast = fast->next->next;    // 快：2 步
    }
    return slow;  // fast 到末尾时，slow 就是中点
}

int main() {
    // 测试 1: 1→2→3→4→5（奇数）
    Node* head1 = new Node{1, new Node{2, new Node{3,
                        new Node{4, new Node{5, nullptr}}}}};
    cout << findMiddle(head1)->data << "\n";  // 3

    // 测试 2: 1→2→3→4（偶数）
    Node* head2 = new Node{1, new Node{2, new Node{3,
                        new Node{4, nullptr}}}};
    cout << findMiddle(head2)->data << "\n";  // 3

    return 0;
}

关键点：

• 快慢指针是处理链表「中点」「倒数第 K 个」「环检测」的通用利器，时间 O(N)、空间 O(1)
• 循环条件 fast && fast->next——因为快指针一次走两步，两个判空缺一不可
• 当 fast == nullptr（奇数长度）或 fast->next == nullptr（偶数长度）时循环退出，slow 恰好在中点
• 如果想要第一个中间节点（偶数长度时返回靠前那个），可以让快指针先走一步：fast = head->next

🔗 USACO 真题练手

本章的指针 / 链表思想直接对应下面这些 USACO 官方真题。建议先用本章的「指针版」或「数组模拟版」实现，再去 usaco.org 提交验证：

💡 解题提示：

• Reordering the Cows：每头牛要从位置 i 走到目标位置，沿着「当前牛该去哪、那个位置原来的牛又该去哪」一路跟踪，就会走出一个个「环」。这种「顺着指向一路跳」的遍历，和链表遍历、Floyd 判圈是同一种思维。
• Cow Line：左右两端都要 O(1) 增删，标准做法是双端队列。理解了本章的双向链表（pre / nxt 两个方向的「指针」），你就能明白 deque 内部为什么能两端 O(1)。

📌 更系统的题单：USACO Guide 按难度和专题（含 Stacks/Queues、Linked Lists）整理了官方真题，是赛前刷题的权威路线图。

📖 第 2.8 章：枚举与模拟

2.8.0 从两道题出发

先看两道典型的 Bronze 题目——它们分别代表了本章的两大主题。

📋 题目 1：熄灯问题（简化版） 有一个 3×3 的灯阵，每个格子要么亮（1）要么灭（0）。现在灯全部亮着。 按下任意一个格子的开关，会翻转它自己和上下左右相邻格子的亮灭状态。 问：至少按多少次开关，才能把所有灯熄灭？ 数据范围： 3×3 灯阵，开关只有「按」和「不按」两种选择。

📋 题目 2：爬行的蠕虫 一只蠕虫在一口深 n 厘米的井底。每分钟它先向上爬 u 厘米， 如果这之后还没爬出井口，就向下滑 d 厘米（休息时滑落）。 问：多少分钟后蠕虫爬出井口？ 数据范围： 1 ≤ n, u, d ≤ 100，保证 u > d。

两道题，两种思路

熄灯问题：答案藏在「每个开关按或不按」的所有组合里——共 2⁹ = 512 种。把每种组合都试一遍，检查哪种能把灯全熄灭。这就是枚举：暴力搜索整个答案空间。

爬行的蠕虫：没有任何组合可选——过程是确定的，一分钟一分钟往下推就行。爬、检查、滑落，循环往复。这就是模拟：按题意忠实复现过程。

这两招是 Bronze 级别最朴素也最可靠的得分手段：

1. 枚举：答案空间有限时，把每个候选答案都验证一遍。不需要聪明，只需要不重不漏。
2. 模拟：题目描述了一个过程时，让计算机一步步照做。不需要算法，只需要不出错。

拆解本章需要回答的问题

学习目标（学完本章你将能够）：

1. 为一道题建立正确的「解空间模型」，做到不重不漏
2. 用三种手段缩小枚举空间：缩小范围、利用对称性、边枚举边排除
3. 掌握子集枚举（位运算 mask）与排列枚举（next_permutation）
4. 用「纸上流程 → 模块化 → 统一量纲」的方法写对大模拟题
5. 熟练处理日期、时间类模拟题（平闰年、大小月）
6. 使用「枚举决策 + 模拟验证」套路解决 USACO Bronze 常见的开关类问题

2.8.1 枚举（Enumeration）

什么是解空间？

解空间是「所有可能的答案（候选解）组成的集合」。枚举就是逐个检查候选解，把满足条件的挑出来。

比如：

• 「熄灯问题」的解空间 = 9 个开关每个按/不按，共 2⁹ = 512 种方案；
• 「三个数中选两个」的解空间 = C(3,2) = 3 种选法；
• 「1 到 n 的整数」的解空间就是 1, 2, ..., n。

枚举的正确性取决于两件事：完备（每个可行解都被访问到）与不重（同一方案不被统计两次）。而枚举的效率取决于解空间的大小——所以枚举的功夫全在「如何让解空间变小」上。

枚举三要点

1. 建立解空间模型：先把「候选答案到底是什么」想清楚，再动手写循环。是选一个数？选一对数？选一个子集？还是一组排列？
2. 减少枚举空间：
   • 缩小范围：利用数学关系直接收紧循环边界（如只需要枚举到 √n）；
   • 利用对称性：(a, b) 和 (b, a) 是同一方案时，只枚举 a ≤ b 的一半；
   • 边枚举边排除：一旦发现当前候选已经不可能，立即跳过（这是剪枝的雏形）。
3. 选择枚举顺序：有时按特定顺序枚举能提前找到答案（如求「字典序最小的方案」就按字典序枚举），有时能让「不重不漏」自然成立。

下面用一道题把三要点全部走一遍。

完整实战 1：和为零的数对

📋 题目：和为零的数对 给定 n 个整数，问其中有多少对数 (i, j)（i < j）满足 a[i] + a[j] = 0？ 数据范围： 1 ≤ n ≤ 10⁶，|a[i]| ≤ 10⁶。

第一步：建立解空间模型。 答案是一对下标 (i, j) 且 i < j——解空间是所有下标对，共 n(n−1)/2 个。

版本 1：朴素双重循环 O(n²)

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;

    long long cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)   // j 从 i+1 开始：天然保证 i < j
            if (a[i] + a[j] == 0) cnt++;

    cout << cnt << endl;
    return 0;
}

注意内层 j 从 i + 1 开始——这就是「利用对称性」：(i, j) 和 (j, i) 是同一对，只统计一次。如果写成 j 从 0 开始再判断 i < j，既慢又容易把「不重」写错。

样例验证：

输入：            输出：
5
3 -3 5 -5 2       2

(3, -3) 和 (5, -5) 共 2 对。

n = 10⁶ 时双重循环约 5×10¹¹ 次——超时。换模型：不要枚举数对，改为枚举每个数，问「它的相反数出现几次」。

版本 2：有序去半（排序 + 双指针思路的雏形）O(n log n)

先把数组排序，a[i] 的相反数如果存在，必然集中出现在某个连续段——用双指针可以在一轮扫描内统计完。这个思路在第 3 章双指针部分会展开，这里先看更彻底的版本 3。

版本 3：桶标记 O(n)

值域只有 |a[i]| ≤ 10⁶，开一个桶数组记录每个值出现的次数。扫描到 a[i] 时，之前的数里值为 -a[i] 的都能和它配对：

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

const int OFFSET = 1000000;   // 值域 [-1e6, 1e6] 平移到 [0, 2e6]
int bucket[2000001];

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;

    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        // 在「已经见过的数」中找 a[i] 的相反数
        if (-a[i] >= -1000000 && -a[i] <= 1000000)
            cnt += bucket[-a[i] + OFFSET];
        bucket[a[i] + OFFSET]++;   // 然后把自己也记入桶中
    }

    cout << cnt << endl;
    return 0;
}

先查再记的顺序很关键：如果先把自己记进桶再查，a[i] = 0 时会把自己和自己配对。

三版对比：

这条「朴素 O(n²) → 有序去半 → 桶标记 O(n)」的优化路径是枚举题的通用成长路线：先保证正确，再一步步压解空间。

完整实战 2：子集枚举——选数凑和

当候选答案是「从中挑出若干个数」时，解空间就是子集。n 个数的子集共 2ⁿ 个，正好对应 n 位二进制数——这正是第 2.6 章位运算中位掩码的用武之地。

📋 题目：选数凑和 给定 n 个整数和一个目标值 target，问有多少种非空选法，使得选出的数之和恰好等于 target？ 两种选法不同当且仅当选中的下标集合不同。 数据范围： 1 ≤ n ≤ 20，|a[i]| ≤ 10⁹，|target| ≤ 10⁹。

n ≤ 20 暗示 2²⁰ ≈ 10⁶——子集枚举的典型信号：

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

int main() {
    int n;
    long long target;
    cin >> n >> target;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;

    long long cnt = 0;
    for (int mask = 0; mask < (1 << n); mask++) {  // 枚举每个子集
        long long sum = 0;
        for (int i = 0; i < n; i++)
            if (mask & (1 << i)) sum += a[i];       // 第 i 位为 1 表示选它
        if (sum == target) cnt++;
    }

    cout << cnt << endl;
    return 0;
}

样例验证：

输入：            输出：
5 5
1 2 3 4 5         3

三种选法：{5}、{1,4}、{2,3}。

两个易错点：

• (1 << n) 中若 n ≥ 31 会溢出——好在 n ≤ 20 时 1 << 20 只有约 10⁶，安全；
• sum 用 long long：20 个 10⁹ 相加达 2×10¹⁰，int 必爆。

完整实战 3：排列枚举——密码锁

当候选答案是「顺序也有意义」时，解空间是排列。STL 的 next_permutation 按字典序逐个生成排列，是排列枚举的标准工具。

📋 题目：密码锁 一个三位密码锁由数字 1、2、3 各一个组成。从小到大列出所有可能的密码， 求第 k 个密码是什么。 数据范围： 1 ≤ k ≤ 6。

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

int main() {
    int k;
    cin >> k;
    string s = "123";
    sort(s.begin(), s.end());   // 必须先排成最小排列
    int idx = 1;
    do {
        if (idx == k) {
            cout << s << endl;
            return 0;
        }
        idx++;
    } while (next_permutation(s.begin(), s.end()));
    return 0;
}

样例验证： k = 4 输出 231（六种排列按字典序是 123、132、213、231、312、321）。

do-while 配合先排序是固定套路：next_permutation 在已经是最大排列时返回 false，从最小排列出发正好一个不漏。

枚举剪枝：预告

「边枚举边排除」的极端形式是：枚举到一半就发现此路不通，立刻回头换一条路——这就是回溯（剪枝）。它是第 5.2 章 BFS 与 DFS 的主角，也是子集枚举从 2ⁿ 走向更聪明搜索的必经之路。现在只需记住：枚举是回溯的骨架，剪枝是枚举的加速器。

2.8.2 模拟（Simulation）

模拟题的特征与心态

模拟题的标志是：题目把过程讲得一清二楚，你只需要照做。日期推算、游戏规则、机器执行、蚂蚁爬行……USACO Bronze 每场比赛几乎都有一道。

模拟题的特点是码量大、逻辑琐碎——难的不是想到做法，而是写对。正确的心理预期是：

模拟题不是比谁聪明，是比谁细心。把「我会了」和「我写对了」之间的距离，用工程习惯填平。

五大技巧

1. 先在纸上写流程：把题目过程翻译成伪代码步骤，每一步的变量变化列一个表。写代码之前手算一遍样例，纸面流程和样例对得上再动手。
2. 代码模块化：一个功能一个函数（或结构体）。「翻转一格灯」写成 flip(r, c)，「判断闰年」写成 isLeap(y)。模块短小、命名清楚，出错时定位快。
3. 统一量纲：时间统一换成秒、日期统一换成天数、金额统一换成「分」。所有比较和加减只在统一单位后进行，3 分 20 秒 与 200 秒 混用是模拟题最经典的 bug 来源。
4. 常量命名：大小月天数表、方向数组 dx/dy、一周七天名称……提取成 const 数组放在文件开头，魔法数字全部消灭。
5. 分块调试：每写完一个模块就用样例（或自造小数据）单独验证它，再拼装。一次只怀疑一个模块——这比盯着 200 行 main 找错高效十倍。系统方法见附录调试指南。

完整实战 1：爬行的蠕虫（开篇题回收）

按纸上流程走一遍：每分钟「先爬 u，若已出井口立即结束，否则下滑 d」——注意先判断后下滑的顺序，顺序反了会多算一分钟（出井口后不会滑落）。

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

int main() {
    long long n, u, d;
    cin >> n >> u >> d;

    long long pos = 0, minutes = 0;
    while (pos < n) {
        pos += u;            // 先爬
        minutes++;
        if (pos >= n) break; // 到顶就结束，不再下滑
        pos -= d;            // 没到顶，才滑落
    }

    cout << minutes << endl;
    return 0;
}

样例验证： n = 10, u = 2, d = 1 时，位置依次为 2→1、4→3、6→5、8→7、10（到顶）——输出 9 分钟。手算公式：第 k 分钟爬后位置 = ku − (k−1)d = k + 1，k = 9 时恰好为 10。✅

再验一组边界：n = 5, u = 5, d = 3——第一分钟直接爬到 5 出井，输出 1（下滑根本没发生）。

完整实战 2：日期模拟——N 天之后是几月几号

日期是模拟题的常客，考点全在平闰年和大小月上。

📋 题目：N 天之后 给定一个日期 y-m-d 和整数 n，求 n 天之后的日期。 数据范围： 1900 ≤ y ≤ 2100，日期合法，1 ≤ n ≤ 10000。

模块化 + 常量表的做法：

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

bool isLeap(int y) {
    return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
}

int daysOfMonth(int y, int m) {
    static const int d[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if (m == 2 && isLeap(y)) return 29;
    return d[m];
}

int main() {
    int y, m, d, n;
    cin >> y >> m >> d >> n;

    d += n;
    while (d > daysOfMonth(y, m)) {   // 当前月份装不下了就进位
        d -= daysOfMonth(y, m);
        m++;
        if (m > 12) {
            m = 1;
            y++;
        }
    }

    printf("%04d-%02d-%02d\n", y, m, d);
    return 0;
}

样例验证：

输入：2024 2 28 2     输出：2024-03-01   （2024 是闰年，2 月有 29 天）
输入：2023 2 28 2     输出：2023-03-02   （2023 是平年，2 月只有 28 天）
输入：2024 12 31 1    输出：2025-01-01   （跨年进位）

注意 daysOfMonth(y, m) 在 while 条件和循环体里各调用一次——月份进位后要重新查天数，写错这里（比如循环外缓存）跨月时必错。

完整实战 3：胜负判定表——win() 函数

很多游戏类模拟题的核心是一张「谁克谁」的判定表。以石头剪刀布为例：

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

char names[3][8] = {"Rock", "Paper", "Scissors"};   // 0=石头 1=布 2=剪刀

// 返回 1 表示 a 赢 b，-1 表示 a 输 b，0 平局
int win(int a, int b) {
    if (a == b) return 0;
    return (a - b + 3) % 3 == 1 ? 1 : -1;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << names[a] << " vs " << names[b] << ": ";
    int r = win(a, b);
    if (r == 1) cout << "first wins" << endl;
    else if (r == -1) cout << "second wins" << endl;
    else cout << "tie" << endl;
    return 0;
}

这里用了一个小巧的取模公式：把三种手势编号成环（石头 0 → 布 1 → 剪刀 2 → 石头 0），(a − b + 3) % 3 == 1 恰好表示「a 克 b」——比三行 if 更不容易写反。这套写法在 USACO 的「HPS（Hoop-Toss?）」石头剪刀布系列题（见第 6.2 章）中直接可用。

2.8.3 枚举 × 模拟：黄金套路

枚举决策 + 模拟验证

把两招合起来就是 Bronze 最强大的套路之一：

决策空间大但结构有规律时——枚举「第一步的所有决策」，剩下的过程用模拟推完。

开篇的熄灯问题正是如此。直接枚举 9 个开关的 2⁹ 种按法当然可行，但有一个更优雅的观察：

第 0 行的灯一旦确定按法，第 1 行怎么按就被唯一确定了——因为第 0 行还亮着的灯，只能靠按第 1 行正下方的开关来熄灭（第 0 行自己的开关已经定死了）。同理第 1 行确定后第 2 行也随之确定。

所以只需枚举第一行的 2³ = 8 种按法，剩下的 6 个开关由「逐行熄灭上方残留亮灯」的规则模拟推出来，最后检查最末行是否全灭即可：

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

int main() {
    int grid[3][3];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cin >> grid[i][j];   // 1=亮, 0=灭

    int best = INT_MAX;   // 最少按键数
    int bestMask = -1;    // 对应的第一行按法

    // 枚举第一行的按法：bit j = 1 表示按下 (0, j)
    for (int mask = 0; mask < 8; mask++) {
        int g[3][3], press[3][3];
        memcpy(g, grid, sizeof(grid));
        memset(press, 0, sizeof(press));
        int cnt = 0;

        // 第 0 行的按法由 mask 决定
        for (int j = 0; j < 3; j++)
            if (mask & (1 << j)) { press[0][j] = 1; cnt++; }

        // 应用第 0 行的按键：翻转自己和上下左右
        for (int j = 0; j < 3; j++)
            if (press[0][j]) {
                int di[] = {0, 0, 0, 1, -1};
                int dj[] = {0, 1, -1, 0, 0};
                for (int k = 0; k < 5; k++) {
                    int ni = di[k], nj = j + dj[k];
                    if (ni >= 0 && ni < 3 && nj >= 0 && nj < 3)
                        g[ni][nj] ^= 1;
                }
            }

        // 第 i 行还亮着的灯，只能靠按第 i+1 行正下方的开关熄灭
        for (int i = 0; i + 1 < 3; i++) {
            for (int j = 0; j < 3; j++)
                if (g[i][j] == 1) {
                    press[i + 1][j] = 1;
                    cnt++;
                }
            // 应用第 i+1 行新确定的按键
            for (int j = 0; j < 3; j++)
                if (press[i + 1][j]) {
                    int di[] = {0, 0, 0, 1, -1};
                    int dj[] = {0, 1, -1, 0, 0};
                    for (int k = 0; k < 5; k++) {
                        int ni = i + 1 + di[k], nj = j + dj[k];
                        if (ni >= 0 && ni < 3 && nj >= 0 && nj < 3)
                            g[ni][nj] ^= 1;
                    }
                }
        }

        // 最末行必须全灭，方案才成立
        bool ok = true;
        for (int j = 0; j < 3; j++)
            if (g[2][j] == 1) { ok = false; break; }

        if (ok && cnt < best) {
            best = cnt;
            bestMask = mask;
        }
    }

    if (bestMask < 0) {
        cout << "无解" << endl;
    } else {
        cout << "最少按键 " << best << " 次" << endl;
        cout << "第一行按法(列0到2): ";
        for (int j = 0; j < 3; j++)
            cout << ((bestMask >> j) & 1);
        cout << endl;
    }
    return 0;
}

样例验证： 输入全亮的 3×3（1 1 1 / 1 1 1 / 1 1 1），输出：

最少按键 5 次
第一行按法(列0到2): 101

即按下四角加中心共 5 个开关——这与 2⁹ 全枚举对拍的结果一致（本程序的答案已用 512 种初始状态逐一和暴力全枚举对拍验证过）。

为什么这个套路如此常见？

• 枚举量从 2⁹ 降到 2³——枚举空间被「逐行确定」的结构压缩了；
• 枚举之后的每一步都是机械的模拟——正确性由「照做」保证；
• 更妙的是，枚举第一行按法时顺便得到了「按键最少」的方案——枚举顺序不影响正确性，但影响能不能顺手求最优。

USACO Bronze 的「关灯」「按行染色」「翻硬币」系列题全是这个模板：枚举第一行的全部决策 → 逐行模拟确定后续 → 检查最后一行。把 3×3 推广到 R×C（第一行按法 2^C 种），就是完整的 USACO 真题规模。

⚠️ 常见错误

调试建议

模拟题写完之后，按这个清单自造数据检查：

1. 最小规模：n = 1、只有一行、只有一分钟——边界循环体是否还正确？
2. 刚好卡边界：蠕虫第一分钟就出井；日期加 0 天；子集只选第一个数。
3. 跨段进位：日期跨月、跨年；蠕虫整除到顶。
4. 对拍：写一个朴素暴力版（如 2⁹ 全枚举），用小数据随机对拍——这是验证枚举题的终极手段。

本章小结

本章最重要的思想可以总结为两句话：

1. 枚举的功夫在解空间：建对模型 → 压缩空间（缩范围 / 用对称 / 边排除）→ 选好顺序。
2. 模拟的功夫在工程：纸上流程、模块化、统一量纲、常量命名、分块调试——用习惯换正确率。

速查表

枚举 × 模拟黄金套路：
枚举第一行的所有决策（2^C 种）
  → 逐行模拟：上一行的亮灯决定本行的按法
  → 检查最后一行是否满足条件

💪 练习题

🟢 题目 1：虫群计数

题目描述：

给定 n 个整数，问其中有多少对 (i, j)（i < j）满足 a[i] + a[j] == 10？

数据范围： 2 ≤ n ≤ 1000，0 ≤ a[i] ≤ 10。

输入格式：

第一行一个整数 n
第二行 n 个整数 a[1..n]

输出格式：

一个整数，表示满足条件的数对数量

样例输入：

5
3 7 5 5 10

样例输出：

3

提示： 直接用本章的双重循环 O(n²) 就够了（n ≤ 1000 时约 10⁶ 次）。配对有 (3,7)、(5,5)、(5,5) 共 3 对——注意下标不同、值相同的两对要分别计数。

🟢 题目 2：日期差

题目描述：

给定两个日期，求它们之间相差多少天（含首尾两端中的较早日期、不含较晚日期，即「从日期 1 走到日期 2 需要多少天」）。

数据范围： 两个日期均在 1900-01-01 到 2100-12-31 之间且合法，保证日期 1 不晚于日期 2。

输入格式：