专栏文章

贪心方法

cchenzhiyv
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio7pja4
此快照首次捕获于
2025/12/02 14:43
3 个月前
此快照最后确认于
2025/12/02 14:43
3 个月前
查看原文
2025.8.21

临项交换法

适用于将序列重排列使最优的题目。 当不知道最优序列满足什么性质时，可以使用这个方法。
例：P1080 [NOIP 2012 提高组] 国王游戏
2025.8.24 upd:[AGC023F] 01 on Tree
首先，是最优排列顺序。
容易发现，在 suma1×sumb0<sumb1×suma0suma_1 \times sumb_0 < sumb_1 \times suma_0 时，排列最优。注意这就可以直接排序了！！！。当然，不放心也可以移项，将一个点的变量放在一边，变成一个除法的形式。
文章：
1
2

线段覆盖/选最多的线段（P2255 [USACO14JAN] Recording the Moolympics S）

可以考虑按右端点排序，能放就尽量放。
注意贪心最小化/最大化的是什么

哈夫曼树的构建

构建 kk 叉哈夫曼树：
  1. 所有叶子节点对应着一个字符串，权值为出现次数。
  2. 每次选择权值前 kk 小的 kk 个节点，合并在一起，压入优先队列
  3. 注意可能节点放不满导致不优，加入一些权值为 00 的节点直到 (n−1)(n-1)%(k-1)=0 时就可以了。（为什么是这个式子：因为每一次合并会减少 k−1k-1 个节点，最后只剩 11 个节点，减少 n−1n-1 个节点，每一轮保证有 kk 个节点，所以 n−1n-1 是 k−1k-1 的倍数）
题：P2168 [NOI2015] 荷马史诗

完全图定向

首先，一个拓扑序唯一对应一个 DAG 竞赛图（有向完全图）。
根据拓扑序的定义，这个点只会向拓扑序在它后面的点连边，所以出度是 n−1n-1 到 00。
这样P8896 「DPOI-1」道路规划的出度限制条件就可以转化为序列值的限制，然后就可以做了。
具体：将满足左端点限制的点全部压入优先队列，按右端点排序，每次将这个点放入右端点最小的那个区间。

贪心的定义

贪心是通过局部最优解得到全局最优解的方法。
所以有些题目应先考虑边界怎么做，即最小的情况，再合并。
如CF525D Arthur and Walls

一种反悔贪心（？）

CF3D Least Cost Bracket Sequence
这道题中，我们可以先将所有 ? 号全部填做 ) ,然后再不合法时将 ) 变为 (,并将贡献做对应的增减。
不清楚是否能推广。
CF1085E Vasya and Templates
贪心，尽量贴着下界。
首先，再没有冲突的情况下，一直填 ll 对应，当冲突后，向前找到第一个可以调整的位置，将字典序加1，后面就可一不用管下界了，尽量小地填。
P4765 [CERC2014] The Imp
临项交换法的题目。
我们需要找出以个最优的选物品的顺序（最优策略）。考虑用邻项交换法来证明。
设有两个物品，是[v1,c1],[v2,c2][v_1,c_1],[v_2,c_2]
最优排序有 min⁡(v1−c1,v2−c1−c2)<min⁡(v1−c1−c2,v2−c2)\min(v_1-c_1,v_2-c_1-c_2) < \min(v_1-c_1-c_2,v_2-c_2)
分类讨论：
  1. v1−c1<v2−c2v_1-c_1<v_2-c_2
    同时 v1−c1−c2>v2−c2v_1-c_1-c_2 > v_2-c_2
    所以 v1−c1−c2>v1−c1v_1-c_1-c_2>v_1-c_1
    不合法
  2. v1−c1<v1−c1−c2v_1-c_1 < v_1-c_1-c_2 不合法
  3. v2−c1−c2<v1−c1−c2→v2<v1v_2-c_1-c_2 < v_1-c_1-c_2 \to v_2<v_1
  4. v2−c1−c2<v2−c2→v2−c1<v2v_2-c_1-c_2 < v_2-c_2 \to v_2-c_1 < v_2 没有用处。
所以按 vv 从小到大来排列，然后进行DP
CF1685C Bring Balance
画图，证明上界，神秘结论题。
CF436E Cardboard Box
有反悔贪心做法，也可以对普通贪心魔改。
题解
CF1493E Enormous XOR
打表找规律

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...