GESP C++ 三级系统自学讲义

课程定位：面向计算机编程三级（GESP Level 3）学员的系统化自学教材与实战讲义。
适用对象：已掌握 C++ 基本语法（顺序、分支、基础循环），希望系统攻克计算机底层数据编码、进位制转换、位运算微操、一维数组进阶、字符串处理、枚举算法与模拟算法的编程自学者。
教学特色：坚持“第一性原理”，拒绝死记硬背。从概念起源、数学直觉与内存图景出发，辅以步进手推表（Dry Run）、规范代码范式与经典例题精解，建立完整严密的算法与编程思维体系。

导言：GESP 三级学习路线与思维跃迁

欢迎进入 GESP 三级系统的学习殿堂！

在一级和二级阶段，你学习了变量、算术表达式、分支条件（if-else、switch）和循环语句（for、while）。那个阶段的核心任务是**“熟悉语法，把日常逻辑翻译成代码”**。

而从三级开始，你的编程学习将发生质的跃迁：

1. 向下扎根（理解计算机硬件与底层存储）：你将不再把数字当成抽象符号，而是看清它们在内存芯片中如何以由 0 和 1 构成的比特串（原码、反码、补码）存储与运算，理解位运算的纳秒级微操；
2. 向内筑基（掌握核心线性数据结构）：你将系统掌握一维数组与字符串对象，学会管理成百上千个连续排列的数据，掌握极值打擂、数据统计、模式检索与切片等核心操作；
3. 向上拓展（建立真正的算法思维）：你将学习计算机科学中最朴素却极其强大的两大经典算法——枚举算法与模拟算法，学会用穷举去穷尽空间、用状态变迁去复刻现实世界的运行规则。

               ┌─────────────────────────────────────────────────┐
               │              GESP 三级知识大厦架构               │
               └───────────────────────┬─────────────────────────┘
                                       │
        ┌──────────────────────────────┼──────────────────────────────┐
        ▼                              ▼                              ▼
 ┌──────────────┐              ┌──────────────┐              ┌──────────────┐
 │  底层原理篇  │              │ 核心结构篇   │              │ 算法思维篇   │
 ├──────────────┤              ├──────────────┤              ├──────────────┤
 │· 原码反码补码│              │· 一维数组应用│              │· 算法与流程图│
 │· 进位制转换  │              │· 字符串与文本│              │· 枚举算法优化│
 │· 比特级位运算│              │· 桶与频数统计│              │· 规则时序模拟│
 └──────────────┘              └──────────────┘              └──────────────┘

自学建议：

• 勿跳步：每一讲的代码请务必在 Dev-C++ 中亲手敲一遍，并尝试修改变量自己观察输出；
• 重手推：遇到算法推导，请准备好草稿纸，按照讲义中的“变量跟踪推演表”一步步手推，脑中建立清晰的内存画面。

第 1 讲 计算机内部的秘密——原码、反码与补码

本讲核心目标：理解计算机底层为什么只有加法器；掌握正负数在机器中的表示形式；吃透原码、反码、补码的推导法则；理解 8 位二进制数的范围为什么是 $-128 \sim +127$。

1.1 问题的引入：计算机只有加法器，减法怎么做？

我们在纸上计算减法很简单：$5 - 3 = 2$。 但是在真实的计算机 CPU 内部，硬件设计极其追求极简与高速。制造一个既能做加法又能做减法的“加减法器”，电路极其复杂且成本高昂。工程师们提出了一个天才的想法：能不能把减法变成加法？

$$5 - 3 = 5 + (-3)$$

如果能用一套统一的二进制编码，让加法电路把负数加进去之后，自然得出正确的结果，硬件电路就能省下一半的成本！这就是机器数编码诞生的起源。

生活中的直觉模型：时钟回拨与“模（Modulo）”

想象你手腕上的机械钟表，现在指针指向 6 点，你想让它指向 3 点，你有两种办法：

1. 倒拨 3 个小时：$6 - 3 = 3$（减法）；
2. 顺拨 9 个小时：$6 + 9 = 15$，而表盘满 12 就归零，$15 \pmod{12} = 3$（加法）！

在表盘这个系统里，减 3 和加 9 的效果是完全等价的！ 这里的 $12$ 就叫做**“模（Modulus）”，$9$ 就是 $-3$ 针对模 $12$ 的“补数（Complement）”**。

在有限位数的计算机存储单元里（例如 8 位 byte，满 $2^8 = 256$ 就会像表盘一样自然溢出归零），减去一个数，等价于加上它的补码！

1.2 机器数与真值：最高位的“符号位”

• 真值：日常生活中带正负号的数值，如 $+5, -5$；
• 机器数：在计算机中存储的形式，正负号也必须用 0 和 1 来表示。

在定长二进制数中，最高位（最左边的一位）被规定为符号位：

• 0 表示正数（Positive）；
• 1 表示负数（Negative）。 其余各位称为“数值位”。

