建模。抽 \(n\) 个 iid 样本 \(Z_i\sim N(0,\sigma^2)\)，令指示变量 \(I_i=\mathbf{1}\{|Z_i|\le2\sigma\}\)（尺度无关，取 \(\sigma=1\) 即可），则 \(I_i\overset{\text{iid}}{\sim}\mathrm{Bernoulli}(p)\)、\(p=P(|Z|\le2)\)，估计量取 \(\hat p=\frac1n\sum I_i\)——一个标准的蒙特卡洛二项实验。

推导。真值 \(p=2\Phi(2)-1\approx0.9545\)。估计量性质：\(\hat p\) 无偏，标准误（蒙特卡洛标准误）为

代入 \(n=10^4\)：\(\mathrm{SE}\approx0.00208\)，95% 置信区间 \(\hat p\pm1.96\times0.00208\approx\hat p\pm0.41\%\)。要 ±1% 精度（95% 置信）：\(n=1.96^2p(1-p)/0.01^2\approx1668\)；用最保守的 \(p(1-p)=\tfrac14\) 预算则是 \(n\approx9604\)。二项方差在 \(p\) 接近 1 时天然变小，这是本题值得点出的结构。

检验。覆盖核对：区间 \(0.9545\pm0.0041\) 恰好覆盖 95%；量级核对：精度要求每提高十倍，样本量乘一百（\(1/\sqrt n\) 法则）。另指出替代路径——直接查正态表或用 \(\mathrm{erf}\) 计算无需采样，本题考的是「给采样估计配误差棒」的方法论，与 035 章的蒙特卡洛实现衔接。

面试怎么讲。三句话：指示变量化成伯努利；标准误 \(\sqrt{p(1-p)/n}\)；报出 \(n=10^4\) 时 ±0.41%、要 ±1% 约需 1700 个样本。最后强调「估计必须配误差棒，否则无法判断 0.95 与 0.96 的差异是真是假」。

建模。锚点是 \(2^{10}=1024\approx10^3\)。\(2^{40}=(2^{10})^4\)，于是估算路径与误差都由这个替换决定。

推导。朴素估算：\(2^{40}\approx(10^3)^4=10^{12}\)。误差记账：每次替换把 \(1024\) 写成 \(1000\)，低估比例 \(\delta=24/1024\approx2.34\%\)；四次复合（乘法误差传播）：

（二项展开 \((1+\varepsilon)^4\approx1+4\varepsilon+6\varepsilon^2\) 足够。）所以真值 \(\approx1.0995\times10^{12}\)，朴素答案 \(10^{12}\) 相对真值低估约 \((1.0995-1)/1.0995\approx9.0\%\)——超出 5% 容差，必须修正为 \(1.1\times10^{12}\)（修正后误差约 0.04%）。交叉验证走第二条路：\(2^{20}=1{,}048{,}576\approx1.0486\times10^6\)，平方得 \((1.0486)^2\times10^{12}\approx1.0995\times10^{12}\)——两条独立路径会合，通过。

检验。「5% 怎么验」的一般方法就在表里：给每个近似步骤记相对误差账，乘法复合时相加（\(4\times2.34\%\approx9.4\%\)），账面超容差即判定朴素答案不合格；再用独立分解路径复核。顺带记住锚点 \(\log_{10}2\approx0.301\)：\(40\times0.301=12.04\)，同样给出 \(10^{12.04}\approx1.1\times10^{12}\)。

面试怎么讲。先给朴素答案并当场宣布它的误差上界（9% 量级），主动判它不及格，再给修正值 1.1 万亿与交叉验证。这题的满分动作是自检环节——它就是题目要求的那一半。

建模。「立方以 11 结尾」即 \(n^3\equiv11\pmod{100}\)。立方 mod 100 的结构只依赖 \(n\bmod 100\)，所以先解同余，再数落在区间里的同余类成员。

