第九章. 计算机科学（ACM班）— 面试备考指南

核心培养特色

• 算法核心主导：课程以数据结构、算法设计与分析、计算理论为骨架，远超普通计算机专业的训练强度
• 竞赛实战文化：常态化训练、校赛/省赛/区域赛/世界总决赛层层选拔，强调团队三人协作与抗压
• 荣誉课程 + 本研衔接：数学分析（荣誉）、离散数学（荣誉）、算法（荣誉），优秀者可提前进入导师课题组
• 国际视野：ACM-ICPC 为国际赛事，全英文题目、英文环境，是通往全球顶尖深造的跳板
• 数理硬底子：ACM 班尤其看重组合数学、数论、图论等"竞赛数学"功底，而非单纯工程编码

模板一：学术竞赛导向型（适合有信息学奥赛/算法基础的同学）

适用：有 NOIP/CSP/NOI 经历或自学过算法的同学。重点用具体算法名词和复杂度意识体现专业度。

模板二：综合素质型（适合数理强、竞赛背景弱但思维好的同学）

适用：无竞赛奖项但数理优异、有自学习惯的同学。用"刷题量 + 复杂度直觉 + 具体优化案例"弥补奖项缺失。

模板三：英文版（Academic / Competition-Oriented，全英文自我介绍）

适用：所有申请 ACM 班的同学都应准备一份流利英文自我介绍。ACM-ICPC 为国际赛事，面试官极可能用英文追问，建议背诵至脱口而出。

自我介绍要点总结

• 时长严格 1.5–2 分钟（约 250–350 字 / 英文 180–220 词），切忌超时
• 结构：我是谁 → 算法亮点（竞赛/刷题/复杂度直觉） → 为什么选 ACM 班 → 未来规划 → 致谢
• 多抛"算法钩子"（KMP / 网络流 / DP / 复杂度），引导面试官问你擅长的问题
• 英文版务必练到自然流畅，避免明显背诵感

这是算法面试的"开胃题"，但区分度极高：只会背"都是 O(n log n)"只能及格，能讲清最坏情形与优化策略才能脱颖而出。关键要谈 pivot 选择、已近乎有序的输入、以及稳定性。

归并排序（Merge Sort）：无论最好/最坏/平均，时间复杂度都是严格的 O(n log n)。它把数组递归地二分，再线性合并两个有序子序列，递归深度恒为 log n，每层合并工作量 O(n)。最坏情况不会变差，因为它不依赖数据分布。代价是需要 O(n) 的辅助空间，且不是原地排序；它是稳定的。

快速排序（Quick Sort）：平均复杂度 O(n log n)，但最坏情况退化为 O(n²)。最坏发生在每次划分都极不均衡时——典型场景是：pivot 总是选到当前区间的最小或最大元素。例如对已近乎有序的数组若固定取首元素作 pivot，或对所有元素相等的数组，划分退化成"一边 n-1、一边 0"，递归深度变成 n。归并排序对这类输入依然稳健。

如何避免快排最坏情况：① 随机化 pivot（randomized quicksort）——随机选一个元素交换到首/尾位置再划分，期望复杂度回到 O(n log n)，实际竞赛几乎必用；② 三数取中（median-of-three）取首、中、尾三元素的中位数作 pivot，对近乎有序输入很有效；③ 对小数组切换到插入排序（工程实现如 introsort）。工程上的 std::sort 多采用 introsort：快排 + 堆排序兜底（递归过深时切换），保证最坏 O(n log n)。

按"是否基于比较"可分成两大类：

一、基于比较的排序（下界 Ω(n log n)）：

• 快速排序：平均 O(n log n)，原地、缓存友好、常数小，是通用排序首选；缺点是不稳定、最坏 O(n²)（靠随机化缓解）。
• 归并排序：稳定、最坏也是 O(n log n)，适合链表排序和外排序（磁盘上无法一次载入内存的大文件）；缺点是 O(n) 额外空间。
• 堆排序：原地 O(n log n)，但不稳定、缓存不友好、常数较大，实际很少单独用，多用于优先队列和 introsort 兜底。