1.3 原码（Sign-Magnitude）：最符合人类直觉的编码

定义：符号位加上数值本身的绝对值二进制。

以 8 位二进制为例：

• $+5$ 的原码：符号位为 0，数值 5 的二进制是 $0000101$，所以是 0000 0101
• $-5$ 的原码：符号位为 1，数值 5 的二进制是 $0000101$，所以是 1000 0101

原码的致命缺陷

如果直接用原码做加法，计算 $1 + (-1)$：

  0000 0001  (+1 的原码)
+ 1000 0001  (-1 的原码)
───────────
  1000 0010  (结果是 -2 的原码！计算完全错误！)

不仅如此，原码还存在两个 0：0000 0000 是 $+0$，1000 0000 是 $-0$。两个零在逻辑判断中会造成巨大的混乱。因此，原码不能直接参与计算机内部运算。

1.4 反码（One's Complement）：历史的过渡

为了尝试解决减法问题，先驱们设计了反码：

• 正数的反码：与原码完全相同；
• 负数的反码：符号位保持为 1 不动，数值位按位取反（0 变 1，1 变 0）。

以 8 位二进制为例：

• $+5$ 的反码：0000 0101
• $-5$ 的反码：原码是 1000 0101 $\to$ 符号位不变，后面 7 位翻转 $\to$ 1111 1010

反码可以计算某些加法，但仍然存在 $+0$（0000 0000）和 $-0$（1111 1111）并存的尴尬，且末位需要额外循环进位。

1.5 补码（Two's Complement）：现代计算体系的终极基石

在补码体系中，彻底消灭了“负零”，并且加减法完美统一！

补码变换规则（必须死死记住的核心）

规则 1：正数的原码、反码、补码完全相同！（三码合一）
规则 2：负数的补码 = 其反码 + 1。

                  数值位取反               最后一位加 1
负数原码 ───────────────────────> 负数反码 ───────────────────> 负数补码
(符号位为 1)     (符号位不变)               (逢二进一)

实战推演：求 $-5$ 的 8 位补码

1. 写绝对值 5 的二进制：000 0101；
2. 加上符号位写出原码：1000 0101；
3. 符号位不变，其余取反得到反码：1111 1010；
4. 反码末位加 1 得到补码：1111 1011。

检验时刻：用补码计算 $5 + (-5)$

  0000 0101  (+5 的补码)
+ 1111 1011  (-5 的补码)
───────────
1 0000 0000  (最高位溢出的 1 超出 8 位，被硬件自然丢弃)
= 0000 0000  (结果正好是 0！毫无偏差！)

极速技巧：从右往左看（考场 3 秒求补码）

口诀：从右往左数，找到第一个 1，这个 1 及其右边的所有 0 保持不变，该 1 左边的所有位（符号位除外）全部取反！

• $-5$ 原码：1 0 0 0 0 1 0 1 $\to$ 最右边的 1 在最后一位；
• 左边的数值位全部翻转 $\to$ 1 1 1 1 1 0 1 1，一步出结果！

1.6 数据的极值与边界：为什么 8 位补码能表示 $-128$？

8 位二进制一共有 $2^8 = 256$ 种不同的 0/1 组合：

• 0000 0000 到 0111 1111：对应十进制的 $0 \sim +127$（共 128 个正数和零）；
• 1111 1111 到 1000 0001：对应十进制的 $-1 \sim -127$（共 127 个负数）；
• 还剩下一个孤零零的编码：1000 0000。它到底代表什么？

在原码和反码里，1000 0000 曾被浪费在 $-0$ 上。但在补码数学体系中： $$(1000\ 0000)_2 = -2^7 = -128$$ 因此，计算机将 1000 0000 赋予了 $-128$！它没有对应的 8 位原码和反码。

📌 核心结论：有符号整数的表示范围

• 8 位有符号数（C++ 的 char）：$-2^7 \sim 2^7-1$，即 $-128 \sim +127$；
• 16 位有符号数（C++ 的 short）：$-2^{15} \sim 2^{15}-1$，即 $-32768 \sim +32767$；
• 32 位有符号数（C++ 的 int）：$-2^{31} \sim 2^{31}-1$，即 $-2,147,483,648 \sim +2,147,483,647$。

1.7 本讲自学演练与手推挑战

请拿出一张草稿纸，独立手推以下三题，做完后再点击查看解析：

1. 写出十进制数 $-13$ 的 8 位原码、反码与补码；
2. 已知一个 8 位有符号数的补码为 1111 0010，求它对应的十进制真值；
3. 计算补码加法：0000 1100 ($+12$) 与 1111 0101 ($-11$)，写出运算过程与最终结果。

第 2 讲 数字的多面镜——进位制与数制转换

本讲核心目标：理解基数与位权的概念；熟练掌握二进制、八进制、十进制、十六进制之间的数学转换原理（按权展开法、短除法、分组映射法）；能用 C++ 代码实现任意进制转换。