推导。个位：\(n^3\) 个位为 1，只有 \(n\) 个位为 1 可达（个位立方的个位逐一检验）。设 \(n=10k+1\)，展开：

（第二步两边约去公因子 10，模相应缩小为 10。）故 \(n\equiv71\pmod{100}\)，每个百数段恰一个解。个数：\(71,171,\dots\)，不超过 \(10^{12}\) 的成员数 \(=\bigl\lfloor(10^{12}-71)/100\bigr\rfloor+1=10^{10}\)。

检验。直接验算 \(71^3=357{,}911\)——尾数正是 11；再验 \(171^3=5{,}000{,}211\)，同样以 11 结尾（同余类平移不变）。mod 4 副检：\(11\equiv3\pmod4\)，奇数立方 mod 4 等于自身，\(71\equiv3\pmod4\) 一致。

面试怎么讲。口诀式推进：个位定 1 → 十位解同余 → 唯一类 71 → 区间计数 \(10^{10}\)。强调「同余类每 100 个数出现一次」这一不变量，验算 \(71^3\) 收尾。

建模。流式均匀抽样，标准解法是蓄水池抽样（reservoir sampling）的容量 1 版本：维护一个「当前中选者」，来一个新元素就按规则决定是否替换。

推导。算法：第 1 个元素必选中；看到第 \(i\) 个元素（\(i\ge2\)）时，以 \(\tfrac1i\) 用它替换中选者，否则保留。归纳证明均匀性：设前 \(i\) 个元素各自中选概率为 \(\tfrac1i\)。到第 \(i+1\) 个时：新元素以 \(\tfrac1{i+1}\) 直接中选；任一旧元素以 \(\tfrac{i}{i+1}\times\tfrac1i=\tfrac1{i+1}\) 保住席位——两者合成，\(i+1\) 个元素各 \(\tfrac1{i+1}\)，归纳成立，终点即全长 \(n\) 时各 \(\tfrac1n\)。

检验。小情形手工核对：\(n=2\) 时第 2 个以 1/2 替换，两者各 1/2；\(n=3\) 时元素 1 存活概率 \(\tfrac12\times\tfrac23=\tfrac13\) ✓。期望替换次数 \(\sum_{i\ge2}\tfrac1i\approx\ln n\)，一遍扫描、\(O(1)\) 额外空间。

面试怎么讲。先说约束（未知长度、单遍历）逼出在线算法；给替换规则与归纳证明；主动推广容量 \(k\) 的版本（第 \(i\) 个元素以 \(k/i\) 入池、随机踢掉一个旧成员）。实现细节与变体在 036 章的数据结构设计题里展开。

建模。记抽取次数为 \(N\)，用尾部概率求和 \(\mathbb{E}[N]=\sum_{n\ge0}P(N\gt n)\)；而 \(P(N\gt n)\) 就是「前 \(n\) 个均匀数之和不超过 1」的概率。

推导。记 \(V_n=P(U_1+\cdots+U_n\le1)\)：这是 \(n\) 维单位单纯形的体积。递推：给定 \(U_n=x\)，前 \(n-1\) 个数须落在和不超过 \(1-x\) 的单纯形里，故

检验。小情形核对：\(P(N=1)=P(U_1\gt1)=0\)（单个均匀数超不过 1）；\(P(N=2)=1-V_2=\tfrac12\)；\(P(N=3)=V_2-V_3=\tfrac12-\tfrac16=\tfrac13\)——分布 \((0,\tfrac12,\tfrac13,\tfrac18,\dots)\) 加总为 1，期望 \(2\times\tfrac12+3\times\tfrac13+\dots=e\) ✓。完整推导与仿真的更多细节见 021 章。

面试怎么讲。关键一步是把期望写成 \(\sum P(N\gt n)\) 并认出单纯形体积 \(1/n!\)；答案 \(e\) 报出后补一句「和超过任意 \(x\le1\) 的期望步数同理可算」，展示方法而非巧合。

