【重置版】贪心及分类讨论

ty_mxzhn · 2025-03-08 10:46:45 · 算法·理论

前言

本总结收录了贪心以及少量分类讨论的题目，有配套的贪心及分类讨论练习。

贪心概论

贪心的大部分题目，都是“大海捞针”形的，也就是说，在极其多的解中找出极值。

这些解大多都有一些特点，这才让贪心法可以实施。具体情况具体分析。

一些定义：

一个解优于另一个解指在最小值中，一个解比另一个解要小，而如果我们要求的是最大值就反过来，一个解比另一个解要大。

劣于是优于的反义词。

调整法或 Exchange Argument

假设我们有一些衡量解的指标 k_{i,X}。

如果对于任意的解 X 都可以找到另一个解 X'，而且 \forall i[k_{i,X'} \le k_{i,X}]，另外要求 X' \ge X，那么最优解的每一个 k 都可以调整到 0。

正文

这里并没有什么通用的算法，于是我们可以直接开始一题一题的讲。

基础算法剖析

上课问题

题意：有一些线段，你要选出一些线段使得这些线段不交而且线段的个数最大（区间图的最大独立集）

解：按照右端点位置从小到大贪心选择。

证：

假设这样得到为 A。

反证法，如果另一个解 X 优于 A，并且 A 和 X 之间前 k 条线段是相同的，这一个 k 在所有优于 A 的解中是最大的。

那么 X 的第 k+1 条线段的右端点不能比 A 的还要小。

所以假设把 X 的这条线段换成 A 的第 k+1 条线段，可以得到另一个解 X'，而这个解和 A 之间的前 k+1 条线段都是相同的。

因为 X' \ge X > A 所以 X' > A，但是 X' 和 A 之间前 k+1 条线段都是相同的，矛盾，原命题得证。

最小生成树的 Kruskal 算法

证：

假设这样得到为 A。

反证法，如果另一个解 X 优于 A，并且 A 和 X 之间有 k 条边是相同的，这一个 k 在所有优于 A 的解中是最大的。

从 X 中和 A 不同的边中选出一条边 s，然后可以把 X 分成两半点集 X_1 和 X_2，A 中有且仅有一条边满足 u \in X_1 并且 v \in X_2，记这条边为 r，有 Kruskal 算法得 w_s \ge w_r。

所以假设把 X 中的 s 换成 r，可以得到另一个解 X'=X-s+r，而这个解和 A 之间有 k+1 条线段都是相同的，并且 X' \ge X。

因为 X' \ge X > A 所以 X' > A，但是 X' 和 A 之间有 k+1 条线段都是相同的，矛盾，原命题得证。

大家有没有发现这道题的证明过程和上道题有点像？

最短路的 Dijkstra 算法

不是很好讲的，因为这个专栏其实偏题单性质所以不讲了。

例题略解

[CSP-S2019] 树上的数

本题考查了选手对特殊性质的把握，对于树结构的剖析。

本题可以通过分类讨论菊花图和链来制作构造方案。

[CSP-S2020] 贪吃蛇

本题考查了一个经典博弈论问题的拓展，实现也是难点。

贪心的方案可以考虑一些特殊点，其中叶子是一棵树最松动的部分，根是一棵树最牢固的部分，可以考虑他们。

[NOIP2015 普及组] 推销员

本题考查了一个简单数学模型的直接最优化。

不要急着 dp，要先考虑最终答案的形态。

[MtOI2018] 崩坏3？非酋之战！

本题可以剖析每种操作的作用，进行模拟，然后得出结论，舍弃不可能的解。

大家可以试试做小 xi 的这道题。

这就是缩小法。

[AHOI2017/HNOI2017] 大佬

同上的同时，可以分离互不相干的子问题。

同类题还有：[十二省联考 2019] 皮配。

CF521D Shop

考虑逐层调整法，每次调整问题的一个部分，这样解就已经可以收敛到唯一的极大值，也就是最大值了。

[ABC219H] Candles

这题是关路灯加强版，但是好像有一些问题？？？

有一些解，它们永远不会成为最优解，所以这些解就可以放着不管了。这就是扩大法。

[ZJOI2020] 序列

有一种较为简单的方法是线性规划对偶，大家可以自己学习。

另一种方法可以考虑假设我们已经确定了一种方案，这个方案有什么问题，哪里可以改进？

[NOI2019] 序列

有一种方法是反悔贪心，另一种是模拟费用流。

不过这两种本质上是一样的，因为费用流的退流就是一种反悔。

[HNOI2019] 序列/Sonya and Problem Wihtout a Legend

这是保序回归问题。