2.1 进位计数制的本质：基数与位权

我们从小学一年级学数学，最习惯十进制。为什么十进制里 $325$ 代表三百二十五？ 因为每一个位置上的数字，其重要程度是不一样的：

$$325 = 3 \times 10^2 + 2 \times 10^1 + 5 \times 10^0$$

这里包含两个核心概念：

1. 基数（Base / Radix）：该进制允许使用的数码个数。十进制的基数是 10（允许使用 $0 \sim 9$）；
2. 位权（Weight）：某个数位上的 1 所代表的实际大小。以小数点为基准向左，位权依次是 $\text{Base}^0, \text{Base}^1, \text{Base}^2, \dots$。

进位制的通则：“逢基数进一，借一当基数”。

2.2 计算机科学中的四大金刚进制

📌 十六进制字母的数字对应（必背）：
A = 10, B = 11, C = 12, D = 13, E = 14, F = 15。

2.3 任意进制转十进制：按权展开求和法

通用公式：对于任意 $R$ 进制数 $(d_n d_{n-1} \dots d_1 d_0)_R$，其等价的十进制值为：

$$\text{Value}_{10} = \sum_{i=0}^{n} d_i \times R^i = d_n \times R^n + d_{n-1} \times R^{n-1} + \dots + d_1 \times R^1 + d_0 \times R^0$$

实例推演 1：二进制转十进制

$$(101101)_2 = 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 32 + 0 + 8 + 4 + 0 + 1 = 45$$

实例推演 2：十六进制转十进制

$$(2\text{A}3)_{16} = 2 \times 16^2 + \text{A}(10) \times 16^1 + 3 \times 16^0 = 2 \times 256 + 10 \times 16 + 3 \times 1 = 512 + 160 + 3 = 675$$

2.4 十进制转任意进制：除基取余，倒序排列

十进制转 $R$ 进制采用短除法：

1. 每次将数字除以基数 $R$，记录所得的商和余数；
2. 用商继续除以 $R$，重复上述步骤；
3. 直到商变为 0 为止；
4. 把所有余数从后往前（倒序）排列，即为目标进制数。

将十进制 53 转换为二进制：
  2 | 53 
    +────
  2 | 26 ...... 余数 1  (最后一位 / 低位) ↑
    +────                               │
  2 | 13 ...... 余数 0                   │ 倒
    +────                               │ 序
  2 |  6 ...... 余数 1                   │ 抄
    +────                               │ 录
  2 |  3 ...... 余数 0                   │
    +────                               │
  2 |  1 ...... 余数 1                   │
    +────                               │
       0 ...... 余数 1  (第一位 / 高位)  │

结论：(53)₁₀ = (110101)₂

2.5 快速通道：二进制与八进制、十六进制极速互转

因为 $8 = 2^3$，$16 = 2^4$，它们之间不需要经过十进制折腾，直接“按位打包”即可！

规则 1：二进制 $\leftrightarrow$ 八进制（3 位一组）

• 二进制转八进制：以小数点为中心向左（整数）向右（小数）每 3 位划分为一组，左边不够补 0。每组按 $4-2-1$ 的权值算出一位八进制数字。
• 范例：$(1101011)_2$ 分组 $\to$ 001 101 011 $\to$ 1 5 3 $\to$ $(153)_8$。

规则 2：二进制 $\leftrightarrow$ 十六进制（4 位一组）

• 二进制转十六进制：每 4 位划分为一组。每组按 $8-4-2-1$ 的权值算出一位十六进制字符。
• 范例：$(110101101)_2$ 分组 $\to$ 0001 1010 1101 $\to$ 1 A(10) D(13) $\to$ $(1\text{AD})_{16}$。

二进制:       0 0 0 1     1 0 1 0     1 1 0 1
位权:         8 4 2 1     8 4 2 1     8 4 2 1
分值:            1       8+2=10(A)   8+4+1=13(D)
十六进制:        1           A           D

2.6 C++ 代码实操：通用十进制转任意进制函数

在编程题中，常常要求我们把一个十进制数转换成 $K$ 进制（$2 \le K \le 16$）。请研读并敲写下面的核心代码模板：

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

// 字符映射表：下标 0~15 对应字符 '0'~'F'
const string DIGITS = "0123456789ABCDEF";

// 函数功能：将十进制数 n 转换成 k 进制字符串
string toBase(long long n, int k) {
    if (n == 0) return "0"; // 边界特判：0 本身返回 "0"
    
    string result = "";
    while (n > 0) {
        int remainder = n % k;          // 除基取余
        result += DIGITS[remainder];     // 记录余数对应的字符
        n /= k;                          // 商继续参与下一轮除法
    }
    
    // 因为是倒序取余，所以要把字符串反转回来
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    long long n = 675;
    cout << "十进制 675 转二进制:   " << toBase(n, 2) << endl;
    cout << "十进制 675 转八进制:   " << toBase(n, 8) << endl;
    cout << "十进制 675 转十六进制: " << toBase(n, 16) << endl;
    return 0;
}

