第 1 章：C++ 从零开始

针对有 C 语言基础的学生，快速掌握竞赛中常用的 C++ 特性。

---

1.1 为什么要学 C++

在 ACM 竞赛中，C++ 是绝对的主流语言。但你不需要学完所有 C++ 特性——竞赛中我们把 C++ 当做 "更好的 C" 来用。

C++ 在竞赛中的核心优势

优势	说明	示例
STL 标准模板库	提供大量现成的数据结构和算法	vector、sort、map
更方便的 I/O	cin/cout 不需要格式符	不用记 %d、%lld 等
string 类	字符串操作变得极其简单	s1 + s2 拼接，s.size() 取长度
引用传递	比指针更安全简洁	void f(int &x)
函数重载	同名函数处理不同类型	max(int, int) 和 max(double, double)
模板	写一次代码适用于多种类型	template<typename T>
bool 类型	布尔值语义清晰	bool vis[100]
auto 关键字	自动推导类型	auto it = s.begin()

竞赛中用到的 C++ 特性占比

• 输入输出（cin/cout/printf/scanf）：必用
• STL（容器 + 算法）：核心，占 80% 的便利
• string 类：高频
• 引用、函数重载、模板：中频
• 类与对象：偶尔用（自己封装数据结构时）
• 继承、多态、虚函数：几乎不用

---

1.2 C vs C++ 关键区别

1.2.1 输入输出：cin / cout

C 语言使用 scanf 和 printf，需要记住格式符。C++ 提供了更简洁的 cin 和 cout。

#include <iostream>
using namespace std;

int main() {
    // ---- C 风格 ----
    int a;
    double b;
    char s[100];
    scanf("%d %lf %s", &a, &b, s);  // 需要取地址，需要格式符
    printf("%d %.2f %s\n", a, b, s);

    // ---- C++ 风格 ----
    int x;
    double y;
    string str;
    cin >> x >> y >> str;   // 不需要取地址，不需要格式符
    cout << x << " " << y << " " << str << endl;

    return 0;
}

cin/cout 的特点

• cin >> a 自动根据变量类型读取，不需要 %d、%lf 等格式符
• cout << a 自动根据变量类型输出
• endl 相当于 \n + 刷新缓冲区
• 多个值可以用 << 或 >> 连接，非常方便

1.2.2 string 类（告别 char 数组）

#include <iostream>
#include <string>
#include <cstring>  // strcpy/strcat/strlen/strcmp 需要这个头文件
using namespace std;

int main() {
    // ---- C 风格字符串（繁琐）----
    char s1[100] = "hello";
    char s2[100] = "world";
    char s3[200];
    strcpy(s3, s1);         // 复制
    strcat(s3, s2);         // 拼接
    int len = strlen(s1);   // 求长度
    int cmp = strcmp(s1, s2); // 比较

    // ---- C++ string（简洁）----
    string a = "hello";
    string b = "world";
    string c = a + b;       // 拼接，直接用 +
    int len2 = a.size();    // 求长度
    // 比较直接用 ==, <, > 等运算符
    if (a < b) {
        cout << "a < b" << endl;
    }

    // string 的更多便利操作
    string s = "abcdef";
    cout << s[0] << endl;        // 访问单个字符: a
    cout << s.substr(1, 3) << endl; // 子串: bcd（从位置1开始，长度3）
    cout << s.find("cd") << endl;   // 查找子串: 返回位置2

    // 读取一整行（包含空格）
    string line;
    getline(cin, line);  // 读取一整行
    cout << line << endl;

    return 0;
}

1.2.3 bool 类型

#include <iostream>
using namespace std;

int main() {
    // C 语言中通常用 int 表示真假
    int flag_c = 1;  // 1 表示真

    // C++ 有专门的 bool 类型
    bool flag = true;   // true 就是 1
    bool flag2 = false; // false 就是 0

    // 实际用途：标记数组
    bool visited[100] = {false};  // 初始化为全部 false
    visited[5] = true;

    // bool 可以直接输出
    cout << flag << endl;   // 输出 1
    cout << flag2 << endl;  // 输出 0

    // 如果想输出 true/false
    cout << boolalpha << flag << endl;  // 输出 true

    return 0;
}