二、非比较排序（可突破 Ω(n log n) 下界，但受限于数据范围）：

• 计数排序（Counting Sort）：O(n + k)，k 为值域范围。适合整数且值域不大的场景，如给 0–100 分的成绩排序。稳定。
• 基数排序（Radix Sort）：O(d·(n + k))，按位（个位→高位）用稳定子排序（通常计数排序）逐位排。适合定长整数或字符串（如手机号、身份证），且可做到稳定。SSD/数据库中有应用。

选型直觉：通用数据用快排；要稳定或数据在磁盘用归并；整数且范围小用计数/基数；实时取最值用堆。面试中能说出"为什么工程实现（如 Java/Python/C++）在小数组用插入、大数组用快排/introsort"会体现工程素养。

请解释什么是动态规划，并给出一个具体例子及其时间复杂度。

Dynamic Programming (DP) is a method for solving problems by combining the solutions of overlapping subproblems. It applies when a problem exhibits two properties:

• Optimal substructure: an optimal solution contains optimal solutions to its subproblems.
• Overlapping subproblems: the same subproblems are solved repeatedly, so we cache (memoize) or build them bottom-up to avoid exponential recomputation.

DP is essentially smart recursion with memory. A typical implementation stores results in a table dp[state]; the answer is derived by a state definition plus a transition equation.

Example — Longest Increasing Subsequence (LIS): given an array a[1..n], find the length of the longest strictly increasing subsequence.

Define dp[i] = length of LIS ending exactly at position i. Transition: dp[i] = 1 + max{dp[j] | j < i and a[j] < a[i]}. The naive DP runs in O(n²). We can optimize it to O(n log n) by maintaining the smallest tail of all increasing subsequences of length k using a binary search (patience sorting). The O(n²) version is fine to present in an interview; mentioning the O(n log n) improvement shows depth.

Why it matters: DP turns many exponential brute-force searches (e.g., edit distance, knapsack, shortest paths on DAGs) into polynomial time, which is the core reason it appears everywhere from bioinformatics to competitive programming.

朴素匹配在主串 S、模式串 P 上，遇到失配就把模式串整体右移一格、重新比对，最坏 O(n·m)。问题：它丢弃了已经匹配上的信息。

KMP（Knuth–Morris–Pratt）的核心思想：失配时，利用"已匹配前缀"的内部结构，让模式串尽可能远地、且不回头地右移。它预计算一个 next 数组（部分匹配表 / failure function）。

next 数组定义：next[i] 表示模式串 P[0..i] 这个前缀中，最长的、真相等的"前缀 = 后缀"的长度（border length）。例如 P="ABABC"，next[4]（前缀 "ABABC"）的最长 border 是 "AB"，长度 2。

如何求 next（自身匹配，O(m)）：令 j = next[0] = 0 为当前已匹配长度，从 i=1 遍历：

• 若 P[i] == P[j]，则 next[i] = ++j；
• 否则若 j > 0，令 j = next[j-1]（沿 border 回退）后继续比较；
• 若 j == 0 且仍不匹配，则 next[i] = 0。

匹配阶段：主串指针 i 只前进不回退（这是 O(n) 的关键）。当 S[i] != P[j] 时，令 j = next[j-1] 即可把模式串右移而不重扫主串。整体时间 O(n + m)，空间 O(m)。

为什么快：朴素法在失配时主串指针回退，存在大量重复比较；KMP 通过 next 把"已经确认的相等字符"复用，主串指针单调递增，所以线性。KMP 是"用预处理换匹配效率"的典范，也是 AC 自动机（多模式匹配）的基础。

两者解决同一问题（单源最短路），但底层假设与机制不同：

Dijkstra：基于贪心。维护一个优先队列，每次取出当前距离最小的未确定点"确定"其最短路，并用它松弛邻居。