第 3 讲 比特级的微操——位运算原理与实战

本讲核心目标：理解位运算的直接硬件执行属性；吃透 6 种位运算符的运算规则与真值表；深刻认识位运算优先级的陷阱；掌握奇偶判断、乘除倍增、异或魔力与状态掩码等经典实战应用。

3.1 什么是位运算？

日常算术运算（如加减乘除）是面向“数值”的。而位运算（Bitwise Operators）是面向“内存中的每一个二进制比特位（Bit）”的。 因为 CPU 内部的逻辑门电路（AND门、OR门、XOR门）天然就能一步完成位操作，位运算不需要进位判断与除法器介入，运算耗时仅需一个 CPU 时钟周期（纳秒级），速度极其惊人！

3.2 六大位运算符全解与真值表

我们用一个比特位（只有 0 和 1）来说明逻辑：

① 按位与（&，AND）

• 法则：双真才为真，有零则为零。
• $1 \& 1 = 1,\ 1 \& 0 = 0,\ 0 \& 1 = 0,\ 0 \& 0 = 0$。
• 作用：用来提取/保留某些特定位置上的 1，把其余位置清零（相当于掩码过滤）。

② 按位或（|，OR）

• 法则：见真即为真，双零才为零。
• $1 | 1 = 1,\ 1 | 0 = 1,\ 0 | 1 = 1,\ 0 | 0 = 0$。
• 作用：用来强制把某些位置置为 1。

③ 按位异或（^，XOR）

• 法则：相同为 0，相异为 1（求不同）。
• $1 \text{ \textasciicircum } 1 = 0,\ 0 \text{ \textasciicircum } 0 = 0,\ 1 \text{ \textasciicircum } 0 = 1,\ 0 \text{ \textasciicircum } 1 = 1$。
• 作用：密码学加密、反转特定位、不进位加法。

④ 按位非（~，NOT）

• 法则：单目运算符，黑白颠倒，0 变 1，1 变 0（包含符号位）。
• $\sim 0 = 1,\ \sim 1 = 0$。
• 对一个有符号整数 x，在补码体系下永远有数学恒等式：~x = -(x + 1)。比如 ~5 = -6。

⑤ 左移运算（<<，Left Shift）

• 法则：将操作数的二进制位全部向左移动指定的位数，高位丢弃，低位补 0。
• 数学本质：在不溢出的前提下，x << k 等价于 $x \times 2^k$！
• 范例：3 << 2 $\to (00000011)_2 \ll 2 = (00001100)_2 = 12 = 3 \times 2^2$。

⑥ 右移运算（>>，Right Shift）

• 法则：将操作数的二进制位全部向右移动指定位数，低位被挤出丢弃。对于正数高位补 0，负数高位补 1（算术右移）。
• 数学本质：x >> k 等价于 $\lfloor x / 2^k \rfloor$（向下整除）！
• 范例：25 >> 2 $\to 25 / 4 = 6$。

六大位运算速查对比表（设 a = 5 即 0101B, b = 3 即 0011B）：
a:       0 1 0 1 (5)
b:       0 0 1 1 (3)
─────────────────────
a & b:   0 0 0 1 (1)
a | b:   0 1 1 1 (7)
a ^ b:   0 1 1 0 (6)
~a:      ...11111010 (-6)
a << 1:  1 0 1 0 (10)
a >> 1:  0 0 1 0 (2)

3.3 ⚠️ 考场头号杀手：位运算符优先级灾难！

请在脑海中建立极度深刻的警惕：位运算符的优先级低于大多数算术和关系运算符！

// 惨剧现场：
if (n & 1 == 0) // 你的本意是判断 n 是偶数

因为比较运算符 == 的优先级高于 &，编译器会先执行 1 == 0（结果是 false 即 0），整个表达式变成了：

if (n & 0)      // 无论 n 是几，n & 0 永远是 0 (假)！条件永远不成立！

🛡️ 黄金保命法则：写位运算，必须无条件加圆括号！
正确写法：if ((n & 1) == 0)

3.4 位运算五大王牌实战模式

模式 1：极速判断奇偶

if ((n & 1) == 1) {
    // 奇数（二进制最末位是 1）
} else {
    // 偶数（二进制最末位是 0）
}

模式 2：异或的四大神力

1. 归零律：$x \text{ \textasciicircum } x = 0$；
2. 恒等律：$x \text{ \textasciicircum } 0 = x$；
3. 交换律与结合律：多个数连环异或，顺序任意；
4. 两数无额外变量对调：

   a ^= b;
   b ^= a;
   a ^= b; // 此时 a 和 b 的值已完成对调！