1.2.4 引用（Reference）

引用是 C++ 中非常重要的概念，它相当于变量的"别名"。在竞赛中，引用主要用于函数参数传递，避免拷贝大对象。

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

// ---- 不用引用：值传递，会复制整个 string ----
void bad_print(string s) {
    cout << s << endl;
    // 修改 s 不会影响原变量
}

// ---- 用引用：直接操作原变量，不复制 ----
void good_print(const string &s) {
    cout << s << endl;
    // const 表示不会修改 s
}

// ---- 用引用修改变量 ----
void swap_ref(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

// ---- 对比：用指针实现交换（C 风格）----
void swap_ptr(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main() {
    int x = 10, y = 20;

    // 引用传递（简洁）
    swap_ref(x, y);
    cout << x << " " << y << endl;  // 20 10

    // 指针传递（繁琐）
    swap_ptr(&x, &y);
    cout << x << " " << y << endl;  // 10 20

    // 引用在读取大对象时的用法
    string long_str = "这是一个很长很长的字符串...";
    good_print(long_str);  // 不会复制，效率高

    return 0;
}

引用 vs 指针

特性	引用 &	指针 *
语法	int &a = x	int *p = &x
使用	直接用 a	需要解引用 *p
是否可为空	不可以	可以 nullptr
能否重新绑定	不可以	可以
竞赛常用场景	函数参数	链表/树的指针

1.2.5 函数重载

C++ 允许同名函数有不同的参数列表，编译器会自动选择匹配的版本。

#include <iostream>
using namespace std;

// 函数重载：同名函数，不同参数类型或个数
int max_val(int a, int b) {
    return a > b ? a : b;
}

double max_val(double a, double b) {
    return a > b ? a : b;
}

int max_val(int a, int b, int c) {
    return max_val(max_val(a, b), c);
}

int main() {
    cout << max_val(3, 5) << endl;         // 调用 int 版本: 5
    cout << max_val(3.14, 2.72) << endl;   // 调用 double 版本: 3.14
    cout << max_val(1, 2, 3) << endl;      // 调用三参数版本: 3
    return 0;
}

1.2.6 auto 关键字

auto 让编译器自动推导变量类型，在使用 STL 迭代器时特别方便。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    // auto 自动推导类型
    auto a = 10;           // 推导为 int
    auto b = 3.14;         // 推导为 double
    auto c = "hello";      // 推导为 const char*
    auto d = string("hi"); // 推导为 string

    // 最大用途：简化 STL 迭代器声明
    vector<int> v = {1, 2, 3, 4, 5};

    // 不用 auto（啰嗦）
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 用 auto（简洁）
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // map 中 auto 更方便
    map<string, int> mp;
    mp["hello"] = 1;
    mp["world"] = 2;

    for (auto &p : mp) {
        cout << p.first << " -> " << p.second << endl;
    }

    return 0;
}

---

1.3 C++ 的 I/O 优化

为什么需要优化？

默认情况下，C++ 的 cin/cout 比 C 的 scanf/printf 慢很多。在竞赛中，数据量可能达到 10^6 级别，如果不优化 I/O，可能会 超时（TLE）。

#include <iostream>
using namespace std;

int main() {
    // 关键：关闭 C++ 和 C 的 I/O 同步
    ios::sync_with_stdio(false);
    // 关键：解除 cin 和 cout 的绑定
    cin.tie(nullptr);

    // 之后使用 cin/cout 就和 scanf/printf 速度接近了

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cout << x << "\n";  // 注意：用 "\n" 而不是 endl
    }

    // endl 会刷新缓冲区，比 "\n" 慢
    // 竞赛中统一用 "\n" 即可

    return 0;
}