• 复杂度：二叉堆 O((V+E) log V)；斐波那契堆可到 O(V log V + E)。
• 致命前提：所有边权非负。一旦存在负权边，贪心"确定即最优"的假设被破坏，结果错误。
• 优点：快、工程实用，是路网/地图导航的默认算法（配合 A* 更优）。

Bellman-Ford：基于动态规划/松弛。对所有边做 V−1 轮松弛：每轮尝试用每条边 (u,v,w) 更新 dist[v] = min(dist[v], dist[u]+w)。

• 复杂度：O(V·E)，明显慢于 Dijkstra。
• 能处理负权边（只要无负权环），并可在第 V 轮再松弛一次来检测负环（若还能更新则存在负环）。
• 缺点：慢；但在含负权、需判负环的金融/网络场景不可替代。

对比小结：无负权、求快 → Dijkstra；有负权或需判负环 → Bellman-Ford。进阶可提 SPFA（队列优化的 BellFA）最坏仍 O(VE)，以及 Johnson 算法借助 Bellman-Ford 重赋权后用 Dijkstra 处理全源最短路。

最小生成树（MST）是在连通无向带权图上选 V−1 条边，使总权最小且连通。两种经典算法：

Kruskal：贪心策略——把所有边按权升序排序，依次加入，若两端点不在同一连通块（用并查集判断）就保留。

• 复杂度：排序 O(E log E) + 并查集 O(E·α(V))，整体 O(E log E)。
• 适合边稀疏（E 远小于 V²）的图，且天然支持非连通图求最小生成森林。

Prim：贪心策略——从一个起点开始，维护"已在树中点集"到"树外点"的最小边，每次把最近的外点加入树（类似 Dijkstra 的堆实现）。

• 复杂度：二叉堆 O((V+E) log V) ≈ O(E log V)；用邻接矩阵暴力取最小则 O(V²)。
• 适合边稠密（E 接近 V²）的图，此时 O(V²) 版本比 Kruskal 的 O(E log E) 更优。

两者正确性都由 MST 的" cut property（割性质）"保证：横跨任意割的最小权边必属于某棵 MST。Kruskal 是"按边贪心"，Prim 是"按点扩张"。进阶可提 Borůvka 算法（并行友好）和当边权两两不同时 MST 唯一的结论。

解释时间复杂度与 Big-O 表示法的概念。为什么我们关注渐近行为而非精确运行时间？

Big-O notation describes the asymptotic upper bound of a function's growth rate. Formally, f(n) = O(g(n)) if there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀. It captures how resource usage (time or space) scales as the input size n grows, ignoring constant factors and low-order terms.

We also use related notations: Ω for asymptotic lower bound, Θ for tight bound, and o / ω for strict upper / lower bounds.

Why asymptotics, not exact time? Three reasons:

• Machine independence: exact runtime depends on CPU, compiler, cache — constants vary, but the growth rate is intrinsic to the algorithm.
• Scalability focus: for small n almost anything is fast; the interesting question is what happens when n becomes 10⁵ or 10⁶. An O(n²) algorithm may beat O(n log n) at n=10 but collapse at n=10⁵.
• Clean comparison: comparing 3n²+5n+7 vs 100 n log n exactly is messy; saying "quadratic vs linearithmic" immediately tells us which wins at scale.

Example: binary search is O(log n); linear scan is O(n). For n = 1,000,000, log₂n ≈ 20 vs 1,000,000 — the asymptotic gap is decisive. That is why complexity analysis, not wall-clock measurement, is the universal language of algorithm design.

并查集维护一个元素划分为若干不相交集合的结构，支持两个核心操作：

• find(x)：返回 x 所在集合的代表元（根）。
• union(a, b)：把 a、b 所在的两个集合合并为一个。

朴素实现下，若树退化为链，find 会 O(n)。两种优化使其近乎常数：

1. 路径压缩（Path Compression）：在 find(x) 递归找根时，把沿途每个节点直接挂到根上（parent[x] = find(parent[x])）。下次再查这些节点就是 O(1)。

