1. 为什么需要背诵算法模板？

算法竞赛和编程面试中，熟练度往往决定了成败。当你在白板编程或限时比赛中，面对经典算法问题时，如果还需要从头推导基本框架，时间很可能不够用。这就是为什么ACWing等算法学习平台特别强调模板化训练——把常见算法的标准实现刻进肌肉记忆。

我刚开始刷题时也犯过这个错误：觉得理解了算法原理就够了，结果在Codeforces比赛中明明知道该用Dijkstra，却因为堆优化的实现卡壳，直接痛失100分。后来系统性地整理和记忆模板后，解题速度和稳定性明显提升。

2. 高效记忆模板的黄金法则

2.1 理解优先于死记硬背

在记忆快速排序模板前，务必先明白：

• 分治思想如何应用
• 为什么取中点作为pivot更稳健
• 递归终止条件的意义

我习惯用"三步法"学习新算法：

1. 看动画演示建立直观认知（推荐VisuAlgo）
2. 手写模拟执行过程
3. 最后才看代码实现

2.2 模块化拆解模板

以ACWing的快速排序模板为例：

void quick_sort(int q[], int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j + 1, r); }

可以分解为：

1. 终止条件（l >= r）
2. 双指针初始化（i/j的±1偏移）
3. 基准值选取（位运算优化）
4. 分区过程（do-while避免边界问题）
5. 递归处理子区间（注意j的分界）

2.3 刻意练习方法论

我的每日训练计划：

• 早晨：默写3个模板（手写）
• 午休：在ACWing题库筛选对应标签题目
• 晚间：用模板AC题目后，尝试变形实现

关键技巧：用不同颜色标记模板中的关键边界条件，比如快速排序中的i/j初始偏移和递归区间划分，这些往往是面试官故意考察的细节。

3. 第一天必备模板清单

3.1 排序算法三件套

快速排序

// 上文已给出完整实现

易错点：

• 忘记处理i<j的swap判断
• 递归时错误使用i而不是j分界

归并排序

void merge_sort(int q[], int l, int r) { if (l >= r) return; int mid = l + r >> 1; merge_sort(q, l, mid); merge_sort(q, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++]; while (i <= mid) tmp[k++] = q[i++]; while (j <= r) tmp[k++] = q[j++]; for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j]; }

应用场景：

• 逆序对问题
• 链表排序
• 外部排序

堆排序

void down(int u) { int t = u; if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1; if (u != t) { swap(h[u], h[t]); down(t); } } // 建堆 for (int i = n / 2; i; i--) down(i); // 排序 while (m--) { printf("%d ", h[1]); h[1] = h[size--]; down(1); }

注意：

• 小根堆实现
• 建堆复杂度O(n)的数学原理
• 删除堆顶元素后的调整策略

3.2 二分查找模板

整数二分

bool check(int x) { /* ... */ } int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } return l; } int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } return l; }

记忆口诀：

• 版本1找第一个满足条件的（右边界左移）
• 版本2找最后一个满足条件的（左边界右移）
• 注意mid计算是否要+1防死循环

浮点数二分

double bsearch_3(double l, double r) { const double eps = 1e-6; while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; }

应用场景：

• 求平方根
• 最优解问题
• 物理运动模拟

4. 模板实战应用技巧

4.1 快速排序变形

求第k小的数（快速选择算法）：

int quick_select(int l, int r, int k) { if (l == r) return q[l]; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } int sl = j - l + 1; if (k <= sl) return quick_select(l, j, k); return quick_select(j + 1, r, k - sl); }

时间复杂度从O(nlogn)优化到O(n)

4.2 归并排序应用

统计逆序对数量：

LL merge_sort(int l, int r) { if (l >= r) return 0; int mid = l + r >> 1; LL res = merge_sort(l, mid) + merge_sort(mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k++] = q[i++]; else { tmp[k++] = q[j++]; res += mid - i + 1; // 核心修改 } // ...剩余部分不变 return res; }

5. 常见坑点与调试技巧

5.1 边界条件大全

5.2 内存问题排查

• 归并排序忘记开临时数组
• 堆排序数组下标从1开始却用0初始化
• 递归算法爆栈（可改为迭代版本）

5.3 数据测试策略

我常用的测试用例：

1. 空数组
2. 单元素数组
3. 完全有序数组
4. 完全逆序数组
5. 大量重复元素数组
6. 随机生成的大数据（1e5级别）

6. 模板进阶：竞赛专用优化

6.1 输入输出加速

ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

6.2 位运算优化

• 除2：x >> 1
• 乘2加1：x << 1 | 1
• 奇偶判断：x & 1

6.3 内联汇编优化

（适用于ICPC等允许汇编的比赛）

__asm__( "movl %ebx, %eax\n" "shrl $1, %eax\n" );

7. 个人训练路线建议

第一阶段（1-2周）：

• 每天精练2个模板
• 每个模板配套做3道ACWing基础题
• 整理错题本记录变形用法

第二阶段（3-4周）：

• 尝试用模板解决LeetCode中等题
• 参加每周的ACWing竞赛
• 开始整理模板变种库

第三阶段（持续）：

• 参与开源算法项目
• 自建模板代码生成器
• 尝试魔改标准模板创造新算法