注意事项

开启 ios::sync_with_stdio(false) 后，不要混用 cin/cout 和 scanf/printf，否则可能导致输出顺序错乱。

竞赛中 I/O 的选择策略

场景	推荐方式	原因
一般题目	cin/cout + 优化	简洁方便
大量输入输出（>10^5）	scanf/printf	最稳妥
超大量输入（>10^6）	快读（手写 getchar）	最快
需要格式化输出	printf	格式控制更方便

快速读入模板（进阶）

当数据量非常大时，手写快读是最快的：

#include <cstdio>
using namespace std;

// 快速读入整数：通过 getchar 逐字符读取
inline int read() {
    int x = 0, f = 1;  // f 用于处理负数
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * f;
}

int main() {
    int n = read();  // 读入一个整数
    for (int i = 0; i < n; i++) {
        int x = read();
        printf("%d\n", x);
    }
    return 0;
}

---

1.4 动态内存：new / delete

1.4.1 new 和 delete 基础

在竞赛中，动态分配内存最常用的是数组。虽然我们通常用 vector，但了解 new/delete 有助于理解底层。

#include <iostream>
#include <cstdlib>  // malloc/free 需要这个头文件
using namespace std;

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

    // ---- C 风格：malloc/free ----
    int *a = (int *)malloc(n * sizeof(int));
    // 使用...
    free(a);

    // ---- C++ 风格：new/delete ----
    int *b = new int[n];  // 分配 n 个 int 的数组
    for (int i = 0; i < n; i++) {
        b[i] = i * 2;
    }
    delete[] b;  // 释放数组用 delete[]

    // 单个对象
    int *p = new int(42);  // 分配一个 int，初始值为 42
    cout << *p << endl;    // 输出 42
    delete p;              // 释放单个对象用 delete

    return 0;
}

new/delete 的注意事项

• new[] 对应 delete[]，new 对应 delete，不要混用
• 忘记 delete 会导致内存泄漏
• 在竞赛中，程序结束后操作系统会回收内存，所以通常不会造成问题
• 推荐用 vector 替代手动 new/delete

1.4.2 为什么竞赛中推荐用 vector

#include <iostream>
#include <vector>
using namespace std;

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

    // vector 自动管理内存，不需要手动 new/delete
    vector<int> v(n);  // 创建大小为 n 的动态数组

    for (int i = 0; i < n; i++) {
        v[i] = i;
    }

    // vector 可以动态增长
    v.push_back(100);  // 在末尾添加元素
    cout << v.size() << endl;  // 输出 n+1

    // vector 离开作用域时自动释放内存
    return 0;
}

---

1.5 类与对象基础

在竞赛中，我们很少使用复杂的面向对象特性。但有时自己封装一个数据结构（如线段树节点）会用到类。

#include <iostream>
#include <string>
#include <cmath>  // sqrt 需要这个头文件
using namespace std;

// 定义一个简单的"点"结构体
struct Point {
    int x, y;

    // 构造函数：创建对象时自动调用
    Point() : x(0), y(0) {}  // 默认构造
    Point(int x, int y) : x(x), y(y) {}  // 带参数构造

    // 成员函数
    double dist(const Point &other) const {
        int dx = x - other.x;
        int dy = y - other.y;
        return sqrt(dx * dx + dy * dy);
    }

    // 运算符重载：让 Point 可以直接比较
    bool operator<(const Point &other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }

    // 运算符重载：输出
    friend ostream& operator<<(ostream &os, const Point &p) {
        os << "(" << p.x << ", " << p.y << ")";
        return os;
    }
};

int main() {
    Point p1(3, 4);
    Point p2(1, 2);

    cout << p1 << endl;           // (3, 4)
    cout << p1.dist(p2) << endl;  // 2.82843

    // 因为重载了 <，Point 可以直接放入 set
    // set<Point> s;  // 这样就能用 set 存点，自动排序

    return 0;
}