2. 按秩合并（Union by Rank / Size）：合并时，把"较矮/较小"的树挂到"较高/较大"的树下面，避免树长高。记录每个根的秩（高度上界）或大小。

复杂度：单独用路径压缩已接近 O(log n)；两者结合时，单次操作均摊复杂度为 O(α(n))，其中 α 是反阿克曼函数——增长极慢，n 取宇宙原子数时 α(n) 也小于 5，实践中可视为常数。这正是 Kruskal 求 MST、连图、离线查询（如"朋友圈"问题）如此高效的原因。

两者都是在区间上做"单点/区间更新 + 区间查询"的数据结构，但能力与复杂度各有侧重。

树状数组（Fenwick Tree）：

• 用 lowbit 技巧，单点加 / 前缀和查询均为 O(log n)，代码极短、常数小、空间 O(n)。
• 擅长前缀和 / 单点更新类问题（如逆序对统计、频率计数）。
• 局限：原生只支持前缀查询；区间和靠两个前缀和相减；不易扩展到"区间最值""区间赋值"等复杂语义。

线段树（Segment Tree）：

• 把区间递归二分，每个节点代表一段区间。单点/区间更新与查询均 O(log n)，空间 O(n)（或 4n）。
• 能力极强：区间求和、区间最值、区间赋值（lazy 标记下传）、甚至维护有序集合、合并信息（如区间 GCD、区间不同的数个数）。
• 局限：代码更长、常数更大；需正确处理 lazy propagation（懒标记） 才能高效做区间更新。

选型："前缀和/频率"这类简单场景优先树状数组（好写快）；"区间最值/区间赋值/lazy"等复杂语义用线段树。进阶方向：动态开点线段树、权值线段树、可持久化线段树（主席树，用于静态区间第 k 小）。

最大流问题：给定有向图，边有容量 c(e)，源点 s、汇点 t，求从 s 到 t 能推送的最大流量。

核心概念——残量网络与增广路：对每条边维护"剩余容量"。在残量网络中找一条从 s 到 t 的增广路（路径上每条边都有正剩余容量，包括反向边），沿它推送流量 f = 路径最小剩余容量，并更新残量（正向减、反向加——反向边允许"反悔"，是算法的灵魂）。重复直到无增广路，此时流量最大（最大流最小割定理保证）。

Ford-Fulkerson：不断 DFS 找任意增广路。复杂度 O(F·E)，F 为最大流值；若容量为无理数或整数但 F 极大，可能很慢甚至不终止（实际用整数容量时 OK）。

Edmonds-Karp：改进——每次用 BFS 找最短增广路。复杂度 O(V·E²)，与具体流量值无关，稳定。Dinic 算法进一步用 BFS 分层 + DFS 多路增广，复杂度 O(V²E)，是竞赛主流。

典型应用（建模是关键）：

• 二分图最大匹配：左部连 s、右部连 t、中间容量 1，最大流即最大匹配。
• 最大权闭合子图 / 最小割：项目选择、任务依赖问题。
• 上下界网络流、最小费用最大流（边带费用，在最大流前提下最小化总费用，用于运输/分配优化）。

网络流的精髓不在代码，而在把问题建模成流——这是 ACM 竞赛中区分高手的标志性能力。

三者都保证 BST 操作（插入/删除/查找）约 O(log n)，但平衡策略不同：

AVL 树：严格平衡——每个节点左右子树高度差 ≤ 1。查找极快（树最矮），但插入/删除后旋转频繁，维护成本高。适合查找多、写入少的场景（如字典、集合的读密集型应用）。

红黑树：弱平衡——通过"红/黑"着色与五条性质（如根是黑、红节点不相邻、任一路径黑高相同）保证"最长路径 ≤ 2×最短路径"。插入/删除旋转次数少于 AVL，综合性能优。C++ std::map / Java TreeMap / Linux 内核完全公平调度器均用红黑树，是工程默认的平衡 BST。

