1. 三级新增知识框架

• 原码、反码、补码。
• 二/八/十/十六进制转换。
• 位运算：& | ~ ^ << >>。
• 算法描述：自然语言、流程图、伪代码。
• 一维数组。
• 字符串与常用函数。
• 枚举法、模拟法。

2. 原码、反码、补码

以固定位数的有符号整数为背景：

编码	正数	负数	关键特点
原码	符号位 0 + 数值	符号位 1 + 绝对值	有 +0 与 -0
反码	与原码相同	符号位不变，其余位取反	仍有两种 0
补码		反码 + 1	只有一个 0，便于统一加减法

$n$ 位补码范围

• 有符号：$-2^{n-1}$ 到 $2^{n-1}-1$。
• 8 位：$-128$ 到 $127$。
• 16 位：$-32768$ 到 $32767$。

负数补码求法

求 -5 的 8 位补码：

1. +5：00000101
2. 各位取反：11111010
3. 加 1：11111011

3. 四种常用进制

进制	基数	数字字符	C++ 常见字面量
二进制	2	0,1	0b1010
八进制	8	0～7	012
十进制	10	0～9	10
十六进制	16	0～9,A～F	0xA

其他进制转十进制

按位权展开：

$a_ka_{k-1}\cdots a_0$（基数为 $b$）的值为 $\sum_{i=0}^{k} a_i b^i$。

例如：$1011_2=1\times2^3+0\times2^2+1\times2+1=11$。

十进制整数转其他进制

除基取余，余数逆序。

十进制小数转其他进制

乘基取整，整数部分顺序。

例如：$0.625_{10}=0.101_2$。

快速互转

• 二进制 ↔ 八进制：每 3 位二进制一组。
• 二进制 ↔ 十六进制：每 4 位二进制一组。

4. 位运算表

运算	符号	规则	常见用途
按位与	&	都为 1 才为 1	取位、判断奇偶
按位或	`		有 1 就为 1
按位非	~	0/1 取反	位翻转
按位异或	^	不同为 1，相同为 0	翻转、异或性质
左移	<<	向左移动	非溢出情况下相当于乘 $2^k$
右移	>>	向右移动	对非负整数常相当于除 $2^k$ 取整

必背位运算性质

• x & 1：取最低位，可判断奇偶。
• x ^ x = 0。
• x ^ 0 = x。
• x & 0 = 0。
• x | 0 = x。
• 第 k 位掩码常写：1 << k。
• 判断第 k 位：(x >> k) & 1。
• 将第 k 位置 1：x |= (1 << k)。
• 将第 k 位翻转：x ^= (1 << k)。

5. 一维数组

int a[100];
for (int i = 0; i < n; i++) cin >> a[i];

项目	要点
下标	从 0 开始时，长度为 n 的合法下标是 0..n-1
连续存储	同类型元素连续排列
越界	访问 a[n] 属于越界
初始化	int a[10] = {}; 可将元素初始化为 0

常见基础操作：求和、最大值、最小值、计数、反转、去重（配合排序）、前后比较。

6. string 常用操作

功能	写法	说明
长度	s.size() / s.length()	返回字符数量
取字符	s[i]	下标从 0 开始
拼接	s1 + s2	生成新字符串
追加字符	s.push_back(c)	尾部加入字符
删除尾字符	s.pop_back()	字符串非空时使用
子串	s.substr(pos, len)	从 pos 取 len 个字符
查找	s.find(t)	找不到返回 string::npos
删除	s.erase(pos, len)	删除指定区间
插入	s.insert(pos, t)	在 pos 插入
替换	s.replace(pos, len, t)	替换指定区间

大小写转换

#include <cctype>
char a = toupper(c);
char b = tolower(c);

ASCII 条件下也可用偏移理解：'a' - 'A' == 32。

字符串分割【辅助补充】

C++ string 没有类似某些语言的统一 split() 成员函数，常用循环或 stringstream 自己切分。

7. 枚举法

**定义：**把所有可能情况按规则逐一检查。

适用：状态数量可控、直接搜索空间不大。

模板思想：

for (所有候选) {
    if (满足条件) {
        更新答案;
    }
}

复杂度通常与“枚举了多少个状态 × 每个状态检查成本”有关。

8. 模拟法

**定义：**严格按照题目规则，用程序还原事件/过程。

模拟题四步：

1. 确定状态由哪些变量表示。
2. 按题目顺序处理每一步操作。
3. 明确边界、下标、方向和状态更新先后。
4. 必要时打印中间状态调试。

高频类型：日期、位置移动、游戏规则、队列过程、字符串操作、表格变换。

9. 三级必背易错点

1. 补码不是“最高位直接当负号后的普通二进制”。
2. 十六进制 A..F 分别代表 10..15。
3. 位运算与逻辑运算不同：& vs &&，| vs ||。
4. << 既可表示位移，也会在 cout << x 中作为流插入运算符，语境不同。
5. 数组下标越界是高频错误。
6. find() 找不到返回 string::npos，不是固定的 -1 写法。
7. 模拟题要特别注意“先更新谁、后更新谁”。

10. 三级背诵清单

• [ ] 原码/反码/补码定义与 8/16 位范围。
• [ ] 二八十十六进制互转。
• [ ] & | ~ ^ << >> 规则。
• [ ] 一维数组下标与初始化。
• [ ] string 的 size/substr/find/erase/insert/replace。
• [ ] 枚举与模拟的定义和适用场景。