本题涉及到一些数学推导，这是对题目中凸性质条件的观察，求导以后就可以发现端倪。

另一道题目是本题的弱化版，只需要考虑 dp 数组的凸性质即可。

另一道题目也可以不利用凸性质，直接贪心。

加工生产调度/ [HNOI/AHOI2018] 排列/[USACO05NOV] 奶牛玩杂技/GDCPC 2024 C/国王游戏

邻项交换法题目，是贪心的一个分支。

在使用这种方法的时候，要注意题目性质。

[AGC023F] 01 on Tree/种树

这也是邻项交换法的，不过在树上。

但是注意我们可以先制作一个看起来就很对的贪心，比如说去掉限制？

假如说我们出现了一个很优秀的点，那么把它的父亲选上以后它自己肯定接着被选上。所以说这两个点就可以合并了。

CSP-S 那道更加极端，直接将这个点到根上的所有点都合并就是对的了，不需要交换法。

[NOI2017] 蔬菜

时光倒流？

其实这种题目主要要看题目的特殊性质，这道题的性质就是卖完一种菜只会对之后有影响。

[NOI2010] 超级钢琴/Shopping Plans/异或粽子

kth set 问题。每次考虑一种从第 i 大的解转移到第 i+1 大的解的方式。这个转移是从每个数的下一个 kth 转移中选出来的。

Shopping Plans 还运用了分离子问题，其实也都是从每一个子问题中的每一个 kth set 的后继中选啦。

[CSP-S2019] 划分/[NOIP2021] 方差

这个真的不好总结，懒了。只能说多观察多思考多睡觉吧。

CF1387B2 Village (Maximum)

重心是一棵树上，可以避免某一棵下属子树的大小超过一半的点。

所以他可以避免绝对众数，根据经典结论，当一个序列没有绝对众数时可以通过重排两两不同。

但是因为【数据删除】，所以这个构造不仅可以用堆，也可以用一些奇奇怪怪的手法实现。比如说构造后序遍历，然后 i \leftrightarrow i+ \dfrac{n}{2}。

可以分析上下界！一条边最多会被经过他分离出的两个连通块大小之间的最小值次。

[ABC318F] Octopus

缩小法，后面忘了。

好吧其实这题只需要考虑数轴上哪些点才能被选到答案就好了。可行的决策点只有一小部分。

[ABC334C] Socks 2

调整法，后面忘了。

好吧其实这题只需要考虑数轴上两两匹配的方式就好了。

要对匹配的交错有一定的观察。比如假设我们有 a \leftrightarrow c,b \leftrightarrow d(a\le b\le c\le d) 那么显然 a \leftrightarrow b,c \leftrightarrow d(a\le b\le c\le d) 是更好的选择。a \leftrightarrow d,b \leftrightarrow c(a\le b\le c\le d) 也可以调整。

所以全部不相交或者是包含就是最好的选择，也是唯一的选择。

[ABC344F] Earn to Advance/[CSP-J 2023] 公路

这题是边走边反悔贪心了。

设计 dp 的方式值得思考，因为值域过大，所以选择了记录反悔的决策在哪里。

校内模拟赛某题

考虑 dij 的贪心过程，这个转移是单调的，所以直接 dij 就是对的。

校内模拟赛某题/Triangle Formation/Prime Coloring/「CZOI-R1」三角形与树

答案在某个阀值之上是恒定的。这种题真的不喜欢在模拟赛遇到啊。

[ABC322G] Two Kinds of Base

分类讨论底数是 1,2,3 或 >3，然后可以直接做。

[省选联考 2024] 魔法手杖

按位贪心，舍弃不可能解。

详细题解。

[ABC221G] Jumping sequence/Aulvwc

贪心优化 01 满背包，O(n\max w_i)。

另一个做法是 bitset+随机化。

具体的来说，先贪心的从小到大能放就放。然后可以证明这样子选出来的东西调整为正解的过程中，波动是 O(\max w_i) 级别的。

设置 f_{l,r,w} 为区间 [l,r] 是否能调整出 w 的波动参数。这玩意是 O(n^2 \max w_i)。

继续设计判定转最优化（因为有单调性质）。g_{r,w} 为最大的 l 满足 f_{l,r,w}=1。

这样还是 O(n^2 \max w_i) 啊。把 dp 转移的图画出来，贪心省去一个 1D 的转移，就是 O(n \max w_i) 的。

[AGC018C] Coins

反悔贪心，或者是邻项交换法，之前我出的题里面撞了这道。

先把铜币去掉。假设我们已经确定了要给哪些人金或银币，那么我们可以直接把 a_i-b_i 较大的给金币。