💡 经典面试与认证真题：寻找唯一落单的数
题目：给出 $2n+1$ 个整数，其中有 $n$ 对数字两两成对出现，只有一个数字单独出现一次。找出该数字。
解法：根本不需要开数组统计频数！把所有输入的数字全部 ^（异或）在一起：成对出现的数字 $x \text{ \textasciicircum } x$ 全部抵消归零，剩下的就是那个落单的值！时空复杂度 $O(n)$ 时间、$O(1)$ 空间！

模式 3：消除最右侧的 1——n & (n - 1)

这是一个精妙绝伦的数学技巧： 任何一个正整数 $n$，其二进制形式形如 ...100...0。$n-1$ 会将最右边的那个 1 变成 0，而后面的 0 全变成 1。两者一做 & 操作，正好精准抹除最右边的那个 1！

n:       1 0 1 1 0 0
n - 1:   1 0 1 0 1 1
────────────────────
n&(n-1): 1 0 1 0 0 0  (原来第三位的 1 消失了，其余保持不变！)

应用：统计二进制中有几个 1（汉明重量）

int countOnes(int n) {
    int count = 0;
    while (n > 0) {
        n = n & (n - 1); // 每次抹掉一个 1
        count++;
    }
    return count;
}

第 4 讲 算法的蓝图——算法概念、流程图与伪代码

本讲核心目标：理解算法的严格定义与五大特征；熟练掌握流程图的绘制标准与图形规范；学会阅读伪代码并使用草稿纸变量跟踪法（Dry Run）推演算法执行逻辑。

4.1 什么是算法？从做番茄炒蛋谈起

如果说编程语言是“乐器”，那么算法就是“乐谱”。
算法（Algorithm）是解题方案的准确而完整的描述，是一系列解决问题的清晰指令。

并不是所有的过程都能被称为算法。一个合格的计算机算法必须同时满足以下 五大基本特征（选择题极高频考点）：

1. 有穷性（Finiteness）：算法必须在执行有限个步骤后终止，不能陷入无止境的死循环；
2. 确定性（Definiteness）：算法的每一步骤必须有明确的含义，绝不能模棱两可；
3. 可行性（Effectiveness）：算法中的每一步操作都必须是可执行的，能通过有限次基础运算完成；
4. 输入（Input）：可以有 0 个或多个输入；
5. 输出（Output）：必须至少有 1 个或多个输出！一个没有任何输出的程序就像一个黑洞，对外部毫无意义。

4.2 流程图（Flowchart）标准图形规范

流程图用规范的几何图形来表达算法的控制流，是程序设计的重要蓝图。CCF GESP 官方考纲严格要求掌握以下几何图形的语义：

4.3 伪代码（Pseudocode）与变量跟踪推演法（Dry Run）

伪代码是一种介于自然语言和计算机语言之间的文字，它舍弃了严格的语法符号（如头文件、分号），专注于表达算法的逻辑控制。

核心推演技巧：草稿纸表格跟踪法

遇到伪代码阅读题，绝不要光靠大脑空想！最佳习惯是：在纸上列一个表格，表头写上所有变量名，跟着循环一步一步写下每个变量在每一时刻的数值变迁。

实战演练：跟踪分析一段伪代码

输入 N
a <- 1
b <- 1
i <- 3
WHILE i <= N DO
    c <- a + b
    a <- b
    b <- c
    i <- i + 1
END WHILE
输出 b

草稿纸 Dry Run 跟踪表（假设输入 $N = 5$）：

输出结果：b = 5。
算法本质识别：这正是著名的**斐波那契数列（Fibonacci Sequence）**递推！

第 5 讲 数据的整齐排队——C++ 一维数组深入剖析

本讲核心目标：理解一维数组在内存中的连续存储模型与寻址原理；掌握 0-index 下标规范与越界防范；精通一维数组的六大核心操作范式（流式遍历、累加均值、打擂极值、频数统计、就地逆序、桶数组思想）。

5.1 为什么需要数组？

假设班上有 50 名学生，我们要计算平均分，并找出所有高于平均分的学生。 如果没有数组，你需要定义 50 个变量：int s1, s2, s3, ..., s50;。 读入需要写 50 行 cin，求和需要写 50 个加号。更绝望的是，算完平均分后，你无法用一个简单的循环把这 50 个变量逐一比较！

数组（Array）应运而生：它是一种将相同类型的多个数据，在内存中按顺序连续存放的数据结构。

数组名: a
物理内存:  [ 85 ] [ 92 ] [ 78 ] [ 64 ] [ 99 ]
元素下标:    0      1      2      3      4     (长度为 5)

5.2 数组的底层真相：连续线性内存与寻址

在 C++ 中，当你写下 int a[5]; 时：

1. 操作系统在内存中划出一段连续的、长度为 $5 \times 4 = 20$ 字节的空间；
2. 数组名 a 本质上就是这段内存的首地址（起始地址）；
3. 为什么下标从 0 开始？因为下标代表偏移量（Offset）！ $$\text{Address}(a[i]) = \text{BaseAddress} + i \times \text{sizeof(int)}$$
   • $a[0]$ 距离起点偏移 0 个单位，就是首元素；
   • $a[1]$ 距离起点偏移 1 个单位，就是第二个元素。