struct vs class 在竞赛中的使用

• 竞赛中更常用 struct（默认 public），少用 class（默认 private）
• 封装数据时优先用 struct
• 需要运算符重载时（如放入 set 或 priority_queue），用 struct + operator<

---

1.6 模板基础

模板让我们写一次代码就能适用于多种类型，在竞赛中非常实用。

函数模板

#include <iostream>
using namespace std;

// 函数模板：适用于任意可比较类型
template<typename T>
T my_max(T a, T b) {
    return a > b ? a : b;
}

// 模板也可以有多个类型参数
template<typename T1, typename T2>
void print_pair(T1 a, T2 b) {
    cout << a << ", " << b << endl;
}

// 竞赛中常见的模板用途：快速定义数据结构
template<typename T>
struct Node {
    T data;
    Node *next;
    Node(T val) : data(val), next(nullptr) {}
};

int main() {
    // 自动推导类型
    cout << my_max(3, 5) << endl;        // int 版本: 5
    cout << my_max(3.14, 2.72) << endl;  // double 版本: 3.14
    cout << my_max('a', 'z') << endl;    // char 版本: z

    // 也可以显式指定类型
    cout << my_max<int>(10, 20) << endl;

    print_pair(1, "hello");   // T1=int, T2=const char*
    print_pair(3.14, 100);    // T1=double, T2=int

    return 0;
}

typename vs class

// 以下两种写法完全等价
template<typename T> T func1(T a) { return a; }
template<class T>    T func2(T a) { return a; }

// 竞赛中习惯用 typename

---

1.7 常见坑

1.7.1 整数溢出

这是竞赛中最常见的错误之一，尤其容易在计算乘法或求和时发生。

#include <iostream>
using namespace std;

int main() {
    // ---- 坑1：int 乘法溢出 ----
    int a = 100000;
    int b = 100000;

    // 错误！结果超出 int 范围（约 2*10^9）
    int wrong = a * b;
    cout << wrong << endl;  // 输出 1410065408（错误！）

    // 正确做法：用 long long
    long long correct = 1LL * a * b;  // 1LL 强制转为 long long
    cout << correct << endl;           // 输出 10000000000（正确）

    // ---- 坑2：中间结果溢出 ----
    int n = 100000;
    // 错误：n * (n + 1) 先用 int 计算，已经溢出
    int wrong_sum = n * (n + 1) / 2;

    // 正确：先转为 long long
    long long correct_sum = 1LL * n * (n + 1) / 2;
    cout << correct_sum << endl;

    return 0;
}

整数范围速查

类型	范围	大约位数
int	-2×10^9 ~ 2×10^9	约 10 位
long long	-9×10^18 ~ 9×10^18	约 19 位
unsigned int	0 ~ 4×10^9	约 10 位

竞赛经验：如果不确定是否会溢出，一律使用 long long。用 1LL * a * b 可以安全地将乘法结果转为 long long。

1.7.2 数组越界

#include <iostream>
using namespace std;

int main() {
    int n = 100;

    // ---- 坑1：数组大小不够 ----
    // 如果题目要求 n 最大为 100000
    // int a[100000];  // 如果 n 恰好等于 100000，访问 a[100000] 就越界了

    // 正确做法：开大一点
    const int MAXN = 100005;  // 多开 5~10 个空间
    int a[MAXN];

    // ---- 坑2：循环边界 ----
    // 常见错误：i <= n 访问 a[n]，但数组下标只到 n-1
    for (int i = 0; i < n; i++) {  // 正确：i < n
        a[i] = i;
    }

    // ---- 坑3：全局数组 vs 局部数组 ----
    // 在 main 函数内部开大数组可能栈溢出
    // int huge[10000000];  // 危险！可能段错误

    return 0;
}

// 解决方案1：放全局（在 main 外面）
const int N = 10000005;
int global_arr[N];  // 全局数组默认初始化为 0，在堆上

