算法杂题复盘：贪心、BFS、二分与并查集实战指南

“最近做的杂题”这个标题是我给这段时间刷题状态起的代号。那几天没盯着一类专题死磕而是每天挑两三道类型各异的算法题来练贪心、动态规划、图论、搜索混着做。有人觉得杂题不成体系不如按专题刷高效但我的实际体感恰恰相反刷杂题才是维持手感、暴露短板最直接的方式。你被一道题卡住往往不是某个算法不会而是没认出它到底考的是哪个套路杂题治的就是这种“识别不出来”。这篇就当阶段复盘把最近这批题里值得说道的几道、踩过的坑以及现在在用的复盘方法一起整理出来给同样泡在算法训练里的朋友做个参考。1. 这批杂题是怎么筛出来的1.1 杂题不是乱题我给自己定了三个标准按专题刷题时你清楚知道这题要用二分、那题必然需要状态压缩思维其实是被标签喂饱的。但真实比赛和面试里没有任何人告诉你考点所以杂题的价值不在“量多”而在“陌生”。我给自己定了三条筛选标准来决定哪些题值得加到当天清单里第一题面读完五秒内能写出完整代码的直接跳过除非今天只是想热手第二优先选“题干表面和实际解法隔着一步”的题比如表面是模拟、实际要贪心表面是图论、实际要离线排序第三每天至少有一道需要连续写二十分钟以上的中档题不允许全场都是秒杀题也不允许直接上硬核偏题。这个标准其实是在模拟考场上的真实状态你看到一道题第一反应往往不是某个算法而是一堆含糊的直觉。能把这种直觉训练成“我看出来这题要转化成什么”杂题就刷出价值了。1.2 难度配比简单热身中档为主难度上我按 简单 : 中档 : 中上 ≈ 1 : 3 : 1 来配。举个例子我最近某天的三道题是这样的一道基础栈模拟当热身确认手没生一道贪心加优先队列考“换谁出局”的决策一道状态压缩BFS考二维坐标之外还要压几把钥匙。三题难度拉开又不至于某一道占用所有时间导致第二天不想碰题。时间控制也很重要。杂题最大的陷阱是一头扎进某道题死磕两小时结果一天就没了。我的底线是三道题合计不超过两个半小时其中单题最多四十五分钟。超时直接看题解把卡住的点记下来这就够了——刷杂题本来就是见多识广的过程不是每道题都要靠硬磨做出来才有效果。1.3 选题来源先看问题绝不先看标签我挑题的来源比较随意题库按标签随机抽、别人题单里划掉名字的题、或者网上随手翻到的题都有可能。但有一条铁律读题前绝对不看这道题挂在哪个算法分类下面。先看到“动态规划”标签脑子会自动朝DP方向使劲等于提前给了你一半答案杂题的“识别训练”效果就废了。我现在的习惯是拿到题先只看题干在草稿纸上写下两个判断——“我一眼觉得这题考什么”和“这题如果考错了替代方案是什么”。做完之后再去看题解验证。这个动作成本极低但对训练审题能力非常有效最近好几道卡住的题根因都出在第一句话判断上。2. 四道值得记录的题拆解与还原思路2.1 贪心题目标读错差点把“完成数量”做成“延误最小”先说道让我翻车的贪心。题面很朴素n 项任务每项给耗时 t 和截止时间 d从 0 时刻开始串行执行同一时刻只能做一个任务任务执行顺序可以任意安排问最多能完成多少项。我第一眼把这个题和经典的“最小化总延误”混在一起了于是按照“最早截止时间优先”直接扫描遇到处理不完就跳过。这个做法在求“总延误最小”时是对的但在这道题里只保证顺序不超时并不保证完成数量最大。问题出在哪举个例子已经选了一个耗时极长的任务现在来了一个截止时间稍晚但耗时很短的任务总量超了正确的做法是把手里那个耗时最长的任务扔掉而不是把刚来的短任务扔掉。我当时写出来的逻辑恰好是后者样例都过了到构造数据才暴露。正解很短按截止时间升序处理用小根堆保存当前所有已选任务的耗时每加入一个新任务就累加总耗时一旦总耗时超过当前任务的截止时间就从堆里弹出耗时最大的任务把它的耗时从总耗时里减去。结束时堆的大小就是最多能完成的任务数。import heapq n int(input()) tasks [] for _ in range(n): t, d map(int, input().split()) tasks.append((d, t)) tasks.sort() heap [] cur 0 for d, t in tasks: heapq.heappush(heap, t) cur t if cur d: cur - heapq.heappop(heap) print(len(heap))为什么这个贪心是对的等权完成数量只看“完成的个数”不看每个任务的价值。那么任何可行集合都可以按截止时间排序如果集合里存在一个耗时很长的任务而集合外存在一个截止时间更晚但耗时更短的任务把它俩交换完成数量不减少截止约束也不更容易被破坏。重复交换最终一定收敛到“留下截止早的和耗时短的任务”。这个交换论证是理解这类贪心的关键比背模板有用得多。顺带说一个变体如果题目改成“给定任意顺序判断能否全部完成”那只需要按截止时间排序后扫描一遍超过就 false连堆都不需要。只有“最大化完成数量”才需要及时弹出耗时最大的任务。这两个只差一个字的问法解法完全不同是我这次最有收获的点。2.2 状态压缩BFSvisited数组里藏着一整类漏解第二道是典型的状态压缩BFS。网格里有起点、出口、几把钥匙和几扇门每扇门需要对应编号的钥匙才能进拿到钥匙后永久持有墙不能走问从起点到出口且集齐所有钥匙的最短步数。普通BFS想当然会记录 (x, y) 作为访问状态。但这题不行同一个格子有没有某把钥匙是两种完全不同性质的通行状态。第一次路过一道门时没钥匙只能折返绕一圈拿到钥匙再回来就能穿过如果 visited 只记坐标就会把“没钥匙时来过”标记成“来过”导致有钥匙之后正确的路线被拦截。钥匙数量一般不超过 6 把可以用整数的二进制位表示钥匙集合1 表示已持有状态直接定义成 (x, y, mask)。转移的核心就两步。遇到钥匙mask | 1 key_id把对应位置置 1。遇到门判断(mask door_id) 1是否为 1不是 1 就不能走。模板长这样from collections import deque dy [-1, 1, 0, 0] dx [0, 0, -1, 1] # dist[y][x][mask]mask 范围是 [0, 2^k) # 初始状态 (sy, sx, 0)目标状态 (ey, ex, full) q deque() q.append((sy, sx, 0)) dist[sy][sx][0] 0 while q: y, x, mask q.popleft() for i in range(4): ny, nx y dy[i], x dx[i] if not (0 ny n and 0 nx m): continue cell grid[ny][nx] if cell #: continue if A cell F: # 遇到门 door_id ord(cell) - ord(A) if (mask door_id) 1 0: continue nmask mask if a cell f: # 遇到钥匙 key_id ord(cell) - ord(a) nmask | 1 key_id if dist[ny][nx][nmask] INF: dist[ny][nx][nmask] dist[y][x][mask] 1 q.append((ny, nx, nmask))状态数量是 n × m × 2^k本题 k 很小所以空间完全够。这个题给我的教训是凡是走迷宫类题目只要“进入格子后能力会变化”visited 就必须包含这个能力状态。生活里也好理解一栋楼有门禁你第一次走到门口没有卡和办完卡后再次走到门口是截然不同的两种通行条件用“到过门口”一次标记覆盖两种情况必然漏状态。2.3 二分答案check函数比二分本身更考验细节第三道是万物皆可二分的典型。数组里全是正整数一次操作可以把任意一个数变成 ceil(v/2)给定操作次数上限 m问最终数组中最大值最小能压到多少。这种“最大值最小”的题第一反应就应该是二分答案。我直接二分最终的最大值 x然后写一个 check(x) 判断把所有数降到不超过 x需要的操作次数是否小于等于 m。check 完全不需要动数组原值对每个大于 x 的 v不断地v (v 1) // 2并计数直到 v x。这个上取整写法是这次踩坑重点后文单独说。def check(x): cnt 0 for v in a: while v x: v (v 1) // 2 cnt 1 if cnt m: return False return True l, r 1, max(a) while l r: mid (l r) // 2 if check(mid): r mid else: l mid 1 print(l)边界有几个细节。左边界不是 0因为正整数反复减半最终最小只能是 1右边界直接取 max(a)表示一次操作都不做时的答案。二分模板我用的是“满足条件时收缩右边界不满足时推左边界”最后 l 就是答案。这个模板配合 check 的单调性——x 越大越容易满足越小越难——是二分答案类题最稳固的组合。为什么我强烈推荐把二分模板背熟因为这类题的难点从来不在二分本身而在怎么把“最值问题”翻译成“给定一个上界能否满足”的判定问题。翻译对了 check后面就是套路。这道题就是把“最大值最小”翻译成了“给定上界 x每个数要操作多少次”。2.4 离线并查集在线难题靠排序变成静态扫描第四道题我印象最深因为它同时揉进了排序、双指针和并查集三个基础工具。无向图有 m 条带权边q 次询问每次给一个阈值 w问有多少对点之间能通过边权不超过 w 的边互相连通。在线做法最大问题是每来一个 w都要重新扫一遍图或做一次全源连通性判断q 一旦上万复杂度直接失控。这题的正确打开方式是离线。先把边按边权升序排序再把查询按 w 升序排序然后一个指针扫边把所有边权不超过当前 w 的边全部通过并查集合并维护一个全局变量 total表示当前所有连通块内部点对数之和。合并两个连通块时新增的点对数就是两个块大小相乘加到 total 里。处理完这批边以后当前查询的答案就是 total。class DSU: def __init__(self, n): self.parent list(range(n)) self.size [1] * n def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, a, b): ra, rb self.find(a), self.find(b) if ra rb: return 0 if self.size[ra] self.size[rb]: ra, rb rb, ra gain self.size[ra] * self.size[rb] self.parent[rb] ra self.size[ra] self.size[rb] return gain edges.sort() queries sorted(queries) # 每个元素是 (w, idx) ptr 0 total 0 ans [0] * q for w, idx in queries: while ptr len(edges) and edges[ptr][0] w: _, u, v edges[ptr] total dsu.union(u, v) ptr 1 ans[idx] total复杂度是 O(m log m q log q m α(n))。这个题最大的思维转折点在于所有查询的阈值是单调递增的边按边权排序后只需要加边不需要删边并查集恰好只支持加边。把在线问题倒过来看删边问题也可以反过来变成加边问题——这种“倒过来想”的套路正是杂题里最容易出现、也最值得记录的部分。3. 做杂题途中踩过的坑细节失误全复盘3.1 上取整写错二分的check直接失真2.3 那道题里我把每次操作的v (v 1) // 2写成v v // 2。差了一个符号check 统计出的操作次数少了很多二分的答案偏大。为什么会犯这种错因为整数除法默认向下取整遇到奇数时ceil(v/2)和floor(v/2)是不相等的。例如 v3正确操作一次后是 2v//2直接变成 1等于一次操作做了两次的效果计数失真。排查这个方法很好用构造一个超小样例。a[3, 2]m 足够大目标 x1。3 降到 1 需要两次操作3 → 2 → 12 降到 1 需要一次。总共三次。如果按错写法3 → 1 只需要一次总数变成两次一测就露馅。以后凡是出现上取整、下取整混用的地方我都会多写一行注释# (v 1) // 2 表示 ceil(v / 2)。3.2 位运算和比较运算混在一起括号一定要给足2.2 里判断“是否有某把钥匙”的写法是mask (1 k)判断“是否为 0”时我一开始写成了mask (1 k) 0。在某些语言里比较运算符的优先级高于位运算这一行会被解析成mask ((1 k) 0)结果完全不是本意。表现形式很迷惑有时候判断恰好对有时候整段逻辑抽风非常浪费时间。我现在的规矩是位运算和其他运算混用时一律用括号把位运算单独包起来比如(mask door_id) 1。不要觉得多写括号啰嗦这种问题一旦上了几千组数据的评测里出现调试成本远高于写括号的成本。这个坑本质不是算法问题是语言细节问题但杂题里遇到多了就会明白细节稳定也是做题能力的一部分。3.3 大数据量下逐行读入时间直接翻倍有一道题的输入规模到了百万级我一开始用input()逐行读测试大数据时明显卡顿改成像下面这种一次读入后才顺畅import sys data sys.stdin.buffer.read().split() ptr 0 n int(data[ptr]); ptr 1 a list(map(int, data[ptr:ptr n]))一次读入和逐行读入的差距在数据量大时可以差出一倍以上。代价是可读性变差所有取数都要手动维护指针。我的取舍是数据量小或者时间充裕时用直观写法知道是百万级输入直接上read().split()省得后面被卡常。这种性能细节在刷杂题时很少注意但恰好是正式场合最容易翻车的一环。3.4 并查集合并时漏掉 size 更新答案越算越错2.4 的并查集我最初在 union 里只更新了 parent忘了更新 size。前几次合并看着没问题因为小数据碰巧正确答案等到出现三个以上连通块合并时total 的增量全都算错了而且错得很隐蔽——不是直接崩溃是答案逐渐偏小。链式合并最明显先合并两个大小 1 的块total1再合并一个大小 1 的块时应该 total2如果 size 没更新就会按 1×1 加成 1答案当场失真。这类问题没有捷径只能靠经验形成习惯模板代码里凡是改了 parent后面必然跟一行 size 更新。另外 find 尽量写迭代版避免递归深度过大时爆栈。这些模板细节看着不起眼但杂题里的并查集题几乎没有一道是单纯考模板的都是藏在别的包装下面模板一旦不稳整道题跟着崩。4. 杂题复盘方法从“做过”到“会做”4.1 题解笔记只记两件事一眼结论和卡点以前我刷题也记笔记但经常把整个题解抄一遍复习时看到密密麻麻的字反而不想看。现在每道杂题我只记两行一眼结论和卡点。比如 2.1 的一眼结论是“等权最大完成数量按截止排序丢最大耗时”卡点是“误以为求延误最小”。2.4 的一眼结论是“带权阈值连通性边排序查询排序并查集”卡点是“没想到把询问也排序”。为什么只记这两行因为杂题考的就是“快速识别套路”一眼结论负责存储识别特征卡点负责提醒我上次在哪里想歪。一周后复习时只看一眼结论如果能顺着推出完整做法说明真懂了如果盯着结论发呆那就把这题标记为重写。4.2 按转化技巧归类而不是按算法名字归类整理错题本时我逐渐把分类标准从“贪心、DP、图论”改成“转化技巧”。比如我现在本子上的类别是离线化把在线问题通过排序变成静态扫描二分答案化把最值问题变成判定问题状态压缩化把坐标之外的状态压进一个整数反转化删边难做就倒过来加边。这么分类的原因很简单杂题里真正卡住你的从来不是“没想到用并查集”而是“没看出这个题可以离线处理”或者“没意识到要枚举状态”。按转化技巧归类复习时练的恰好是最薄弱的“翻译”环节而不是已经背熟的算法模板。4.3 三十分钟法则和隔天重写单题思考超过三十分钟没有清晰路线我就直接看题解但看完以后不许关掉题解就觉得完事。我的流程是先看题解搞懂思路合上所有资料在编辑器里独立重写一遍重写时卡住的地方就是真正没懂的地方比看十遍题解都有价值。第二天再把同一道题重写一遍这次不看任何参考能写出来才算吸收。这套流程看起来笨但对杂题特别有效。杂题不成体系不靠重复很容易一忘全忘。一次认真重写加一次隔日重写比当时反复读三遍题解的记忆留存率高得多。4.4 改条件出题一道杂题当三道练遇到值得记的题我会在笔记最后加一个“变体想法”区把题目的条件往难里或往偏里改一改只写思路不去写代码。比如 2.2 那把钥匙数量从 6 改到 20状态压缩直接爆状态数就得考虑双向 BFS 或者别的搜索剪枝2.4 不允许离线排序每来一个查询必须在线回答那就得往树链剖分之外的结构上想。这种“改条件”的练习本质上是在训练边界感知你知道一种解法成立的前提是什么也知道前提一旦被破坏该往哪个方向补救。刷杂题刷到最后练的就是这个。这批杂题里我还没有搞明白的、以及做出来但解法很丑的题都先记在清单上。杂题就是这样永远有下一批永远有下一道让你卡住又让你拍大腿的题。慢慢来比较快。