⚠️ 一生的警钟：严防数组下标越界（Out-of-Bounds）！
int a[100]; 的合法下标永远是 0 到 99！
绝对没有 a[100]！访问 a[100] 会去读写不属于你的未知内存，可能导致程序崩溃（RE）、得到乱码垃圾值，或者在正式评测时直接被判 0 分！

5.3 全局数组 vs 局部数组

💡 B 班实战守则：只要数组元素个数超过 1000，统一写在 main 函数外面（全局）！

5.4 一维数组核心操作六大范式（代码与推演）

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

// 建议开在全局，多开 10 个格子以绝越界隐患
const int MAXN = 1005;
int a[MAXN];

int main() {
    int n;
    if (!(cin >> n)) return 0;

    // 范式 1：顺序读取
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 范式 2：累加求和与防截断平均分
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
    // 必须用 (double) 强转，否则整数除法会丢掉小数
    double avg = (double)sum / n;

    // 范式 3：打擂台法找最大值与其位置
    int max_val = a[0]; // 先让第 0 号当擂主
    int max_idx = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] > max_val) {
            max_val = a[i];
            max_idx = i;
        }
    }

    // 范式 4：条件统计（统计超过平均分的人数）
    int above_cnt = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > avg) {
            above_cnt++;
        }
    }

    // 范式 5：首尾双指针就地逆序翻转
    int left = 0, right = n - 1;
    while (left < right) {
        swap(a[left], a[right]);
        left++;
        right--;
    }

    // 打印结果
    cout << "平均分: " << fixed << setprecision(2) << avg << endl;
    cout << "最高分: " << max_val << " 出现在下标 " << max_idx << endl;
    cout << "超均分人数: " << above_cnt << endl;
    cout << "逆序输出: ";
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;

    return 0;
}

5.5 进阶核心：桶数组（计数排序模型）

假设考试成绩在 $0 \sim 100$ 分之间，有 10 万名考生的分数，如何统计每个分数出现的次数？
传统方法是对每个分数去搜索比对，效率极低。
桶思想（Bucket / Frequency Array）：用数组的“下标”直接代表“数值本身”！

int cnt[105] = {0}; // cnt[s] 存储分数为 s 的学生总人数

for (int i = 0; i < n; i++) {
    int score;
    cin >> score;
    cnt[score]++; // 听到这个分数，对应的桶里加 1 票
}

// 统计完毕，如果想知道得 100 分的有几人：直接看 cnt[100]！

第 6 讲 文字的积木——字符串（std::string）与字符处理

本讲核心目标：理解字符 char 与 ASCII 的底层映射；掌握 C++ 标准库 string 的对象模型；彻底破解 cin 与 getline 的换行符缓冲区死锁；熟练运用子串提取、检索匹配、替换反转与字符库工具。

6.1 char 与 ASCII 码的本质

计算机内部没有文字，每一个字符在内存中本质上都是一个 8 位整数（即 ASCII 编码）：

• 字符 '0' 的码值是 48；
• 大写字母 'A' 的码值是 65；
• 小写字母 'a' 的码值是 97；
• 空格字符 ' ' 的码值是 32。

📌 字符运算两大黄金公式：

1. 数字字符转实际数值：c - '0'（例：'7' - '0' = 55 - 48 = 7）；
2. 大小写字母快速转化：
   • 大写转小写：c + 32 或 tolower(c)；
   • 小写转大写：c - 32 或 toupper(c)。

6.2 C++ std::string 对象模型

C 语言中使用以 \0 结尾的字符数组 char s[100]，容易产生越界溢出。C++ 提供了强大的现代字符串类 std::string：

• 动态自动管理内存长度，无需担心字符串过长越界；
• 支持像整数一样直接使用 + 拼接，使用 ==, <, > 比较字典序！

6.3 读入机制与输入缓冲区陷阱（必须掌握）

机制 1：cin >> s;

• 读取规则：自动跳过前导空格和换行，读到空格、制表符或换行符就停下。
• 缺点：不能读取带有空格的句子（例如 "Hello World" 只能读进 "Hello"）。

机制 2：getline(cin, s);

• 读取规则：读取一整行字符，直到遇到回车换行符 \n 才停止，空格会被完整读入。

⚠️ 深度避坑：换行符残留死锁

先看一段错误示范：

int n;
string s;
cin >> n;         // 键盘输入: 3 然后按了回车
getline(cin, s);  // ❌ 灾难：s 读到的是回车符后的空行！什么都没拿到！

原因解析：cin >> n 只取走了数字 3，而把紧随其后的回车符 \n 留在了输入缓冲区。接下来的 getline 一看缓冲区开头就是回车，立刻认为这一行结束了，直接返回空串！

