来自gc课件的一些贪心题

反悔型贪心

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

CF867E

Description

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

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

n3×105n \le 3 \times 10^5

Solution

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

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

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

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

如何反悔?

依旧是上面的做法,把yy弹出堆后,将xx扔进堆里两次即可

这两次的意义是不一样的,分别是这两个意义:

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

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

CF3D

Description

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

n106n\le 10^6

Solution

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

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

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

LG P1484

Description

给出一个长度为nn的序列aia_i,你需要从中最多选出kk个互不相交的位置,使得这些位置的权值和最大

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

Solution

对于任意三个相邻位置i1,i,i+1i - 1, i, i + 1,若ai>max{ai1,ai+1}a_i > \max\{a_{i - 1}, a_{i + 1}\},那么最优方案要么选ii,要么选i1i-1i+1i+1

若只选i1i-1,不选i+1i+1,显然不如只选ii

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

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

其中li,ril_i, r_i用链表维护一下

51nod 1053

先贪心选所有的正数段,再考虑把段数减少到mm。操作方法有两种:

  • 不取一个正数段ii
  • 多取一个负数段ii

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

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

位运算相关

CF967E

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

Description

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

n105,Ai260n\le 10^5, A_i\le 2^{60}

Solution

所有满足 sk>ss \oplus k > skk 必然满足, kk的最高位在 ss 上为 0.

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

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

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

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

CF1054D

Description

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

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

n2106,k30n\le 2*10^6, k\le 30

Solution

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

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

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

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

其他

LOJ2306

51nod 1302

Description

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

n105n \le 10^5

Solution

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

19-8-16-2