Splay 树（伸展树）：不保证每步平衡，但每次访问（查/插/删）后把该节点通过旋转"伸展"到根（基于"局部性原理"）。无需存额外平衡信息，均摊 O(log n)。适合有访问局部性的场景（如缓存、垃圾回收中的指针结构）。

对比：AVL 查最快、维护最贵；红黑树最均衡、工程最爱；Splay 利用局部性、无需平衡字段。进阶可提 Treap（随机优先级 BST，期望 O(log n)，代码短）与 替罪羊树（重建式平衡）。

DP 设计有两步：定义状态（要算的是什么，用一个或多个维度刻画子问题）+ 写转移方程（如何由更小的子问题推出当前）。

例一：LIS。定义 dp[i] = 以第 i 个元素结尾的 LIS 长度。转移：dp[i] = 1 + max{dp[j] | j<i 且 a[j]<a[i]}，初始 dp[i]=1。答案 = max dp[i]。O(n²)；用" tails 数组 + 二分"可优化到 O(n log n)。

例二：0/1 背包。有 n 件物品，重量 w[i]、价值 v[i]，背包容量 C。定义 dp[i][c] = 考虑前 i 件、容量不超过 c 时的最大价值。转移：dp[i][c] = max( dp[i-1][c], dp[i-1][c-w[i]] + v[i] )——即"不选第 i 件"或"选第 i 件"。时间 O(nC)、空间 O(nC)，用滚动数组可压到 O(C)。

设计要点：① 状态要"无后效性"（一旦确定就不再受后面决策影响）；② 转移要覆盖所有必要子问题；③ 边界初始化要正确（背包初始为 0，计数类初始为 1 等）。进阶题型：区间 DP（石子合并）、树形 DP（树上依赖）、状压 DP（集合维度用二进制）。

解释哈希表的工作原理以及如何处理冲突。一个好的哈希函数起什么作用？

A hash table maps keys to values using a hash function h(key) that converts a key into an index in an array (the bucket array). Ideally this gives O(1) average insert, delete, and search.

Collisions are unavoidable: by the pigeonhole principle, if we have more possible keys than buckets, two keys must map to the same bucket. Two classic resolution strategies:

• Chaining (separate chaining): each bucket holds a linked list (or balanced tree, e.g. Java 8 HashMap switches to a red-black tree when a bucket gets long) of entries that hash to it. Search time is O(1 + α), where α = n/m is the load factor.
• Open addressing: when a slot is occupied, probe for the next free slot — linear probing, quadratic probing, or double hashing. Needs a lower load factor to stay efficient.