那么我们维护这个给金币的端点，两边跑优先队列即可，怎么样，很小清新吧。

[十二省联考 2019] 春节十二响/Village(Minimum)

一个子树可以看成贪心中的一个最优子结构。

事实上树形 dp 也是这个套路，不过这种最优子结构往往需要被贪心的证明。

对于第二道题，每一个子树是一个最优子结构，那么假设有两个子树内的点走出了这个子树，那么这两个点就可以匹配在一起而不是走出子树。所以每个子树内只会有 0/1 个点会走出子树，根据奇偶性判断即可。

构造方案的话，每个子树都只有至多一个点走出子树，那么只需要暴力构造 u 和 v 的子树内的匹配就好了。

[ABC347D] Popcount and XOR

这样的一个位运算最优化，可以逐位拆分，步步贪心。

似曾相识燕归来

和树上的数一样，分类讨论边界情况，尝试构造适配方案。

不一样的是，这题可以考虑答案的上下界，步步紧逼。运用了一点置换环的知识。

「CROI · R2」01-string

简单分类讨论 + 贪心，舍弃不可能解的类型。记得最后套一个 dp。

「CROI · R2」落月摇情

结合 Kruskal 的超级钢琴类的 kth 问题。

「EZEC-6」造树

先不管权值，你可以直接想到一种贪心方法。

但是有了权值呢？你可以考虑调整法。

假设最大值和次大值没有匹配，那么他们总可以调整成一个匹配的方案，同理，最后肯定可以调整成一个朴素的贪心模式。

P3441 [POI2006] MET-Subway

来个简单的测测实力。

每条路径直接伸到叶子下面，这样子问题转化成给你 2l 个点标记，然后问你这些点匹配组成的连通块的大小最大是多少？

观察到，假设叶子个数 \le 2l 我们就直接构造完了。但是假设有一层点数 \le 2l 那么上面的点都报送了，下面的点只能有 2l 个了。

Dirty Arkady's Kitchen

懒得讲了，自己去看。

Squid Game

可能一般的问题可以通过 O(1) 的代价转化成特殊的问题呢。

对于本题，假设路径形如 x \to \mathrm{lca} \to y 那么这些点可以用一次操作全部消掉。

[POI2007] POW-The Flood/终末螺旋（Light Bulbs）

考虑贪心。假设我们把这个图建出来就可以明了我们究竟选哪些点是不优的。

P10747 [SEERC2020] Neo-Robin Hood

读懂题以后发现其实就是 [AGC018C] Coins 加了点东西，具体的来说，你需要二分一个数 k 然后在两边选数。

https://www.luogu.com.cn/article/qm8kqdc9

https://www.luogu.com.cn/article/i4qu4u5v

https://www.luogu.com.cn/article/lsi802om

https://www.luogu.com.cn/article/nftt3psx

https://www.luogu.com.cn/article/et5o96kl

https://www.luogu.com.cn/article/1gvxm1z5

https://www.luogu.com.cn/article/ezfz2pwd

https://www.luogu.com.cn/article/l27a5zg1

https://www.luogu.com.cn/article/9he926c7 https://www.luogu.com.cn/article/4g4c6l65

反悔贪心

反悔贪心，拓展了贪心的策略，用来让贪心更加覆盖全局。

Buy One, Get One Free

P1484 种树

P2107 小Z的AK计划

Cardboard Box

这是个经典题啊。

考虑反悔贪心，每次假设我们要多放置一颗星。

把一个两颗星的拿掉一颗星，然后找一个没星的变成两颗星。
把一个一颗星的拿掉一颗星，然后找一个没星的变成两颗星。
找一个没星的位置变成一颗星。
找一个有一颗星的变成两颗星。

手膜一下可以发现他可以覆盖到任何情况，所以它是对的。

考虑数据删除，假设我们已经确定了要玩哪些关，那么我们可以直接把 b_i-a_i 较小的关玩到两颗星，于是我们按照 b_i-a_i 排序，枚举一个分界线，左边的都玩到两颗星，右边的都玩到一颗星。

如果直接把他卷积了可能可以做，但是我们可以观察到函数的性质，然后直接三分优化即可。（可能也可以 wqs 二分）

April Fools' Problem

这是个经典题啊。

考虑先 wqs 二分，然后每次从左往右扫，先把当前这个准备了。我们可以假设准备完如果不打印就不花时间。

然后每次准备完了以后可以打印，每次可以打印最小的准备代价 a，或者是反悔之前最大的打印代价 b。

然后就做完了，时间复杂度 O(n \log^2 n)。

后记

本专栏持续更新，但是你可以认为这是个题单。