ACM ICPC算法基础包括哪几类

ACM ICPC（国际大学生程序设计竞赛）的算法基础涵盖多个核心领域，主要分为以下几大类，每类包含关键知识点和典型应用场景：

---

一、基础数据结构

1. 线性结构

   • 数组、链表（单/双）、栈、队列
   • 特殊变体：循环队列、单调栈、双端队列（Deque）
   • 应用场景：表达式求值（栈）、滑动窗口（队列）

2. 树形结构

   • 二叉树（遍历、BST、堆）
   • 进阶树：AVL树、红黑树（较少手写，需理解原理）
   • 应用场景：优先队列（堆）、区间查询（线段树）

3. 哈希与集合

   • 哈希表实现、冲突解决（开放寻址/链地址法）
   • STL中的unordered_map与set使用技巧

---

二、算法设计范式

范式	核心思想	典型问题
暴力枚举	穷举所有可能	全排列、子集生成
分治算法	分解-解决-合并	归并排序、最近点对问题
贪心算法	局部最优→全局最优	霍夫曼编码、区间调度
动态规划	状态转移+重叠子问题	背包问题、最长公共子序列
回溯算法	试错+剪枝	N皇后、数独求解

---

三、图论算法

1. 基础算法

   • 图的表示：邻接矩阵/邻接表
   • 遍历：DFS、BFS（双向BFS优化）

2. 最短路径

   • Dijkstra（非负权图）
   • Bellman-Ford（负权检测）
   • Floyd-Warshall（全源最短路径）

3. 连通性与网络流

   • 并查集（Union-Find）
   • 最小生成树（Prim/Kruskal）
   • 最大流（Edmonds-Karp/Dinic）

---

四、数学与数论

1. 数论基础

   • 素数筛法（埃氏筛、欧拉筛）
   • 模运算、快速幂、逆元
   • 扩展欧几里得算法（解线性同余方程）

2. 组合数学

   • 排列组合公式、容斥原理
   • 卡特兰数、斐波那契数列应用

3. 计算几何

   • 点/线/多边形基本操作
   • 凸包算法（Graham Scan）
   • 扫描线算法（矩形面积并）

---

五、字符串处理

1. 模式匹配

   • KMP算法（失配数组优化）
   • Trie树（前缀统计）

2. 高级处理

   • 后缀数组（DC3算法）
   • 有限状态自动机（AC自动机）

---

六、复杂度与优化

1. 时间复杂度分析

   • 主定理（递归算法分析）
   • 均摊分析（如并查集路径压缩）

2. 竞赛技巧

   • 输入输出优化（ios::sync_with_stdio(false)）
   • 位运算压缩状态（状态压缩DP）

---

七、必备模板题

1. 动态规划：01背包、最长上升子序列（LIS）
2. 图论：拓扑排序、强连通分量（Tarjan）
3. 数据结构：RMQ（ST表）、树状数组

---

学习路径建议

1. 初级阶段：掌握暴力枚举→分治→贪心
2. 中级阶段：攻克动态规划+图论基础
3. 高级阶段：网络流/计算几何/后缀自动机

ACM ICPC的算法体系强调灵活组合能力——实际赛题常需多算法嵌套（如DFS+剪枝+状态压缩）。建议通过Codeforces、LeetCode等平台针对性训练，并熟悉C++ STL的<algorithm>库高效实现。