面灵AI→

一场算法笔试题型复盘:抽屉原理、博弈论到最小生成树

轮次
笔试
时间
2026-10
来源
牛客网

《面试题目》

  1. 第一题:签到题。
  2. 第二题:数论(抽屉问题)。
  3. 第三题:博弈论。
  4. 第四题:图论(最小生成树),按贪心考虑似乎也可以。
  5. 第五题:构造。
  6. 第六题:位运算。

《参考解析》

这套题的分布很典型

六道题里只有一道是纯签到,其余五道分别落在数论、博弈、图论、构造、位运算——这是校招算法笔试常见的「广覆盖」配比:不考复杂数据结构(没有线段树、树状数组),但每个方向的经典模型都要认得出来。准备这类卷子的顺序应该是「识别题型 → 套模型 → 处理边界」,而不是刷难题。

数论里的抽屉原理

抽屉原理的题面通常是「n 个数里必有两个满足某关系」「长度为 n 的序列必有某性质」,提示词是范围与数量不匹配:给的取值空间比元素个数小,或者要证明存在性。做法往往是把元素按某个量(模 k 的余数、前缀和)分组成若干「抽屉」,元素数超过抽屉数就必有落在一起的两个。看到「必存在」「一定有」这类表述,先想抽屉;看到前缀和,先想同余相等。

博弈论:先手胜负的判定套路

校招笔试的博弈题基本是三类:Nim 类(异或和为零则后手胜)、取石子变种(按可达状态推 SG 值)、以及纯逻辑对称博弈(先手能否靠对称策略必胜)。判断入口是「双方最优、无随机」,那就写状态转移或找不变量。要注意边界:只剩一堆、只允许取连续段、以及「不能操作者输」与「不能操作者赢」的差别。

最小生成树:为什么贪心是对的

Kruskal(按边权排序 + 并查集)和 Prim(按点扩展 + 优先队列)都是贪心,正确性来自切分性质:对任意把点集分成两半的切割,横跨切割的最小边一定属于某棵最小生成树。复杂度上稀疏图用 Kruskal O(E log E),稠密图用 Prim 堆优化 O(E log V)。原帖提到「按贪心去考虑好像也可以」——如果题目只要求给出一种最优连接方案且边权有特殊结构,确实可能退化成一个排序加并查集的直接贪心;但要分辨「最小生成树」与「最短路径」的区别,前者连接所有点、后者只关心两点间距离。

构造题与位运算

构造题的通用策略是先看小规模(n=1,2,3)手工找规律,再猜一个通式,最后验证边界;常见目标是「构造一个排列使相邻差满足条件」「构造矩阵使行列和相等」,多数能用奇偶分组或首尾交错搞定。位运算题的高频点:x & (x-1) 消掉最低位的 1(数 1 的个数)、x & -x 取最低位的 1(树状数组的基础)、异或的自反性(找唯一出现一次的数)、以及按位贪心(从高位到低位逐位确定答案)。写的时候注意有符号移位与溢出的语言差异。

考试节奏建议

签到题先做完保证有分;数论和位运算通常代码短、想通就过,优先做;博弈与构造容易卡在思路上,先写个暴力打表看规律,别硬推;图论模板题如果记得模板就写,不记得就先拿部分分(比如只处理连通块内部)。这类卷子拉开差距的往往不是最后一题,而是中间那两道「想通了五分钟、想不通半小时」的题,给自己设一个 15 分钟的止损线。