🛡️ 解惑良药：cin.ignore() 清除缓存

cin >> n;
cin.ignore();     // 关键：吃掉留在缓冲区里的换行符！
getline(cin, s);  // 现在可以顺畅读入整行文本了！

6.4 string 核心函数全景图

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

int main() {
    string s = "ABCDEFGHIJ";

    // 1. 获取长度
    int len = s.size(); // len = 10，也可以用 s.length()

    // 2. 截取子串：s.substr(起始位置, 截取长度)
    // ⚠️ 注意：第二个参数是【截取字符个数】，绝不是结束下标！
    string sub = s.substr(2, 4); // 从下标 2 开始切 4 个字符
    cout << "sub: " << sub << endl; // 输出: CDEF

    // 3. 查找子串：s.find(目标串, 从哪开始找=0)
    string text = "I love C++ and C++ is fast";
    size_t pos = text.find("C++");
    if (pos != string::npos) {
        cout << "找到了！第一次出现在下标: " << pos << endl; // 7
    }

    // 4. 字符串替换：s.replace(起始位置, 替换长度, 替换的新串)
    s.replace(2, 4, "999");
    cout << "replace 后: " << s << endl; // AB999GHIJ

    // 5. 字符判断库 <cctype>
    char ch = '8';
    if (isdigit(ch)) cout << ch << " 是数字！" << endl;
    char ch2 = 'a';
    if (isalpha(ch2)) cout << ch2 << " 是字母！" << endl;
    cout << "大写形式: " << (char)toupper(ch2) << endl; // 'A'

    return 0;
}

第 7 讲 最朴素的智慧——枚举算法（穷举法）

本讲核心目标：理解枚举算法的底层哲学（不重不漏地穷尽解空间）；掌握确定状态变量、划定搜索边界、构建判定条件的三步法；深入学习代数降维与剪枝技巧（以百钱买百鸡、水仙花数为例）。

7.1 穷举也是一种智慧

在很多同学眼中，“枚举（Enumeration）”听起来很土，甚至觉得只有不会高级算法的人才会用穷举。 这是极大的认知误区！ 计算机的核心优势就是：每秒能做上亿次运算，不知疲倦，分秒不差。如果一个问题的可能解只有 10 万个，计算机花 0.001 秒就能把所有可能检查一遍。在有限的解空间内，枚举是最稳妥、最不可能出错的满分策略！

7.2 枚举设计三部曲

无论多复杂的枚举题，都可以严格拆解为三个问答：

 1. 枚举谁？       ───> 选定状态变量（循环变量是谁？）
 2. 空间有多大？   ───> 确定上界与下界（循环从几到几，保证不重不漏）
 3. 如何验证？     ───> 编写 if 条件准则（符合条件的保留，否则丢弃）

7.3 经典案例剖析：水仙花数与数位分解

题目描述：打印所有三位“水仙花数”。水仙花数是指一个三位数，其各位数字的立方和恰好等于该数本身。例如：$153 = 1^3 + 5^3 + 3^3$。

三步推演：

1. 枚举谁：三位数 $n$；
2. 范围多大：从 $100$ 到 $999$（整整 900 个数，计算机一瞬间就能跑完）；
3. 如何验证：提取百位、十位、个位，检验是否满足立方和相等。

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

int main() {
    for (int n = 100; n <= 999; n++) {
        // 核心基本功：三位数的数位拆解
        int ge = n % 10;          // 取模 10 得到个位数
        int shi = (n / 10) % 10;  // 先整除 10 砍掉个位，再模 10 得到十位
        int bai = n / 100;        // 整除 100 得到百位

        if (bai * bai * bai + shi * shi * shi + ge * ge * ge == n) {
            cout << n << " 是水仙花数！" << endl;
        }
    }
    return 0;
}

7.4 降维优化：百钱买百鸡与循环缩减

问题：公鸡 5 元一只，母鸡 3 元一只，小鸡 1 元三只。用 100 元钱买 100 只鸡，公鸡、母鸡、小鸡各多少只？

初学者的三层循环暴力（慢）：

for (int x = 0; x <= 100; x++) {       // 公鸡
    for (int y = 0; y <= 100; y++) {   // 母鸡
        for (int z = 0; z <= 100; z++) { // 小鸡
            if (x + y + z == 100 && 5 * x + 3 * y + z / 3.0 == 100) { ... }
        }
    }
}
// 循环执行了 100 * 100 * 100 = 1,000,000 次！

算法高手的数学降维思维（快百倍）：

一共买 100 只鸡。如果公鸡买了 $x$ 只，母鸡买了 $y$ 只，那么小鸡的数量必然是 $z = 100 - x - y$！根本不需要第三重循环！ 此外，100 元全买公鸡最多买 20 只，全买母鸡最多买 33 只。我们可以大大压缩枚举范围：

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

