1. 竞赛算法全景概览算法竞赛是检验程序员解决问题能力的终极试金石。从ACM-ICPC到Google Code Jam从LeetCode周赛到企业编程挑战优秀的竞赛选手往往掌握着一套完整的算法武器库。这套武器库不是简单的方法堆砌而是经过千锤百炼的思维框架与实战策略。我在过去五年参与各类编程竞赛的经历中发现真正决定比赛胜负的往往不是知道多少种算法而是能否在高压环境下快速识别问题本质并选择最合适的解决路径。这需要我们对算法有系统性的认知——了解每类算法的适用场景、时间代价和实现陷阱。2. 基础数据结构与算法2.1 线性结构处理技巧数组和链表是竞赛中最基础的数据结构但高手与新手的区别往往体现在对这些基础结构的极致优化上。比如在滑动窗口问题中双指针技巧可以将O(n²)的暴力解法优化到O(n)。一个经典案例是求解最小覆盖子串问题def minWindow(s: str, t: str) - str: from collections import defaultdict need defaultdict(int) for c in t: need[c] 1 left 0 valid 0 res window defaultdict(int) for right in range(len(s)): c s[right] if c in need: window[c] 1 if window[c] need[c]: valid 1 while valid len(need): if not res or right - left 1 len(res): res s[left:right1] d s[left] left 1 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return res这个实现中有几个关键点需要注意使用valid变量而非直接比较字典避免频繁的字典遍历收缩左边界时的条件判断顺序会影响正确性边界条件处理要考虑空字符串的情况2.2 树形结构的高级应用二叉树相关问题是竞赛中的常客。除了基本的遍历算法竞赛中更常考察变形应用。比如最近公共祖先(LCA)问题使用Tarjan离线算法可以在O(nα(n))时间内处理大量查询struct DSU { vectorint parent; DSU(int n) : parent(n) { iota(parent.begin(), parent.end(), 0); } int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } void unite(int x, int y) { x find(x); y find(y); if(x ! y) parent[y] x; } }; void tarjan(int u, vectorvectorint tree, vectorvectorpairint,int queries, DSU dsu, vectorint ancestor, vectorbool visited) { visited[u] true; ancestor[u] u; for(int v : tree[u]) { if(!visited[v]) { tarjan(v, tree, queries, dsu, ancestor, visited); dsu.unite(u, v); ancestor[dsu.find(u)] u; } } for(auto [v, idx] : queries[u]) { if(visited[v]) { int lca ancestor[dsu.find(v)]; // 处理查询结果 } } }实际比赛中更常用的其实是基于二进制拆分的在线LCA算法虽然理论复杂度是O(nlogn)预处理O(logn)查询但实现更简单且常数更小。3. 动态规划进阶策略3.1 状态压缩技巧当问题规模较小时状态压缩DP可以解决许多看似复杂的问题。比如经典的旅行商问题(TSP)可以用位运算表示访问过的城市集合def tsp(dist): n len(dist) dp [[float(inf)] * n for _ in range(1n)] dp[1][0] 0 # 从城市0出发 for mask in range(1n): for u in range(n): if not (mask (1u)): continue for v in range(n): if mask (1v): continue new_mask mask | (1v) if dp[new_mask][v] dp[mask][u] dist[u][v]: dp[new_mask][v] dp[mask][u] dist[u][v] # 回到起点 res float(inf) for u in range(1, n): res min(res, dp[(1n)-1][u] dist[u][0]) return res这个实现有几个优化点预处理距离矩阵避免重复计算使用位运算快速判断状态包含关系循环顺序确保子问题先被计算3.2 数位DP实战数位DP常用于解决与数字各位相关的计数问题。比如统计区间[L,R]内满足某种条件的数字个数。一个典型实现框架如下int dfs(int pos, int state, bool limit, bool lead, const string num) { if(pos num.size()) return check(state) ? 1 : 0; if(!limit !lead dp[pos][state] ! -1) return dp[pos][state]; int res 0; int up limit ? num[pos]-0 : 9; for(int d 0; d up; d) { bool new_lead lead (d 0); int new_state new_lead ? state : update(state, d); res dfs(pos1, new_state, limit (d up), new_lead, num); } if(!limit !lead) dp[pos][state] res; return res; } int solve(int x) { memset(dp, -1, sizeof dp); string num to_string(x); return dfs(0, 0, true, true, num); }实际应用中需要注意状态设计要足够表达必要条件前导零处理要小心特别是当0本身也是有效数字时记忆化条件要正确limittrue或leadtrue时不能直接取缓存值4. 图论算法精要4.1 网络流建模艺术最大流问题在竞赛中往往需要巧妙的建模。比如二分图匹配可以转化为最大流问题但有些题目需要更复杂的转换。考虑下面这个例题有m个项目和n个学生每个项目需要一定数量的学生每个学生有可参与的项目列表问是否能满足所有项目需求。这可以通过多源点多汇点的网络流模型解决def solve(projects, students): # projects: list of (requirement, [student indices]) # students: list of [project indices] m len(projects) n len(students) size 1 m n 1 # 源点 项目 学生 汇点 graph [[0]*size for _ in range(size)] # 源点到项目 for i in range(m): req projects[i][0] graph[0][1i] req # 项目到学生 for i in range(m): for s in projects[i][1]: graph[1i][1ms] 1 # 学生到汇点 for j in range(n): graph[1mj][-1] 1 return max_flow(graph, 0, size-1) sum(p[0] for p in projects)关键点在于项目需求转化为源点到项目的边容量每个学生只能参与有限项目通过学生到汇点的容量限制项目与学生间的边表示匹配可能性4.2 启发式搜索优化对于状态空间巨大的问题A*算法往往比普通BFS更高效。比如八数码问题使用曼哈顿距离作为启发函数def astar(start, target): def heuristic(state): h 0 for i in range(3): for j in range(3): val state[i][j] if val ! 0: x, y (val-1) // 3, (val-1) % 3 h abs(x-i) abs(y-j) return h heap [] heapq.heappush(heap, (heuristic(start), 0, start)) visited set() visited.add(tuple(tuple(row) for row in start)) while heap: _, cost, state heapq.heappop(heap) if state target: return cost zero_i, zero_j next((i,j) for i in range(3) for j in range(3) if state[i][j]0) for di, dj in [(0,1),(1,0),(0,-1),(-1,0)]: ni, nj zero_idi, zero_jdj if 0 ni 3 and 0 nj 3: new_state [row[:] for row in state] new_state[zero_i][zero_j], new_state[ni][nj] new_state[ni][nj], new_state[zero_i][zero_j] state_tuple tuple(tuple(row) for row in new_state) if state_tuple not in visited: visited.add(state_tuple) heapq.heappush(heap, (cost1heuristic(new_state), cost1, new_state)) return -1实现时需要注意启发函数必须满足可采纳性不大于实际代价使用优先队列确保每次扩展最有希望的节点状态哈希要高效避免成为性能瓶颈5. 数学与计算几何5.1 快速数论变换在多项式乘法和大数运算中FFT/NTT比朴素算法更高效。NTT在模数意义下计算避免了浮点精度问题const int MOD 998244353; // 原根为3 const int G 3; void ntt(vectorint a, bool invert) { int n a.size(); for(int i1, j0; in; i) { int bit n 1; for(; jbit; bit1) j ^ bit; j ^ bit; if(i j) swap(a[i], a[j]); } for(int len2; lenn; len1) { int wlen powmod(G, (MOD-1)/len, MOD); if(invert) wlen powmod(wlen, MOD-2, MOD); for(int i0; in; ilen) { int w 1; for(int j0; jlen/2; j) { int u a[ij], v (long long)a[ijlen/2]*w % MOD; a[ij] (u v) % MOD; a[ijlen/2] (u - v MOD) % MOD; w (long long)w * wlen % MOD; } } } if(invert) { int inv_n powmod(n, MOD-2, MOD); for(int x : a) x (long long)x * inv_n % MOD; } } vectorint multiply(vectorint const a, vectorint const b) { vectorint fa(a.begin(), a.end()), fb(b.begin(), b.end()); int n 1; while(n a.size() b.size()) n 1; fa.resize(n); fb.resize(n); ntt(fa, false); ntt(fb, false); for(int i0; in; i) fa[i] (long long)fa[i] * fb[i] % MOD; ntt(fa, true); return fa; }使用时需要注意数组长度必须是2的幂次模数需要存在原根结果可能超过模数需要处理进位5.2 凸包与旋转卡壳计算几何问题在竞赛中往往考察经典算法的实现精度和鲁棒性。比如求平面点集的凸包def cross(o, a, b): return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]) def convex_hull(points): points sorted(points) lower [] for p in points: while len(lower) 2 and cross(lower[-2], lower[-1], p) 0: lower.pop() lower.append(p) upper [] for p in reversed(points): while len(upper) 2 and cross(upper[-2], upper[-1], p) 0: upper.pop() upper.append(p) return lower[:-1] upper[:-1]旋转卡壳算法可以在凸包基础上求最远点对def rotating_calipers(points): hull convex_hull(points) n len(hull) if n 1: return 0 if n 2: return dist(hull[0], hull[1]) res 0 j 1 for i in range(n): while abs(cross(hull[i], hull[(i1)%n], hull[(j1)%n])) \ abs(cross(hull[i], hull[(i1)%n], hull[j])): j (j 1) % n res max(res, dist(hull[i], hull[j])) return res实现细节凸包排序要正确处理共线点叉积判断方向时要考虑精度问题旋转卡壳的指针移动条件要准确6. 字符串处理高级技巧6.1 后缀自动机应用后缀自动机(SAM)是处理复杂字符串问题的利器。比如统计不同子串数量struct State { int len, link; mapchar, int next; }; struct SAM { vectorState st; int last, size; SAM() { st.emplace_back(); st[0].len 0; st[0].link -1; last 0; size 1; } void extend(char c) { int p last; int curr size; st.emplace_back(); st[curr].len st[p].len 1; while(p 0 !st[p].next.count(c)) { st[p].next[c] curr; p st[p].link; } if(p -1) { st[curr].link 0; } else { int q st[p].next[c]; if(st[p].len 1 st[q].len) { st[curr].link q; } else { int clone size; st.emplace_back(); st[clone].len st[p].len 1; st[clone].next st[q].next; st[clone].link st[q].link; while(p 0 st[p].next[c] q) { st[p].next[c] clone; p st[p].link; } st[q].link clone; st[curr].link clone; } } last curr; } long long count_substrings() { long long res 0; for(int i 1; i size; i) { res st[i].len - st[st[i].link].len; } return res; } };使用SAM时要注意构造过程中的克隆节点处理空间复杂度是线性的但常数较大扩展字符集时需要调整数据结构6.2 AC自动机优化多模式匹配问题中AC自动机比单独使用KMP更高效。比如敏感词过滤class ACNode: def __init__(self): self.children {} self.fail None self.output [] def build_ac_automaton(patterns): root ACNode() # 构建trie树 for pattern in patterns: node root for c in pattern: if c not in node.children: node.children[c] ACNode() node node.children[c] node.output.append(pattern) # 构建fail指针 from collections import deque queue deque() root.fail root for c, child in root.children.items(): child.fail root queue.append(child) while queue: current queue.popleft() for c, child in current.children.items(): fail current.fail while fail ! root and c not in fail.children: fail fail.fail if c in fail.children: child.fail fail.children[c] else: child.fail root child.output child.fail.output queue.append(child) return root def ac_search(text, root): result [] current root for i, c in enumerate(text): while current ! root and c not in current.children: current current.fail if c in current.children: current current.children[c] for pattern in current.output: result.append((i-len(pattern)1, pattern)) return result优化点包括使用双数组Trie减少内存占用输出链压缩加速匹配过程批处理模式串提高构建效率7. 竞赛实战策略7.1 测试用例设计在竞赛中设计有效的测试用例可以快速验证算法正确性。我常用的测试策略包括极小规模案例空输入、单元素完全随机生成的大数据特殊构造的极端情况完全升序/降序序列已知答案的经典案例比如测试排序算法时可以用以下Python代码生成测试数据import random def generate_sorting_tests(): tests [] # 空数组 tests.append(([], [])) # 单元素 tests.append(([1], [1])) # 已排序 tests.append(([1,2,3,4,5], [1,2,3,4,5])) # 逆序 tests.append(([5,4,3,2,1], [1,2,3,4,5])) # 随机案例 for _ in range(5): arr [random.randint(-100,100) for _ in range(20)] tests.append((arr, sorted(arr))) # 含重复元素 tests.append(([3,1,4,1,5,9,2,6,5,3], [1,1,2,3,3,4,5,5,6,9])) return tests7.2 调试与性能分析竞赛中的调试技巧往往决定成败。我总结的几个实用方法使用断言验证不变量打印关键变量状态比较暴力解法的输出使用性能分析工具定位瓶颈例如在C中可以使用chrono进行简单计时auto start chrono::high_resolution_clock::now(); // 待测试代码 auto end chrono::high_resolution_clock::now(); auto duration chrono::duration_castchrono::microseconds(end-start); cout Time taken: duration.count() microseconds endl;对于更复杂的性能分析Linux环境下可以使用perf工具perf stat -e cache-misses,branch-misses ./program8. 模板代码管理8.1 常用代码片段高效竞赛选手通常会维护自己的代码模板库。我的核心模板包括快速输入输出针对不同语言常用数据结构和算法数学工具函数调试宏定义例如C的快速IO模板#include bits/stdc.h using namespace std; #define fastio ios::sync_with_stdio(false); cin.tie(0) #define forr(i,a,b) for(int i(a);i(b);i) #define forn(i,n) forr(i,0,n) #define sz(c) ((int)c.size()) #define zero(v) memset(v, 0, sizeof(v)) #define pb push_back #define mp make_pair #define dbg(v) cerr #v (v) endl typedef long long ll; typedef pairint,int ii; const int INF 1e9;8.2 自动化测试框架为常用算法编写测试框架可以节省大量时间。比如二分查找的测试框架def test_binary_search(): test_cases [ ([], 1, -1), ([1], 1, 0), ([1], 2, -1), ([1,3,5,7], 1, 0), ([1,3,5,7], 3, 1), ([1,3,5,7], 5, 2), ([1,3,5,7], 7, 3), ([1,3,5,7], 0, -1), ([1,3,5,7], 2, -1), ([1,3,5,7], 4, -1), ([1,3,5,7], 8, -1), ] for arr, target, expected in test_cases: result binary_search(arr, target) assert result expected, fFailed on {arr}, {target}: expected {expected}, got {result} print(All tests passed!)这个框架可以扩展到其他算法只需替换binary_search实现和测试用例即可。
1. 竞赛算法全景概览算法竞赛是检验程序员解决问题能力的终极试金石。从ACM-ICPC到Google Code Jam从LeetCode周赛到企业编程挑战优秀的竞赛选手往往掌握着一套完整的算法武器库。这套武器库不是简单的方法堆砌而是经过千锤百炼的思维框架与实战策略。我在过去五年参与各类编程竞赛的经历中发现真正决定比赛胜负的往往不是知道多少种算法而是能否在高压环境下快速识别问题本质并选择最合适的解决路径。这需要我们对算法有系统性的认知——了解每类算法的适用场景、时间代价和实现陷阱。2. 基础数据结构与算法2.1 线性结构处理技巧数组和链表是竞赛中最基础的数据结构但高手与新手的区别往往体现在对这些基础结构的极致优化上。比如在滑动窗口问题中双指针技巧可以将O(n²)的暴力解法优化到O(n)。一个经典案例是求解最小覆盖子串问题def minWindow(s: str, t: str) - str: from collections import defaultdict need defaultdict(int) for c in t: need[c] 1 left 0 valid 0 res window defaultdict(int) for right in range(len(s)): c s[right] if c in need: window[c] 1 if window[c] need[c]: valid 1 while valid len(need): if not res or right - left 1 len(res): res s[left:right1] d s[left] left 1 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return res这个实现中有几个关键点需要注意使用valid变量而非直接比较字典避免频繁的字典遍历收缩左边界时的条件判断顺序会影响正确性边界条件处理要考虑空字符串的情况2.2 树形结构的高级应用二叉树相关问题是竞赛中的常客。除了基本的遍历算法竞赛中更常考察变形应用。比如最近公共祖先(LCA)问题使用Tarjan离线算法可以在O(nα(n))时间内处理大量查询struct DSU { vectorint parent; DSU(int n) : parent(n) { iota(parent.begin(), parent.end(), 0); } int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } void unite(int x, int y) { x find(x); y find(y); if(x ! y) parent[y] x; } }; void tarjan(int u, vectorvectorint tree, vectorvectorpairint,int queries, DSU dsu, vectorint ancestor, vectorbool visited) { visited[u] true; ancestor[u] u; for(int v : tree[u]) { if(!visited[v]) { tarjan(v, tree, queries, dsu, ancestor, visited); dsu.unite(u, v); ancestor[dsu.find(u)] u; } } for(auto [v, idx] : queries[u]) { if(visited[v]) { int lca ancestor[dsu.find(v)]; // 处理查询结果 } } }实际比赛中更常用的其实是基于二进制拆分的在线LCA算法虽然理论复杂度是O(nlogn)预处理O(logn)查询但实现更简单且常数更小。3. 动态规划进阶策略3.1 状态压缩技巧当问题规模较小时状态压缩DP可以解决许多看似复杂的问题。比如经典的旅行商问题(TSP)可以用位运算表示访问过的城市集合def tsp(dist): n len(dist) dp [[float(inf)] * n for _ in range(1n)] dp[1][0] 0 # 从城市0出发 for mask in range(1n): for u in range(n): if not (mask (1u)): continue for v in range(n): if mask (1v): continue new_mask mask | (1v) if dp[new_mask][v] dp[mask][u] dist[u][v]: dp[new_mask][v] dp[mask][u] dist[u][v] # 回到起点 res float(inf) for u in range(1, n): res min(res, dp[(1n)-1][u] dist[u][0]) return res这个实现有几个优化点预处理距离矩阵避免重复计算使用位运算快速判断状态包含关系循环顺序确保子问题先被计算3.2 数位DP实战数位DP常用于解决与数字各位相关的计数问题。比如统计区间[L,R]内满足某种条件的数字个数。一个典型实现框架如下int dfs(int pos, int state, bool limit, bool lead, const string num) { if(pos num.size()) return check(state) ? 1 : 0; if(!limit !lead dp[pos][state] ! -1) return dp[pos][state]; int res 0; int up limit ? num[pos]-0 : 9; for(int d 0; d up; d) { bool new_lead lead (d 0); int new_state new_lead ? state : update(state, d); res dfs(pos1, new_state, limit (d up), new_lead, num); } if(!limit !lead) dp[pos][state] res; return res; } int solve(int x) { memset(dp, -1, sizeof dp); string num to_string(x); return dfs(0, 0, true, true, num); }实际应用中需要注意状态设计要足够表达必要条件前导零处理要小心特别是当0本身也是有效数字时记忆化条件要正确limittrue或leadtrue时不能直接取缓存值4. 图论算法精要4.1 网络流建模艺术最大流问题在竞赛中往往需要巧妙的建模。比如二分图匹配可以转化为最大流问题但有些题目需要更复杂的转换。考虑下面这个例题有m个项目和n个学生每个项目需要一定数量的学生每个学生有可参与的项目列表问是否能满足所有项目需求。这可以通过多源点多汇点的网络流模型解决def solve(projects, students): # projects: list of (requirement, [student indices]) # students: list of [project indices] m len(projects) n len(students) size 1 m n 1 # 源点 项目 学生 汇点 graph [[0]*size for _ in range(size)] # 源点到项目 for i in range(m): req projects[i][0] graph[0][1i] req # 项目到学生 for i in range(m): for s in projects[i][1]: graph[1i][1ms] 1 # 学生到汇点 for j in range(n): graph[1mj][-1] 1 return max_flow(graph, 0, size-1) sum(p[0] for p in projects)关键点在于项目需求转化为源点到项目的边容量每个学生只能参与有限项目通过学生到汇点的容量限制项目与学生间的边表示匹配可能性4.2 启发式搜索优化对于状态空间巨大的问题A*算法往往比普通BFS更高效。比如八数码问题使用曼哈顿距离作为启发函数def astar(start, target): def heuristic(state): h 0 for i in range(3): for j in range(3): val state[i][j] if val ! 0: x, y (val-1) // 3, (val-1) % 3 h abs(x-i) abs(y-j) return h heap [] heapq.heappush(heap, (heuristic(start), 0, start)) visited set() visited.add(tuple(tuple(row) for row in start)) while heap: _, cost, state heapq.heappop(heap) if state target: return cost zero_i, zero_j next((i,j) for i in range(3) for j in range(3) if state[i][j]0) for di, dj in [(0,1),(1,0),(0,-1),(-1,0)]: ni, nj zero_idi, zero_jdj if 0 ni 3 and 0 nj 3: new_state [row[:] for row in state] new_state[zero_i][zero_j], new_state[ni][nj] new_state[ni][nj], new_state[zero_i][zero_j] state_tuple tuple(tuple(row) for row in new_state) if state_tuple not in visited: visited.add(state_tuple) heapq.heappush(heap, (cost1heuristic(new_state), cost1, new_state)) return -1实现时需要注意启发函数必须满足可采纳性不大于实际代价使用优先队列确保每次扩展最有希望的节点状态哈希要高效避免成为性能瓶颈5. 数学与计算几何5.1 快速数论变换在多项式乘法和大数运算中FFT/NTT比朴素算法更高效。NTT在模数意义下计算避免了浮点精度问题const int MOD 998244353; // 原根为3 const int G 3; void ntt(vectorint a, bool invert) { int n a.size(); for(int i1, j0; in; i) { int bit n 1; for(; jbit; bit1) j ^ bit; j ^ bit; if(i j) swap(a[i], a[j]); } for(int len2; lenn; len1) { int wlen powmod(G, (MOD-1)/len, MOD); if(invert) wlen powmod(wlen, MOD-2, MOD); for(int i0; in; ilen) { int w 1; for(int j0; jlen/2; j) { int u a[ij], v (long long)a[ijlen/2]*w % MOD; a[ij] (u v) % MOD; a[ijlen/2] (u - v MOD) % MOD; w (long long)w * wlen % MOD; } } } if(invert) { int inv_n powmod(n, MOD-2, MOD); for(int x : a) x (long long)x * inv_n % MOD; } } vectorint multiply(vectorint const a, vectorint const b) { vectorint fa(a.begin(), a.end()), fb(b.begin(), b.end()); int n 1; while(n a.size() b.size()) n 1; fa.resize(n); fb.resize(n); ntt(fa, false); ntt(fb, false); for(int i0; in; i) fa[i] (long long)fa[i] * fb[i] % MOD; ntt(fa, true); return fa; }使用时需要注意数组长度必须是2的幂次模数需要存在原根结果可能超过模数需要处理进位5.2 凸包与旋转卡壳计算几何问题在竞赛中往往考察经典算法的实现精度和鲁棒性。比如求平面点集的凸包def cross(o, a, b): return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]) def convex_hull(points): points sorted(points) lower [] for p in points: while len(lower) 2 and cross(lower[-2], lower[-1], p) 0: lower.pop() lower.append(p) upper [] for p in reversed(points): while len(upper) 2 and cross(upper[-2], upper[-1], p) 0: upper.pop() upper.append(p) return lower[:-1] upper[:-1]旋转卡壳算法可以在凸包基础上求最远点对def rotating_calipers(points): hull convex_hull(points) n len(hull) if n 1: return 0 if n 2: return dist(hull[0], hull[1]) res 0 j 1 for i in range(n): while abs(cross(hull[i], hull[(i1)%n], hull[(j1)%n])) \ abs(cross(hull[i], hull[(i1)%n], hull[j])): j (j 1) % n res max(res, dist(hull[i], hull[j])) return res实现细节凸包排序要正确处理共线点叉积判断方向时要考虑精度问题旋转卡壳的指针移动条件要准确6. 字符串处理高级技巧6.1 后缀自动机应用后缀自动机(SAM)是处理复杂字符串问题的利器。比如统计不同子串数量struct State { int len, link; mapchar, int next; }; struct SAM { vectorState st; int last, size; SAM() { st.emplace_back(); st[0].len 0; st[0].link -1; last 0; size 1; } void extend(char c) { int p last; int curr size; st.emplace_back(); st[curr].len st[p].len 1; while(p 0 !st[p].next.count(c)) { st[p].next[c] curr; p st[p].link; } if(p -1) { st[curr].link 0; } else { int q st[p].next[c]; if(st[p].len 1 st[q].len) { st[curr].link q; } else { int clone size; st.emplace_back(); st[clone].len st[p].len 1; st[clone].next st[q].next; st[clone].link st[q].link; while(p 0 st[p].next[c] q) { st[p].next[c] clone; p st[p].link; } st[q].link clone; st[curr].link clone; } } last curr; } long long count_substrings() { long long res 0; for(int i 1; i size; i) { res st[i].len - st[st[i].link].len; } return res; } };使用SAM时要注意构造过程中的克隆节点处理空间复杂度是线性的但常数较大扩展字符集时需要调整数据结构6.2 AC自动机优化多模式匹配问题中AC自动机比单独使用KMP更高效。比如敏感词过滤class ACNode: def __init__(self): self.children {} self.fail None self.output [] def build_ac_automaton(patterns): root ACNode() # 构建trie树 for pattern in patterns: node root for c in pattern: if c not in node.children: node.children[c] ACNode() node node.children[c] node.output.append(pattern) # 构建fail指针 from collections import deque queue deque() root.fail root for c, child in root.children.items(): child.fail root queue.append(child) while queue: current queue.popleft() for c, child in current.children.items(): fail current.fail while fail ! root and c not in fail.children: fail fail.fail if c in fail.children: child.fail fail.children[c] else: child.fail root child.output child.fail.output queue.append(child) return root def ac_search(text, root): result [] current root for i, c in enumerate(text): while current ! root and c not in current.children: current current.fail if c in current.children: current current.children[c] for pattern in current.output: result.append((i-len(pattern)1, pattern)) return result优化点包括使用双数组Trie减少内存占用输出链压缩加速匹配过程批处理模式串提高构建效率7. 竞赛实战策略7.1 测试用例设计在竞赛中设计有效的测试用例可以快速验证算法正确性。我常用的测试策略包括极小规模案例空输入、单元素完全随机生成的大数据特殊构造的极端情况完全升序/降序序列已知答案的经典案例比如测试排序算法时可以用以下Python代码生成测试数据import random def generate_sorting_tests(): tests [] # 空数组 tests.append(([], [])) # 单元素 tests.append(([1], [1])) # 已排序 tests.append(([1,2,3,4,5], [1,2,3,4,5])) # 逆序 tests.append(([5,4,3,2,1], [1,2,3,4,5])) # 随机案例 for _ in range(5): arr [random.randint(-100,100) for _ in range(20)] tests.append((arr, sorted(arr))) # 含重复元素 tests.append(([3,1,4,1,5,9,2,6,5,3], [1,1,2,3,3,4,5,5,6,9])) return tests7.2 调试与性能分析竞赛中的调试技巧往往决定成败。我总结的几个实用方法使用断言验证不变量打印关键变量状态比较暴力解法的输出使用性能分析工具定位瓶颈例如在C中可以使用chrono进行简单计时auto start chrono::high_resolution_clock::now(); // 待测试代码 auto end chrono::high_resolution_clock::now(); auto duration chrono::duration_castchrono::microseconds(end-start); cout Time taken: duration.count() microseconds endl;对于更复杂的性能分析Linux环境下可以使用perf工具perf stat -e cache-misses,branch-misses ./program8. 模板代码管理8.1 常用代码片段高效竞赛选手通常会维护自己的代码模板库。我的核心模板包括快速输入输出针对不同语言常用数据结构和算法数学工具函数调试宏定义例如C的快速IO模板#include bits/stdc.h using namespace std; #define fastio ios::sync_with_stdio(false); cin.tie(0) #define forr(i,a,b) for(int i(a);i(b);i) #define forn(i,n) forr(i,0,n) #define sz(c) ((int)c.size()) #define zero(v) memset(v, 0, sizeof(v)) #define pb push_back #define mp make_pair #define dbg(v) cerr #v (v) endl typedef long long ll; typedef pairint,int ii; const int INF 1e9;8.2 自动化测试框架为常用算法编写测试框架可以节省大量时间。比如二分查找的测试框架def test_binary_search(): test_cases [ ([], 1, -1), ([1], 1, 0), ([1], 2, -1), ([1,3,5,7], 1, 0), ([1,3,5,7], 3, 1), ([1,3,5,7], 5, 2), ([1,3,5,7], 7, 3), ([1,3,5,7], 0, -1), ([1,3,5,7], 2, -1), ([1,3,5,7], 4, -1), ([1,3,5,7], 8, -1), ] for arr, target, expected in test_cases: result binary_search(arr, target) assert result expected, fFailed on {arr}, {target}: expected {expected}, got {result} print(All tests passed!)这个框架可以扩展到其他算法只需替换binary_search实现和测试用例即可。