// 解决方案2：用 vector
// vector<int> v(10000000);  // 自动在堆上分配

竞赛中的数组大小经验

• 数组大小一般是题目给定上限的 1.1 ~ 2 倍
• 如果题目说 n <= 10^5，开 100005 或 200005
• 全局数组上限约 10^7 个 int（约 40MB），局部数组约 10^5（约 400KB）
• 竞赛中习惯把大数组开在全局

1.7.3 浮点精度

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    // ---- 坑1：浮点数比较不能用 == ----
    double a = 0.1 + 0.2;
    double b = 0.3;

    // 错误！由于精度问题，a 不严格等于 b
    if (a == b) {
        cout << "equal" << endl;   // 不会执行
    } else {
        cout << "not equal" << endl; // 会执行！
    }

    // 正确做法：用 eps（极小值）判断
    const double eps = 1e-9;
    if (fabs(a - b) < eps) {
        cout << "approximately equal" << endl;  // 正确
    }

    // ---- 坑2：整数除法 vs 浮点除法 ----
    int x = 5, y = 2;
    cout << x / y << endl;           // 输出 2（整数除法，截断小数）
    cout << (double)x / y << endl;   // 输出 2.5（浮点除法）

    // ---- 坑3：浮点数输出精度 ----
    double pi = 3.14159265358979;
    printf("%.10f\n", pi);  // 保留 10 位小数

    return 0;
}

浮点精度的经验

• 一般用 eps = 1e-9 作为精度比较的阈值
• 能用整数解决的问题，尽量不用浮点数
• 比较浮点数大小：fabs(a - b) < eps
• 判断浮点数为零：fabs(a) < eps

---

1.8 竞赛常用头文件和宏定义

常用头文件

// 万能头文件（包含几乎所有标准库）
// 注意：不是所有 OJ 都支持，Codeforces 支持，某些 OJ 不支持
#include <bits/stdc++.h>

// 或者手动包含常用头文件
#include <iostream>    // cin, cout
#include <cstdio>      // scanf, printf, getchar
#include <algorithm>   // sort, lower_bound, unique, reverse, next_permutation
#include <vector>      // vector 动态数组
#include <string>      // string 字符串
#include <map>         // map, multimap
#include <set>         // set, multiset
#include <queue>       // queue, priority_queue
#include <stack>       // stack
#include <cmath>       // sqrt, pow, fabs, ceil, floor
#include <cstring>     // memset, memcpy, strlen, strcmp
#include <climits>     // INT_MAX, INT_MIN, LLONG_MAX
#include <functional>  // greater<> 用于最小堆/升序排序

竞赛常用宏定义

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

// ---- 常用类型别名 ----
typedef long long ll;           // long long 简写
typedef pair<int, int> pii;    // 二元组简写
typedef vector<int> vi;        // 整数向量简写

// ---- 常用宏 ----
#define pb push_back           // vector 尾部添加
#define mp make_pair           // 创建 pair
#define fi first               // pair 的第一个元素
#define se second              // pair 的第二个元素
#define all(x) (x).begin(), (x).end()  // 所有元素的范围
#define sz(x) (int)(x).size()  // 容器大小

// ---- 常量 ----
const int INF = 0x3f3f3f3f;    // int 范围内的无穷大（约 10^9）
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;  // long long 范围的无穷大
const int MOD = 1e9 + 7;       // 常用模数
const double eps = 1e-9;       // 浮点精度

// ---- 快速 min/max（函数模板版）----
template<typename T> inline T mn(T x, T y) { return x < y ? x : y; }
template<typename T> inline T mx(T x, T y) { return x > y ? x : y; }

int main() {
    // 使用示例
    vi v = {3, 1, 4, 1, 5};
    sort(all(v));          // 排序
    cout << sz(v) << endl; // 输出 5

    pii p = mp(1, 2);
    cout << p.fi << " " << p.se << endl;  // 1 2

    return 0;
}

