时间复杂度与空间复杂度
程序为什么会超时？怎么估算一个算法的快慢？从 TLE 说起，把复杂度的账算明白。
先看懂：程序为什么会超时
评测只给 1 秒，运算量太大就 TLE——把计算量算出来，是优化的第一步。
用固定操作的执行次数衡量快慢
不测真实秒数，而是统计“固定操作”的执行次数与变量 n 的关系——这就是时间复杂度。
把排序的复杂度账也算清楚
传统三件套平均 O(n²)，快排平均、归并与堆排序最坏 O(n log n)——再用实测数据说话。
内存不是无限的
KB / MB / GB 怎么换算？数组占多少内存？超了会怎样？——这一部分把空间账也算明白。
用对比把复杂度看透
斐波那契、重复元素检测、最大子数组和——同一道题，不同代价，亲眼看看差距。
前缀和与差分
把「区间和」从 O(n) 降到 O(1)，把「区间修改」从 O(n) 降到 O(1)——一对互为逆运算的加速器。
先把前 n 项的和算好
从水果商人的收购点说起：前 n 项的和就是前缀和，用数组存起来，后面随便查。
一次减法，回答所有区间问题
任意区间 [L, R] 的和，不用再一段段累加——s[R] − s[L−1] 一次搞定。
n、m 都到 100000 的区间查询
数据一大，暴力加法必然超时——用前缀和写一版标准解法。
一维会了，二维也不怕
同样的套路还能用到矩形区域、乘积和异或上——思路是相通的。
每一项与前一项的差
前缀和的反向操作：把每个数变成与前一项的差，区间修改就变成了两个位置的修改。
一对互为逆运算的搭档
前缀和与差分转一圈就能互相还原——最后把两者的适用场景摆在一起对比。
二分查找
每次砍掉一半：在有序数组里，约 20 次比较就能替代 100 万次扫描。
先别看代码，先玩个游戏
我心里想一个 1 ~ 100 的整数，只回答「大了 / 小了 / 猜中」——你最少几次能保证猜中？
把猜数游戏搬到有序数组上
数组有序，就相当于答案已经按顺序排好——中间那个元素，就是那声「大了 / 小了」。
把这三件事写成 while 循环
循环条件写 L <= R，每轮只会更新 L 或 R——最要小心的是：区间必须真的在缩小。
在升序数组里查找目标值
元素互不重复、已经升序排好——把刚写的模板套进完整程序里跑一遍。
二分能做的，不止「找一个数」
把「等于 target」换成「满足某个条件」，二分就变成了找边界——这也是下一单元「二分答案」的入口。
二分答案
答案藏在一个范围里，而「试一下就知道行不行」——于是 10 亿次枚举，变成 30 次判断。
先别写代码，先动手试
3 根木材，长度 8、4、10，要切出 5 段一样长的——每段最长能有多长？
可行的答案，是一段连续的前缀
先框出答案的可能范围，再确认「大的可行 ⟹ 小的也可行」这条性质——它就是二分的通行证。
在 [1, 10] 里，四轮锁定答案
每一轮只做三件事：算 mid、算段数、决定留哪一半。答案用 ans 单独记下来。
把「判断」和「二分」拆成两件事
check(x) 只负责回答行不行；二分框架只负责缩小范围。拆开之后，换一道题只需要重写 check。
换个 check，就是另一道题
切割木材求最大，分书求最小，跳石头求「最大的最小」——模板一个字都不用改。
分治与快速排序
把大问题劈成两半，让基准元素一次归位——平均 O(n log n) 的原地排序。
大问题拆小，小到不用再拆
排序 100 万个数很难，排序 1 个数不用排——中间差的，就是「怎么拆」和「怎么拼」。
一次扫描，让基准找到最终位置
选一个基准，把「不大于它的」全甩到左边，「大于它的」全甩到右边——它就再也不用动了。
分区写进 while，递归收在末尾
二十行的 qsort：两个指针、三次交换、两次递归——每一行都要看清楚在干什么。
平均很快，最坏很惨
快排的速度全看「分得均不均」：每次对半开是 n log n，每次只切掉一个就退化成 n²。
快排不止能排序
同一套分区，改一改就能找第 K 小；重复元素多、数组小，也各有对应的优化。
归并与分治深化
一刀切到单个元素，再两两拼回有序——最坏 O(n log n)，且排序稳定，顺手数清逆序对。
从中间切，一直切到只剩一个
8 个数太难排，1 个数不用排。归并排序的「分解」简单到只有一句话：mid 一刀两半。
两段有序，合成一段有序
归并的功夫全在 merge：两个指针各指一段，谁小就把谁抄进临时数组。
递归只有三行
算 mid、递归两半、合并——归并排序的主函数短得不像话，因为难点都在 merge 里。
多花一倍空间，换来最坏的保证
归并的三层递归每层都合并 n 个数，所以最好最坏都是 n log n——代价是要一块临时数组。
排序顺手数出「反着排」的对
暴力两两比较是 O(n²)，而归并合并时，每一次「取右边」都白送一批逆序对。
简单动态规划
把算过的答案记在表里，用空间换时间——指数级递归，一次循环就能解决。
同一个子问题，被算了三次
分治假设子问题互不相干；可现实里子问题常常重叠——算过的又算一遍，时间就这么没了。
先想清楚：表格里每一格是什么
DP 的难点不在写循环，而在「定义状态」——把题目翻译成一张表，转移方程自然就出来了。
最小的 DP：一维表格
F[i] = F[i−1] + F[i−2]。一维数组、一个循环，把 2ⁿ 压成 n。
只准向右、向下，有几条路？
二维表格的第一次登场：每一格的路径数 = 上面那格 + 左边那格。
每件东西，拿还是不拿
二维 DP 的招牌题：前 i 件物品、容量 j，能装出的最大价值是多少？
因数与倍数
因数成对出现，所以只要枚举到 √n；gcd 一次辗转相除，素数一次试除。
能整除，就是因数
6 ÷ 3 = 2 没有余数，所以 3 是 6 的因数，6 是 3 的倍数——一件事的两种说法。
一直取余，直到余数为 0
欧几里得两千年前就发现：gcd(a,b) = gcd(b, a mod b)——不用分解质因数也能求最大公约数。
只能被 1 和自己整除
判素数是数论的基本功：试到 √n 就够；把合数拆成质数相乘，是整个单元的核心工具。
完全平方、因数个数、枚举倍数
质因数分解是把钥匙：拆开之后，奇偶性、个数、配对关系都一目了然。
高效素数筛选
不再一个一个判：把合数整批划掉，一次预处理，后面全是查表。
要 1 ~ n 的所有素数，还一个一个判？
判一个数 O(√n) 不算慢，可 n 个数加起来就是 n√n——10⁶ 时约 10⁹ 次，超时。
素数至少 2 倍的正整数倍是合数
从小到大扫，遇到没被划掉的数，它就是素数；顺手把它至少 2 倍的倍数标成非素数；从平方起能减少重复。
每个合数，只被划一次
用「i × 已有素数」生成合数，一旦 i 能被某个素数整除就停手——保证只由最小质因数生成。
预处理一次，回答一万次
筛法最典型的用法：先把 1 ~ N 的素数表建好，之后每次查询都是 O(1) 查表。
指针与引用
变量住在内存的某个门牌号上；指针记门牌，引用就是同一个人的小名。
每个变量，都有一个门牌号
指针变量的值不是数字，而是另一个变量在内存里的地址——顺着地址就能找到它。
数组在许多表达式中可转换为首元素指针
数组本身不是指针；转换后可得到 &a[0]。a[i] 等价于 *(a+i)——两种写法，同一块内存。
为什么 swap 写完没反应？
C++ 默认「值传递」：函数拿到的是副本。想改原件，就得把地址或引用递进去。
字符串、越界与野指针
指针给了你直接操作内存的能力，也把所有责任一起交给了你。
文件与异常
让程序从文件读、往文件写；出错的时候，别让整个程序直接崩掉。
把键盘和屏幕，换成两个文件
标准输入 stdin、标准输出 stdout 本来是键盘和屏幕；重定向，就是把它们指到文件上。
出错的时候，别直接崩
文件打不开、输入不合法——与其让程序默默算错，不如把问题「扔」出来，接住再处理。
比赛里怎么用，怎么别踩雷
重定向只占两行；剩下的坑，基本都和「忘了关」「交错了文件」有关。