建模。关键不变量：两只相同的虫碰撞后互换方向，等价于两只互相穿过、只交换「身份标签」。于是任意时刻的实际构型，与「\(n\) 只互不作用的幽灵各自直线爬行」完全一致，清空时间等于最远的幽灵掉落时间。

推导。第 \(i\) 只幽灵到其端点的距离 \(d_i\)：以 1/2 概率向左（距离 \(X_i\)）、1/2 向右（距离 \(1-X_i\)），\(X_i\sim U[0,1]\)，两种情形都服从 \(U[0,1]\) 且相互独立——所以 \(d_i\) 是 \(n\) 个 iid \(U[0,1]\)。清空时间 \(T=\max_i d_i\)（速度 1 米/秒，时间=距离）：

（\(n\) 个 iid 均匀的最大值期望是 \(n/(n+1)\)，密度 \(nx^{n-1}\) 积分即得。）

检验。端点核对：\(n=1\) 给 \(\tfrac12\)（单虫平均爬半米）✓；\(n\to\infty\) 趋于 1 秒——虫再多，最晚掉落也不超过 1 秒（最远端点距离至多 1 米）。单调性核对：虫越多清空越晚，\(n/(n+1)\) 单调上升 ✓。最大值期望的更多练习见 021 章。

面试怎么讲。先讲穿隧等价（一句「反弹=交换标签」），把问题化为 iid 均匀的最大值，报 \(n/(n+1)\)；用 \(n=1\) 与 \(n\to\infty\) 两个端点自证。没有穿隧这一步，任何直接模拟两人碰撞的做法都会陷入细节泥潭。

建模。递归地看：当桌上有 \(k\) 根绳（\(2k\) 个头）时，任取一个头，它与其余 \(2k-1\) 个头配对等可能；无论哪种结局，绳数都减一（成环收走一根，或两根并一根）。

推导。设 \(f(k)\) 为 \(k\) 根绳起手的期望环数。取定一头：以 \(\tfrac1{2k-1}\) 配到同绳另一头——成 1 环，剩 \(k-1\) 根；以 \(\tfrac{2k-2}{2k-1}\) 配到别绳——两绳合一，无环，剩 \(k-1\) 根。两种情形后续期望都是 \(f(k-1)\)：

解递推并改写为调和数：

渐进行为：对数增长，\(\sim\tfrac12\ln N\)——绳翻十倍，环数只加 \(\ln 10/2\approx1.15\) 个。

检验。枚举核对：\(N=1\) 必成 1 环，\(f(1)=1\) ✓；\(N=2\) 时 4 个头的 3 种完全配对中，同绳自配的那种（1 种）给 2 环、其余 2 种各给 1 环（两绳连成一圈），期望 \((2+1+1)/3=\tfrac43=f(2)=1+\tfrac13\) ✓。调和数式核对：\(H_4-\tfrac12H_2=2.0833-0.75=\tfrac43\) ✓。

面试怎么讲。递推三件套：状态（绳数）、一步转移概率（\(\tfrac1{2k-1}\) 成环）、递推式；报 \(H_{2N}-\tfrac12H_N\sim\tfrac12\ln N\)；用 \(N=2\) 的枚举当场验证。易错点：成环与合并都会让绳数减一，所以递推只降一层——别写成 \(f(k-2)\)。

建模。插值路线需要「次数 + 1」个点，两次查询必然欠定——除非选的查询点本身携带编码。核心技巧：把系数当成某个大进制下的「数字」，让一次求值把它们全部读出来。障碍是不知道系数上界，所以第一次查询用来造一个足够大的基数。

推导。两步方案：第一步查 \(q_1=p(1)=\sum_k a_k\)——系数全正，故每个 \(a_k\le q_1\)。第二步查 \(q_2=p(q_1+1)\)。记 \(B=q_1+1\)：