完整竞赛模板

这是一个可以直接复制到比赛中使用的模板：

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

// 类型别名
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

// 常用宏
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

// 常量
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;
const double eps = 1e-9;

// I/O 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

void solve() {
    // 在这里写解题逻辑
    int n;
    cin >> n;
    // ...
}

int main() {
    fast_io();

    int t = 1;
    // cin >> t;  // 多组测试数据时取消注释
    while (t--) {
        solve();
    }

    return 0;
}

模板的使用建议

• 把这个模板保存到一个文件中，比赛时直接复制粘贴
• 根据题目需要增删宏和头文件
• 不要过度依赖宏，保持代码可读性
• #define 的宏在竞赛中是为了节省打字时间，正式工程代码中建议避免

---

1.9 lambda 表达式与结构化绑定

后续章节的代码中会大量出现两种 C++ 现代语法：lambda 表达式（匿名函数）和 结构化绑定（auto [a, b] = ...）。它们不难，但如果没见过会觉得"这是什么语法"，所以在这里提前讲清楚。

1.9.1 lambda 表达式

lambda 就是"写在原地的匿名函数"。竞赛中最大的用途是：给 sort 等算法传自定义比较器时，不用再跑到 main 外面单独定义一个函数。

基本语法：

[捕获列表](参数列表) { 函数体 }
   |          |          |
   |          |          +-- 和普通函数一样写逻辑，可以有 return
   |          +-- 和普通函数的参数一样
   +-- 声明 lambda 内部要用到哪些外部变量

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

int main() {
    // ---- 最简单的 lambda：一个匿名函数 ----
    auto add = [](int a, int b) {
        return a + b;
    };
    cout << add(3, 4) << endl;  // 7

    // ---- 捕获外部变量 ----
    int k = 10;

    auto f1 = [k](int x) { return x + k; };   // 按值捕获：复制一份 k
    auto f2 = [&k](int x) { return x + k; };  // 按引用捕获：直接用外面的 k

    k = 100;
    cout << f1(1) << endl;  // 11（捕获时 k 还是 10）
    cout << f2(1) << endl;  // 101（引用捕获，看到的是最新的 k=100）

    // [=] 按值捕获所有用到的变量，[&] 按引用捕获所有用到的变量
    int a = 1, b = 2;
    auto f3 = [=]() { return a + b; };  // 3
    auto f4 = [&]() { a++; b++; };      // 修改外部的 a 和 b
    f4();
    cout << f3() << " " << a << " " << b << endl;  // 3 2 3

    // ---- 最常用的场景：作为 sort 的比较器 ----
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    // 降序排序：不用再到 main 外面写一个 cmp 函数
    sort(v.begin(), v.end(), [](int x, int y) {
        return x > y;
    });
    for (int x : v) cout << x << " ";  // 9 6 5 4 3 2 1 1
    cout << endl;

    // 按"到某个目标值的距离"排序：捕获让比较器能用上外部变量
    int target = 5;
    sort(v.begin(), v.end(), [target](int x, int y) {
        return abs(x - target) < abs(y - target);
    });
    for (int x : v) cout << x << " ";  // 5 排最前（距离 0）；距离相同的元素先后顺序不保证
    cout << endl;

    return 0;
}

复杂度：lambda 本身没有额外开销——编译器会把它变成一个内联的函数对象，用 lambda 的 sort 和用普通函数指针的 sort 一样是 O(n log n)，甚至常数更小（更容易内联）。

1.9.2 结构化绑定（C++17）

结构化绑定可以把 pair、tuple、数组、简单结构体"一次拆成多个变量"，最高频的用法是遍历 map。

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

