「笔记」一些贪心题

来自gc课件的一些贪心题

反悔型贪心

似乎就是就是模拟费用流？

CF867E

Description

你预言了每天的股票价格 $v_i$ , 从第 $1$ 天开始,你每天可以选择卖一支股票,买一支股票,或者什么也不做

问直到第 $n$ 天结束你最多可以获得多少收益

$n \le 3 \times 10^5$

Solution

定义一次股票买卖(x, y)为，把$x$买进，$y$卖出

考虑贪心，维护一个小根堆，每次将当前股票价格扔进去

对于当前股票$x$而言，看堆里最小的元素$y$是否比它小，如果是，则做一次股票买卖$(y, x)$，答案加上$x - y$

显然，这样做会有问题，因为有可能$y$在后面的某个时刻卖出更优

如何反悔？

依旧是上面的做法，把$y$弹出堆后，将$x$扔进堆里两次即可

这两次的意义是不一样的，分别是这两个意义：

• 把$x$作为后面某一次股票买卖的买进部分
• 把$x$看成中转站，可以理解为，$x$仍旧是后面某次股票买卖$(x, z)$的买进部分，不过在现在$x$已经被卖出了。一卖一买相互抵消，就相当于进行了一次$(y, z)$的买卖，答案会加上$x - y + z - x = z - y$

这样就实现了贪心过程中的反悔

CF3D

Description

给出一个由 ( ) ? 组成的序列,第 $i$ 个 ? 可以花费 $a_i$ 的代价变成 (,花费 $b_i$ 的代价变成 ),问将其变为合法括号序列的最小代价

$n\le 10^6$

Solution

感觉这道题好像不太算反悔型贪心

先贪心把每个$?$看成$)$，尽量满足括号匹配的这个限制，并把$a_i - b_i$加入小根堆

如果某个时刻发现$($数量不够了，再从堆里取出最小的一个元素，把它替换成$($

LG P1484

Description

给出一个长度为$n$的序列$a_i$，你需要从中最多选出$k$个互不相邻的位置，使得这些位置的权值和最大

$n\le 5*10^5, k\le \frac{n}{2}$

Solution

对于任意三个相邻位置$i - 1, i, i + 1$，若$a_i > \max\{a_{i - 1}, a_{i + 1}\}$，那么最优方案要么选$i$，要么选$i-1$和$i+1$

若只选$i-1$，不选$i+1$，显然不如只选$i$

把所有$a_i$丢进一个大根堆，每次从堆里取出一个下标$x$，答案加上$a_i$，再把$a_{l_i} + a_{r_i} - a_i$丢进堆中

这就是反悔型贪心的基本操作了

其中$l_i, r_i$用链表维护一下

51nod 1053

先贪心选所有的正数段，再考虑把段数减少到$m$。操作方法有两种：

• 不取一个正数段$i$
• 多取一个负数段$i$

它们都会多付出$|sum(i)|$的代价，将三个相邻的段合并，使总段数减少1

然后就是和上一题一样的套路了

位运算相关

CF967E

其实之前写过，但是感觉写得不太清楚

Description

给你一个数列$A$，求是否存在它的一个排列使得前缀异或和单调递增。如果存在，则输出一种方案

$n\le 10^5, A_i\le 2^{60}$

Solution

所有满足 $s \oplus k > s$ 的 $k$ 必然满足, $k$的最高位在 $s$ 上为 0.

于是把所有数按二进制最高位存起来, 每次对当前前缀和从低到高 chk 每个为 $0$ 的位，是否是某个未选数最高位的落点.

如果有, 用它更新当前前缀和, 再去填下一个数, 重新找. 如果扫到最高位都没有, 就无解

显然从低位往高位贪心更优，因为选择会更多。若从高到低最多只能放$60$个数

另外，对于最高位相同的数，选择的先后顺序并没有影响

CF1054D

Description

你有一个由 $n$ 个 $k$ 位二进制数组成的序列。允许多次对任意数异或上

最大化序列中异或和不为 0 的区间个数

$n\le 2*10^6, k\le 30$

Solution

区间异或和相关可以想到转化为前缀异或和相关

补集转化，题意转化为要序列前缀异或和相等的数尽量少

因为每次只能对某个数异或上$2^k - 1$，所以对于每个数$a_i$，它只能变成$a_i \oplus (2^k - 1)$

按照$\min\{a_i, a_i\oplus (2^k - 1)\}$分类，显然将同类的数中的一半变成$a_i$，另一半变成$a_i \oplus (2^k - 1)$

其他

LOJ2306

51nod 1302

Description

$n$ 个矩形,你要把它们分成两组,使得两组最大重叠面积之和最大。矩形可旋转, 可移动

$n \le 10^5$

Solution

显然最终答案长边对长边，短边对短边