进制表示的唯一性（每位数字严格小于 \(B\)）保证系数被无损编码；最高非零位的位置即次数 \(d\)。

检验。数值走一遍：\(p(x)=3+5x+2x^2\)。\(p(1)=10\)，\(B=11\)，\(p(11)=3+55+242=300\)；300 的 11 进制分解 \(=2\times121+5\times11+3\)，读出 \((3,5,2)\)——系数、次数全部复原 ✓。

面试怎么讲。先讲清为什么朴素插值不行（两次点值欠定），再给「自造基数」的两步：\(p(1)\) 定上界、\(p(\text{上界}+1)\) 做进制解码，配数值例子。若面试官追问「系数不是整数呢」：正实系数无法用进制编码，退路是数值优化或额外查询——边界诚实交代。另一个理论彩蛋：若允许「精确读取实数值」，单次 \(p(\pi)\) 因 \(\pi\) 的超越性已唯一确定整系数多项式（无非零整系数多项式在 \(\pi\) 取零），只是不给出构造性的解码算法——两查询的进制方案才是可执行的。

建模。套用知识点二的五段框架，把「一堆建议」变成一个带相关结构的组合问题。

推导（作答口径）。目标先行：确认优化的是期望收益还是风险调整收益（决定后面所有权重语言）。单条建模：估计每条建议的期望超额与波动，样本小则收缩。相关维度：估相关矩阵、算等效信号数 \(N_{\text{eff}}\)——一堆相关 0.9 的建议只当一条用，聚类去冗余。组合落地：逆方差或风险平价定权重、凯利式约束定尺度、扣除成本与容量，期望优势付不起成本的建议直接弃。验证闭环：样本外回测与滚动更新，防「建议本身过拟合」。

检验。反例自检：若所有建议其实都是「利率上行」同一逻辑的马甲，零相关假设会严重高估分散、超配该因子——所以相关性一段不可跳过；若建议期望全为零但方差为正，扣完成本后期望为负，最优动作是「全不做」——框架允许空答案也是合理的输出。

面试怎么讲。按五段口头走，每段一个工具名（收缩、\(N_{\text{eff}}\)、风险平价、凯利、样本外）；结尾主动说「最重要的单一动作是查相关性——它决定这堆建议到底是情报还是回声」。开放题的评分在结构完整性，工具细节点到即可。

建模。喷泉 \(i\) 覆盖区间 \([i-r_i,\ i+r_i]\)，问题是「用最少的给定区间覆盖 \([1,n]\)」——经典区间覆盖贪心。

推导。贪心规则：维护已覆盖右端点 \(\text{cur}\)（初始为 0，覆盖到 \([1,\text{cur}]\)）；每轮在所有满足「左端点 \(\le\text{cur}+1\)」（即能接上现有覆盖）的喷泉中，选右端点最远者开启，更新 \(\text{cur}\)；直到 \(\text{cur}\ge n\)。正确性（交换论证，exchange argument）：设最优解第一座喷泉不是贪心所选，则用它替换为贪心那座不会让后续覆盖变差（右端点更远），归纳可知贪心解与最优解同规模。复杂度：按位置顺序扫描、每座喷泉入桶一次，\(O(n+\max r)\) 或排序后 \(O(n\log n)\)。

检验。小情形核对：\(n=3\)、\(r=[1,1,1]\)：区间 \([0,2],[1,3],[2,4]\)，贪心先开 2 号（覆盖 \([1,3]\)），一步完成 ✓（开 1 号则还需第二座）。可达性核对：\(r_i\ge1\) 保证位置 \(i\) 至少能被自己浇到，贪心每步至少推进 1，必然终止。

面试怎么讲。先把「点覆盖」翻译成「区间覆盖」，再说贪心规则与交换 argument，报复杂度；主动提「若 \(r\) 很大则退化为跳跃游戏式线性扫」。这类区间扫描思想在编程分册（如 033 章的滑动窗口）会以实现题形式重现。