int main() {
    // 公鸡最多 20 只，母鸡最多 33 只
    for (int x = 0; x <= 20; x++) {
        for (int y = 0; y <= 33; y++) {
            int z = 100 - x - y; // 降维：直接计算得出
            if (z < 0) continue;
            
            // 小鸡三只一元，数量必须是 3 的倍数
            if (z % 3 == 0) {
                // 用全整数算式，避免 double 小数精度误差
                if (5 * x + 3 * y + z / 3 == 100) {
                    cout << "公鸡: " << x << " 只, 母鸡: " << y 
                         << " 只, 小鸡: " << z << " 只" << endl;
                }
            }
        }
    }
    return 0;
}

运算次数从 100 万次骤降到 $21 \times 34 \approx 700$ 次！这就是算法优化的魅力。

第 8 讲 分秒不差的执行——模拟算法

本讲核心目标：掌握模拟算法（Simulation）的本质特征；精通状态变量定义、规则时序推演与终态控制的设计范式；攻克角谷猜想、约瑟夫环基础模型、时钟推进等经典题型；掌握草稿纸单步调试秘诀。

8.1 什么是模拟法？代码就是剧本的精准演出

模拟题是各类编程考试中最常见的题型。这类题目的特征是：

• 没有深奥晦涩的数学定理；
• 题目会给出一大堆繁琐的具体规则；
• 你的唯一任务：按照出题人给定的现实世界规则，用代码一丝不苟地复现执行过程。

模拟题看似简单，却是最考验基本功的题型，稍微疏忽一个细小边界，就会满盘皆输。

8.2 模拟算法三大要素

1. 状态定义（State）：用哪些变量来记录“当前这一刻”世界的全貌？
2. 状态转移（Transition）：随着时间向前一秒，或者事情发展一步，状态变量如何更新？
3. 终止条件（Termination）：什么时候游戏结束，或者事情办完了？

8.3 经典实战 1：数值步进型模拟——角谷猜想（Collatz Conjecture）

题目描述：日本数学家角谷静夫提出：任何一个正整数 $n$，如果它是奇数，则把它乘以 3 加 1；如果它是偶数，则把它除以 2。重复这个过程，最终必然会停在 1。输入正整数 $n$，打印其变迁过程并统计总步数。

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

int main() {
    long long n; // 过程中数值可能剧烈膨胀，防溢出开 long long
    cin >> n;
    
    int steps = 0;
    while (n != 1) { // 终止条件：n 到达 1
        if (n % 2 == 1) {
            cout << n << "*3+1=" << n * 3 + 1 << endl;
            n = n * 3 + 1; // 奇数转移规则
        } else {
            cout << n << "/2=" << n / 2 << endl;
            n = n / 2;     // 偶数转移规则
        }
        steps++;
    }
    cout << "总共经过了 " << steps << " 步变迁到 1。" << endl;
    return 0;
}

8.4 经典实战 2：规则淘汰型模拟——约瑟夫环初级版（报数出列）

题目描述：$n$ 个人围成一圈，编号从 $1$ 到 $n$。从第 1 个人开始报数，报到第 $m$ 的人出列淘汰，下一个人重新从 1 开始报数，直到所有人出列。输出所有人的出列顺序。

设计思维推演：

1. 状态：每个人是否还在圈内？可以用一个布尔数组 bool out[105] 表示，true 代表已经出局；
2. 变量：
   • alive：当前圈内还剩几个人（初值为 $n$）；
   • cur：当前小人走到几号了；
   • count：当前报数报到几了。

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

bool eliminated[105]; // 默认为 false，都在圈内

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

    int remaining = n; // 剩下的人数
    int cur = 1;       // 从 1 号开始
    int count = 0;     // 当前报的数

    while (remaining > 0) {
        if (!eliminated[cur]) { // 只有没被淘汰的人才报数
            count++;
            if (count == m) {
                // 报到 m 的人出局
                cout << cur << " ";
                eliminated[cur] = true;
                remaining--;
                count = 0; // 重置报数
            }
        }
        
        // 环形推进：如果到了 n 号，下一个回到 1 号
        cur++;
        if (cur > n) cur = 1;
    }
    cout << endl;
    return 0;
}

结语：通往 GESP 四级的进阶指南

当你认真推演、动手敲完本讲义的每一道例题时，你已经掌握了计算机底层的数据运转密码，跨过了一维数组、字符串与经典算法这道最重要的分水岭！

下一步的学习目标（GESP 四级先瞻）：

• 函数与模块化：把重复代码封装为函数，掌握值传递与引用传递；
• 二维数组与矩阵：进入多维空间的世界，处理地图、棋盘与矩阵旋转；
• 基础排序算法：深入学习冒泡排序、选择排序与插入排序的底层运行图式；
• 递推算法：从斐波那契数列和走台阶问题出发，掌握动态规划的前身！

代码没有捷径，每一行亲手敲出的有效代码，都在塑造你未来的计算思维。加油！