int main() {
    // ---- 解包 pair ----
    pair<string, int> p = {"Alice", 90};
    auto [name, score] = p;  // name = "Alice", score = 90
    cout << name << " " << score << endl;

    // ---- 遍历 map（最高频的用法）----
    map<string, int> freq = {{"apple", 3}, {"banana", 5}, {"cherry", 7}};

    // C++17 之前：只能用 p.first / p.second
    for (auto &p : freq) {
        cout << p.first << " -> " << p.second << endl;
    }

    // C++17 结构化绑定：变量名一目了然
    for (auto &[word, cnt] : freq) {
        cout << word << " 出现 " << cnt << " 次" << endl;
    }

    // ---- 修改 map 的 value：用引用绑定 ----
    for (auto &[word, cnt] : freq) {
        cnt *= 2;  // 通过引用直接修改
    }
    cout << freq["apple"] << endl;  // 6

    // ---- 解包数组和 tuple ----
    int arr[2] = {10, 20};
    auto [x, y] = arr;
    cout << x + y << endl;  // 30

    tuple<int, string, double> t = {1, "Bob", 3.14};
    auto [id, who, val] = t;
    cout << id << " " << who << " " << val << endl;

    return 0;
}

1.9.3 例题：洛谷 P1093 [NOIP2007 普及组] 奖学金

题意：有 n（n ≤ 300）名学生，每人有语文、数学、英语三科成绩。按总分降序排名；总分相同按语文降序；再相同则学号小的在前。输出前 5 名的学号和总分。

这是"lambda 作为多关键字比较器"的标准应用：

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

struct Student {
    int id, chinese, total;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Student> stu(n);
    for (int i = 0; i < n; i++) {
        int chinese, math, english;
        cin >> chinese >> math >> english;
        stu[i] = {i + 1, chinese, chinese + math + english};
    }

    // lambda 比较器：总分降序 → 语文降序 → 学号升序
    sort(stu.begin(), stu.end(), [](const Student &a, const Student &b) {
        if (a.total != b.total) return a.total > b.total;
        if (a.chinese != b.chinese) return a.chinese > b.chinese;
        return a.id < b.id;
    });

    for (int i = 0; i < 5; i++) {
        cout << stu[i].id << " " << stu[i].total << "\n";
    }
    return 0;
}

复杂度 O(n log n)，n ≤ 300 随便过。样例输入 6 名学生时，输出 6 265 / 4 264 / 3 258 / 2 244 / 1 237。

lambda 与结构化绑定的常见坑

• 比较器必须是严格弱序：return a.total >= b.total; 这种带等号的写法是错的，两个相等元素会互相"小于"对方，sort 可能直接 RE（崩溃）。记住：相等时必须返回 false。
• 按值捕获是"拍快照"：[k] 捕获的是 lambda 定义那一刻的值，之后外部 k 再变，lambda 里看到的还是旧值。想同步就用 [&k]。
• 引用捕获的悬垂问题：如果 lambda 会在当前函数返回之后才被调用（竞赛中少见），不要用 [&] 捕获局部变量。
• 结构化绑定遍历 map 时记得 &：for (auto [k, v] : mp) 每轮都会拷贝一份键值对，改 v 也不会写回去；要修改或者避免拷贝，写 for (auto &[k, v] : mp)。
• 结构化绑定是 C++17 特性，交题时编译选项要选 C++17 及以上（主流 OJ 都支持）。

---

1.10 位运算基础

位运算直接在二进制位上做操作，速度极快（单条 CPU 指令），是状态压缩、树状数组、快速幂等后续内容的基础。这里先把最常用的部分讲清楚。

1.10.1 六种运算符与常用技巧

运算符	含义	示例（a=12 即 1100，b=10 即 1010）
a & b	按位与：都为 1 才为 1	1100 & 1010 = 1000（8）
a \| b	按位或：有 1 就为 1	1100 \| 1010 = 1110（14）
a ^ b	按位异或：不同为 1	1100 ^ 1010 = 0110（6）
~a	按位取反	~12 = -13（补码表示）
a << k	左移 k 位，相当于乘 2^k	12 << 2 = 48
a >> k	右移 k 位，相当于除 2^k 取整	12 >> 1 = 6

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