Role of a good hash function: it should be deterministic, fast to compute, and distribute keys uniformly across buckets to minimize collisions. A poor hash (e.g., one that maps many keys to the same index) degenerates the table toward O(n) lookup. Cryptographic hashes (SHA) are overkill; simple ones like polynomial rolling hash or FNV-1a suffice, and languages often mix bits (e.g., Java's hashCode() ^ (hashCode() >>> 16)) to spread high bits down.

Resizing: when load factor exceeds a threshold (commonly 0.75), the table is rehashed into a larger array to keep operations near O(1).

最大公约数（gcd）：朴素方法是枚举/质因数分解，O(√n)。欧几里得算法（辗转相除法）基于 gcd(a, b) = gcd(b, a mod b)，每次取模使数字迅速减半，复杂度 O(log min(a,b))，极快。二进制 gcd（Stein 算法）用移位避免除法，更适合底层实现。

扩展欧几里得（exgcd）：在求 gcd 的同时，找出整数 x, y 满足 ax + by = gcd(a, b)。递归实现：先递归到基例，再回代——若 (x', y') 满足 b·x' + (a mod b)·y' = d，则令 x = y', y = x' - ⌊a/b⌋·y' 即得到原方程解。

它能解决什么：

• 求解线性丢番图方程 ax + by = c：有整数解当且仅当 gcd(a,b) | c。
• 求模逆元：当 gcd(a, m)=1 时，exgcd 给出 a 在模 m 下的逆元 x（即 a·x ≡ 1 mod m），是 RSA 等密码学与大模数组合题的基础。
• 中国剩余定理（CRT）的合并步骤、贝祖等式构造。

数论是 ACM 竞赛的常青板块，常与模运算、费马小定理 / 欧拉定理、线性同余方程捆绑出现。

排列与组合：

• 考虑顺序的排列：P(n,k) = n! / (n-k)!；全排列 n!。
• 不考虑顺序的组合：C(n,k) = n! / (k!(n-k)!)，也称二项式系数，满足帕斯卡恒等式 C(n,k)=C(n-1,k)+C(n-1,k-1)。

容斥原理（Inclusion–Exclusion）：计算"至少满足若干性质之一"的元素数时，直接加会重复，需交替加减交集：

|A₁∪A₂∪…∪Aₙ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − … + (−1)ⁿ⁻¹|A₁∩…∩Aₙ|

应用举例——错排问题：n 个人各拿一个礼物，求"所有人都没拿到自己礼物"的错排数 D(n)。用容斥：总排列 n! 减去至少一人拿到自己礼物的情形，得 D(n) = n!·(1 − 1/1! + 1/2! − … + (−1)ⁿ/n!)，近似 n!/e。另一个经典应用是"不能被某些素数整除的数的个数"与"欧拉函数 φ(n) 的容斥求法"。

组合数学还常用隔板法（整数解计数）、卡特兰数（括号匹配、出栈序列）、鸽巢原理（抽屉原理，用于存在性证明）。

Nim 游戏：有 n 堆石子，两人轮流从任一堆取至少 1 颗，取光最后一棵者胜（公平组合游戏，ICG）。

必败/必胜判据（Nim-sum）：计算各堆石子数的异或和 X = a₁ xor a₂ xor … xor aₙ。

• 若 X == 0 → 必败态（P-position，先手必败）：因为无论先手怎么取，都会把异或和变成非零；
• 若 X != 0 → 必胜态（N-position）：先手总能找到一堆，把它的数改成 aᵢ xor X（更小），使新异或和归零，把必败态甩给对手。

SG 函数（Sprague–Grundy）：把 Nim 推广到任意 ICG。定义 SG(u) = mex{ SG(v) | v 是 u 的后续局面 }（mex = 未出现的最小非负整数）。单个游戏的 SG 值等价于"相当于多少颗石子的 Nim 堆"；多个独立游戏组合时，总 SG = 各游戏 SG 的异或和，判据同 Nim。SG=0 必败，SG≠0 必胜。

意义：SG 定理把一大类博弈统一成 Nim，是组合博弈论的基石。变体如"取石子限制取 1/3/4 颗""阶梯 Nim""Anti-Nim（取光者输）"都靠 SG 或异或变形求解。

字典树（Trie）：用树结构存字符串集合，每个节点代表一个前缀，边代表一个字符。插入/查找一个长为 L 的字符串为 O(L)，与集合大小无关。

• 适合：多模式匹配预处理（配合失败指针即 AC 自动机）、前缀查询（自动补全）、异或最大值（01-Trie，用于"选两个数异或最大"）、可持久化 Trie（区间异或最值）。

后缀数组（Suffix Array, SA）：把字符串所有后缀按字典序排序，得到后缀起始位置的数组 sa[]；配合 Height 数组（相邻后缀的最长公共前缀 LCP）可高效解决子串问题。

• 适合：最长公共子串（两串）、最长重复子串、不同子串计数（Σ(n − sa[i] − height[i])）、模式串在后缀数组上二分匹配（O(m log n)）。可由 O(n log n) 算法或后缀自动机（SAM）构建。

与 KMP 的关系：KMP 是单模式匹配（一个模式串对文本），用 border 思想线性匹配；Trie/AC 自动机是多模式匹配（多个模式串同时匹配）；后缀数组/SAM 则是把"文本"的所有子串结构显式建出来，适合子串统计与反复查询。三者构成字符串处理的"由简到繁"工具箱。

P（Polynomial time）：能在确定性图灵机上于多项式时间（O(nᵏ)）内求解的判定问题集合，如最短路、排序、最大流（可构造解并验证）。

NP（Nondeterministic Polynomial）：解不一定好找，但给一个候选解能在多项式时间验证的判定问题。例如 SAT（布尔可满足性）：给一组变量赋值，验证是否满足公式是容易的，但找赋值本身可能极难。注意：NP 不等于"非多项式"，而是"非确定性多项式"——所有 P 问题都属于 NP（P ⊆ NP）。

NP 完全（NPC）：属于 NP，且任何 NP 问题都能在多项式时间内归约到它。SAT 是第一个被证明的 NPC 问题（Cook–Levin 定理）。一旦某个 NPC 问题找到多项式算法，则所有 NP 问题都迎刃而解，即 P = NP。

为什么是"千禧年难题"：克莱数学研究所设 7 个 Millennium Prize 问题（各 100 万美元），P vs NP 是其中之一。它关乎"搜索/求解"与"验证"是否本质等价——若 P=NP，密码学（基于单向函数困难性）、最优化、AI 推理将被彻底改写；主流猜想是 P ≠ NP，但至今无人证明。这正是计算理论的皇冠问题。

考察竞赛中的团队决策与抗压。没有"标准答案"，但优秀选手会展现：重新读题、降级解法、及时止损、团队分工，而非死磕。

（冷静、有条理地）

两小时卡题在区域赛里并不罕见，关键是不能让这一个题拖垮整场。我会按以下步骤处理：

第一，停下来重读题。很多时候"没进展"是误解了题意或漏了约束（数据范围、边界、输出格式）。我会让没写这道题的队友重新口头讲一遍题意，交叉验证。

第二，降级策略。若正解（如需要高级数据结构/网络流）一时写不出，先交一个能拿部分分的暴力/剪枝版本，确保不空手。ICPC 是罚时累计，部分分也有价值。

第三，换人写 / 换思路。三人中常有人陷入思维定势。让另一人用完全不同的建模重写，往往能破局。我们平时训练就刻意练习"同一题两种解法互校"。

第四，设定止损点。若距比赛结束还有充足时间，给这道题最后 20–30 分钟；若已到后期，果断放弃，把精力转向其他可做题——总分最大化才是目标，而非"攻克这一题"。

归根结底，竞赛考的是理性决策而非固执。能在压力下判断"现在该放手"，本身就是高手素养。

我坦诚地说，我对人工智能和软件工程也很有兴趣——它们都极有前景。但最终选 ACM 班，是因为我认为算法与计算思维是一切的上游。

第一，ACM 班给我最硬的"计算内核"。无论以后做 AI（模型背后的优化、搜索、图神经网络算法）、做系统（调度、缓存、一致性），还是做科研，底层的算法功底决定了天花板。ACM 班把复杂度分析、图论、字符串、DP 训到极致，这是普通课程给不了的。

第二，竞赛文化培养的是"在限制下求最优"的思维。ICPC 题目往往要在内存、时间、三人协作的约束中找最优解——这种训练与真实科研/工程中的约束优化如出一辙。

第三，国际视野与同侪氛围。ACM-ICPC 是真正的全球赛场，全英文题目、与世界顶尖队伍同台。我希望在这样一种"追求优雅解法"的环境里，和一群同样痴迷算法的人一起成长。

至于 AI/软工，我会在 ACM 班夯实基础后，通过选修课、科研和项目去交叉——ACM 班从不排斥应用，它给的是"能让应用走得更远的底座"。算法是我的根基，这就是我选它的原因。

面试当天 Do's & Don'ts

• Do：开口先说复杂度；白板推导时边写边讲；遇到优化追问主动给更优复杂度。
• Do：被英文追问时，先听懂关键词（complexity / DP / graph）再作答，不必追求华丽词汇。
• Don't：只背模板不给分析——面试官要的是"你怎么想出来的"，不是"你背了什么"。
• Don't：不懂装懂、硬编复杂度；诚实说"这一点我不确定，但我的直觉是……"更得体。