int main() {
    // ---- 技巧1：判断奇偶 ----
    int n = 7;
    if (n & 1) cout << n << " 是奇数" << endl;  // 最低位是 1 就是奇数

    // ---- 技巧2：取最低位的 1（lowbit）----
    int x = 12;               // 1100
    cout << (x & -x) << endl; // 100 = 4，树状数组的核心操作

    // ---- 技巧3：GCC/Clang 内建函数 ----
    unsigned int y = 44;                    // 101100
    cout << __builtin_popcount(y) << endl;  // 二进制中 1 的个数: 3
    cout << __builtin_ctz(y) << endl;       // 末尾 0 的个数: 2
    // long long 版本加后缀 ll：__builtin_popcountll / __builtin_ctzll

    // ---- 技巧4：对某一位的操作 ----
    int s = 0;
    s |= (1 << 3);                   // 把第 3 位设为 1
    cout << ((s >> 3) & 1) << endl;  // 取出第 3 位: 1
    s &= ~(1 << 3);                  // 把第 3 位清零
    s ^= (1 << 2);                   // 翻转第 2 位
    cout << s << endl;               // 4

    return 0;
}

复杂度：所有位运算都是 O(1)，__builtin_popcount 等内建函数通常对应单条硬件指令。

1.10.2 竞赛常见用途一览

用途	写法	出现场景
判断奇偶	n & 1	到处都是，比 n % 2 略快
取最低位 1（lowbit）	n & -n	树状数组（第 15 章）
第 k 位是否为 1	(n >> k) & 1	状态压缩 DP（第 10 章）
把第 k 位设为 1 / 清零	n \| (1 << k)、n & ~(1 << k)	状态压缩、标记集合
统计 1 的个数	__builtin_popcount(n)	集合大小、汉明距离
末尾 0 的个数	__builtin_ctz(n)	求 2 的幂次
乘 / 除 2 的幂	n << k、n >> k	快速幂、二分
枚举子集	for (int s = m; s; s = (s-1) & m)	状压 DP 子集枚举
不用临时变量交换	a ^= b; b ^= a; a ^= b;	了解即可，实战直接用 swap

1.10.3 例题：洛谷 P1100 高低位交换

题意：给一个 32 位无符号整数 n，把它的高 16 位与低 16 位交换，输出新数。例如输入 1314520，输出 249036820。

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

int main() {
    unsigned int n;
    cin >> n;
    // 高 16 位右移到低位，低 16 位左移到高位，再用 | 拼起来
    unsigned int ans = (n >> 16) | (n << 16);
    cout << ans << endl;
    return 0;
}

一行位运算解决，O(1)。注意必须用 unsigned int：无符号数左移溢出的位会被自然丢弃，且右移补 0，不会出现符号位问题。

位运算的常见坑

• 优先级极低：==、+ 都比 &、|、<< 高。if (n & 1 == 0) 实际是 n & (1 == 0)，恒为 0！位运算表达式永远加括号：if ((n & 1) == 0)。
• 1 << k 会溢出：1 是 int，1 << 40 是未定义行为。k 可能超过 30 时写 1LL << k。
• 负数右移：有符号负数右移是算术右移（补符号位），不等于除以 2 的幂的"向零取整"。涉及负数尽量避免用移位代替除法。
• __builtin_ctz(0) 是未定义行为，调用前保证参数非 0。

---

本章练习

• 用 cin/cout 重写你之前用 scanf/printf 写的程序
• 用 string 替代 char[] 实现字符串拼接和查找
• 用引用实现一个函数，交换两个 vector<int> 的内容
• 写一个函数模板，返回三个值中的最大值
• 整理一个自己的竞赛模板文件，保存为 template.cpp
• 用 long long 计算 100000 * 100000，验证结果正确

---

参考

• OI-Wiki - C++ 语言基础
• OI-Wiki - C++ 进阶
• 代码随想录 - C++ 基础