贪心

标签：偏序 cnt sum times leqslant 贪心

概述

• 贪心用于解决最优化问题。

• 例题之前的都是某次听大牛讲课的产物，可以认为，这一篇目前只是胡乱地把贪心相关的东西堆砌在一起，没有什么应有的逻辑结构。换言之，这没完工，只是建材。

组合问题

• 考虑给定一个集合 \(U\)，对 \(U\) 的子集进行询问。

组合判定

• 考虑给定一个集合 \(U\)，一个限制条件 \(P\)，问是否存在 \({A\subseteq U|P(A)}\)。

• 一般化地，称 \(I={A\subseteq U|P(A)}\)，这里 \(I\) 是一个集族，即集合的集合。

组合构造

• 给定 \(U,P\)，判断是否 \(I=\varnothing\)。如果不是，则求一个元素 \(A\in I\)。

组合最优化

• 给定估价函数 \(f(A)\)，求 \(f(A)_ {max}\)。

组合计数

• 求 \(I\) 的大小。

拟阵贪心

• 考虑一种组合最优化问题，其中 \(f(A)=\sum\limits_{x\in A} v(x)\)。

• 容易证明，如果满足以下两个条件，那么可以逐 \(k\) 个元素地贪心：

  • \(\forall A\in I,\forall B\subseteq A\in I\)。

  • \(\forall A,B\in I\And|A|-|B|=k\)，\(\exists\ C\subseteq A,|C|=k\And (B\bigcup C)\in I\)。

• 拟阵似乎和凸包有一些我尚不了解的关系，否则解释不了为什么带悔贪心和 wqs 有时等效。（信息来源：瞥到的小粉兔的回帖）

带悔贪心

• 带悔贪心是一种用于 \(f(A)=\sum\limits_{x\in A} v(x)\) 且 \(P(A)\) 有特殊性质的组合最优化问题的贪心。

• 空口无凭，给我例题。

ABC218H

• 题意：共 \(n\) 个球排成一列，选出 \(m\) 个染成蓝色，其余为红色。如果 \(c_i\neq c_{i+1}\)，那么获得 \(v_i\) 的收益。求最大收益。

• 数据范围：\(1\leqslant m<n\leqslant 2\times 10^5,0<v\leqslant 10^9\)。

• 首先我们做一个题意转化，即 \(m=\min(m,n-m)\)。于是我们染的蓝球数量一定 \(\leqslant \dfrac{n}{2}\)。

• 容易证明一定不会把相邻的两个球都染成蓝色。

• 结论1：除非 \(n\) 是奇数并且我们恰有 \(m=\lfloor\dfrac{n}{2}\rfloor\)，否则任意的有贡献的一段的段长一定为偶数（相邻段合并）。

  • 上面这个除非，其实是说我们取得了所有 \(v\)，且 \(n\) 是奇数，故为奇数。\(n\) 是偶数的时候全部取得显然也是偶数。

  • 不全部取得的时候，假设某一段有贡献的长度为奇数，则该段必然为 \([1,x]\) 或 \([x,n]\)，且 \(c_1=1\) 或 \(c_n=1\)（\(1\) 为蓝色），此时一定可以通过调整的方式多获得某个点的 \(v\)。

• 结论2：我每染一个球，必然获得一个新段的两个 \(v\)，或将已有的某个段向左/右延伸各 \(1\) 的长度。

  • 前者显然。注意我们说的是极大子段。

  • 后者的话...将 \(l\) 处染色（显然 \(l\) 处以前一定没有染色），然后将 \(l+1\sim r+1\) 的颜色反转。显然我确实只多染了一个。这就是某种“反悔”：本来染的是奇数编号的球，现在变成偶数编号的了。

• 那...就很板了对吧。直接用 p_q 维护区间就好咯。区间合并？嗯...用链表，用过的点从链表中删掉。

P1484 种树

• 题意：\(a_n\) 选 \(m\) 个，相邻两个不可同时选。\(f(A)=\sum\limits_{x\in A} v(x)\)。

• 数据范围：\(n\leqslant 5\times 10^5,m\leqslant \dfrac{n}{2},-10^6\leqslant v\leqslant 10^6\)。

• 可以看到这个和上面那个的形式并不太一样（那是边权这是点权）。不过我并不是以此为最大目的。

• 上面那个贪心在反悔时，并不用真的反悔，即，不用真的把得过的分失掉。这个显然是要的。

• 容易想到分奇偶性做前缀和每次暴力（对，正在写博客的这个小[数据删除]真的干过这事）。

• 好吧我们来谈正经的。怎么标记已经被选过的点？

• 答案是可以这样做（这不比我一开始乱嘴的优雅多了？):

  • 初始时每个点对应的决策都是“选我不选两边”。该决策的 \(id=i\)，\(id\) 是用于判 \(vis\) 或者说 \(occu\) 的。

  • 当选了某个决策，将它的 \(pre\) 和 \(nxt\) 决策的 \(id\) 的 \(vis=1\)。即，对应决策不可用。容易证明我的 \(pre\) 决策一定要求把我的左边界的左边的地方的树种上，反之亦然，故对应决策不再可用。

  • 什么，还可以翻转上述操作？嗯，很对。于是此时将我的 \(v\) 改为 \(v_{pre}+v_{nxt}-v_{now}\)。即，执行前驱决策和后继决策，将我这个决策翻转；这三个联合起来组成了一个新决策！

• 这不优雅死？

CF739E Gosha is hunting

• 我觉得很神妙的一个题，刷新了我对 wqs 和贪心的认知。

• 题意：有 \(n\) 只精灵，\(A\) 个普通球，\(B\) 个超级球。给出 \(Pa_n,Pb_n\) 表示抓到的概率，求抓到精灵数的最大期望。

• 数据范围：原题 \(n\leqslant 2\times 10^3\)。用神妙写法可以过 \(n\leqslant 10^5\)。如果用一点 nth_element 相关优化可以进一步扩大到 \(n\leqslant 10^6\)（然而在我的实测里不太有效...难道又是 STL 的 feature？至少 KDT 那里它是很快的啊）。

• 首先我们容易证明，固定一种的使用数量之后，总期望一定是一个关于另一种的使用数量的凸函数。

• 从而我们可以暴力枚举一种的使用数量，另一种暴力 wqs...等等，怎么 check？

• 唔...好问题。先谈谈带悔贪心的思路？

• 可以。暴力选出 \(Pa\) 前 \(A\) 大的，然后我们的决策无非是选一个没被选过的 \(Pb\)，选一个被选过的 \(Pb\) 和选一个被选过的 \(Pb\) 并把对应的 \(b\) 类球换到别的地方三种。

• 显然我们可以 \(O(n\log n)\) 地处理出所有决策。感觉可以优化哈，每次决策后，一类决策最多减少一个（对应决策变成二/三类的），二类决策最多减少一个，三类决策也最多减少一个（换到的地方在每轮决策中显然是唯一的）。

• 所以应该可以用 multiset 之类乱搞优化到 \(O(n\log^2 n)\)，不过不谈了。

• 回过头来谈怎么 check。在 wqs 意义下，我们其实是有“无数多个”二类球，所以我们先暴力把所有 \(Pb-K>0\) 的都选上，然后来做决策。显然此时被弹走的二类球无处可去，所以决策集几乎不变，用 nth_element 代替快排可以 \(O(n^2\log n)\)。

• 等下。我们知道，这个图像如果拉成三维的，那么它是一个广义的双参凸函数；但由固定一类球的使用数量而定下来的单参凸函数应该是彼此独立的！我们好像只用对钦定用了 \(A\) 个的那个函数求解吧？

• 于是这也是 \(O(n\log^2 n)\) 的，用 nth_element 理论为 \(O(n\log n)\)。

• 直接做 wqs 套 wqs 的 \(O(n\log^2 n)\) 做法，直觉上很可能是对的，然而是假的。理由如下：朴素 wqs 其实是要截一个合法区间，可是多维的合法区间没有平凡的维护方法。

• 对于只有一维的 wqs，我们的合法区间是截到的线段在 \(x\) 轴上的投影线段，也即一个区间。要看这个斜率合不合法，只要看限制的数量是否在这个区间内即可。

• 然而高维 wqs 截得的平面或超平面抛弃掉 \(dp\) 值这一维之后还有至少两维，以二维 wqs 为例就是合法区间是 x-y 平面上的一个投影，其应当是一个多边形或者什么东西。

• 一维的时候，我们可以简单判断限制数量是否在区间内；二维的时候，我们就得判断限制的数量 \((x,y)\) 是否在这个多边形内。

• 首先我们不知道怎么判断是否在其中，然后我们也不知道要怎么记录这个多边形，最后，一维 wqs 我们只要知道区间的左右端点也即最多 dp 两次，而要知道这个多边形我们要怎么 dp？！

例题

P2123 皇后游戏

• 题意：

  • 给出一个序列 \(m_{1\sim n}\)，每个元素有两个属性 \(a,b\)。

  • 求一种排列，使得 \(\max_{i=1}^n(c_i)\) 最小。

  • \(c_i=\begin{cases} a_i+b_i & i=1 \\ \max(c_{i-1},\sum\limits_{j=1}^i a_i)+b_i & otherwise\end{cases}\)

• 数据范围：\(T\leqslant 10,n\leqslant 2\times 10^4\)。

• 发现这东西...很像国王游戏。虽然我们还没有归类，但不妨把它们称作“邻项交换式贪心“。其特点如下：

  • 问题具有某种意义上的序列递推性；

  • 交换相邻两者具有一定的孤立性，至少没有后效性（对前面的结果不影响）；

  • 可以对邻项求出一定的偏序关系使得满足它时最优，且该偏序关系可以推广到整个序列，进而排序解决。

• 首先我们暴力拆式子，乱化一通后得到这个，其中 \(s_i=\sum\limits_{j=1}^i a_i,sum_i=a_i+b_i\)：

\[c_{i+1}=\max(c_{i-1}+b_i+b_{i+1},s_{i-1}+sum_i+b_{i+1},s_{i-1}+a_i+sum_{i+1}) \]

• 如果是首项，那么邻项交换无意义；

• 如果是后两项之一，那么我们关心的其实是 \([\max(sum_i+b_{i+1},a_i+sum_{i+1}) \leqslant \max(sum_{i+1}+b_i,a_{i+1}+sum_i)]\)，后者是交换之后的结果。

• 式左右同乘 \(-1\) 然后加上 \(sum_i+sum_{i+1}\)，简单变号（拆负号会导致 \(\max/\min\) 互换）得到 \([\min(a_{i+1},b_i)\geqslant \min(a_i,b_{i+1})]\)。该式值为 \(1\) 则不换，否则换。

• 然后 sort 之，提交，\(\text{WA 20pts}\)。

• 这是因为，该偏序关系不是严格弱序。所谓严格弱序，是满足以下四个条件的偏序关系：

  • \(\forall x,x\nless x\)（非自反性，即元素不与自己构成偏序）；

  • \(\forall x<y,y\nless x\)（非对称性，即对称的偏序不能同时成立，必有一假）；

  • \(\forall x<y \And y<z,x<z\)（传递性，略）；

  • \(\forall x\nless y \And y\nless x \And y\nless z \And z\nless y,x\nless z\)（不可比性的传递性，即偏序的不成立——双向不成立——也具备传递性）。

• 我们给出的偏序关系满足前三条，但不满足第四条。

  • 非自反性：可以考虑把我们的 \(<\) 关系改成 \(>\)，于是不等号的等号被拆掉了，容易证明两个偏序关系同构，所以我们的偏序关系满足非自反性。

  • 非对称性：证明显然。

  • 传递性：需要分类讨论，这里略去。

  • 不可比性的传递性：显然不成立，不妨考虑 \((3,5),(1,1),(2,7)\)，发现邻项不可比（注意，这导致该偏序稳定！），但跨项可比。

• 解决办法：想办法进一步限制它的不可比情况。

  • 我们偏序关系的正确性其实是显然的，问题主要在于中间插着几个不可比项的时候，会阻止我们需要比的项进行比较（我 \(\text{ABC277F}\) 的假做法问题其实就在这里）。

  • 所以解决办法就是随便加一个合理的偏序，在 \(\min=\min\) 的时候判一下。本题可以放 \(a_i<a_j\) 或 \(b_i>b_j\)，毕竟我们的偏序本身是对的，只要用任意的合理手段破坏掉不可比性就行。

• 于是问题解决。总复杂度 \(O(n\log n)\)。

[AGC009D] Uninity

• 题意略。

• 首先容易发现点分构造可以把上界卡到 \(O(\log)\)。

• 考虑贪心，显然叶节点是 \(0\)，则考虑贪心地把其父节点置为 \(1\)。

• 手推样例发现有小问题，譬如 \(fa\) 的各个儿子分别是 \(0,1\)，则 \(fa\) 必须是 \(2\)；但若 \(fa\) 的各个儿子分别是 \(0,0,2\)，则 \(fa\) 本身可以填 \(1\)，从而 \(fa\) 这棵子树是 \(2\) 而非 \(3\)。

• 猜测相邻两个 \(k\) 之间至少要有一个 \(>k\) 的数作为“分水岭”。按此模拟即可，因为值域不超过 \(O(\log)\)。当然也可以考虑三进制状压。

[AGC037B] RGB Balls

• 题意略。

• 容易构造一种最优解，即贪心地在还能取的球中取一组尽量靠前的。正确性在直觉上显然。

• 考虑从前往后扫这个序列，把所有球都拿到手里等着接后面的。手推样例，譬如 BBGGRR，直觉上发现靠前的 G 和靠前的 R 给哪个 B 或 BG 没有影响。

• 但在 BBGRRG 中，第一个 R 如果给 B，则为 \(4+4\)，否则为 \(3+4\)。

• 故猜测每次如果能结束必须结束，否则能接就接，给谁随意。至于给哪个，容易证明同时只会有一种选择（不考虑二元组的顺序）。

• 一个较为精巧的证明是，认为每走一格就要付出手上的未完成三元组数量的代价。故尽量早结束，同理，尽量接以便尽量早结束。

• 模拟即可。

[AGC028E] High Elements

• 题意略。

• 首先，容易想到按位贪心。考虑怎么 check。

• 不妨分别记两序列（尝试在这一位上放 \(0\) 以后的两序列）的前缀最大值为 \(mx_1,mx_2\)，前缀最大值个数为 \(cnt_1,cnt_2\)。

• 于是问题变成在 \(O(\log)\sim O(\sqrt{n})\) 的时间内，check 是否存在一种后续的放 \(0/1\) 方式，使得 \(cnt_1+k_1=cnt_2+k_2\)，其中 \(k_1,k_2\) 分别为两序列以后的最大值更新次数。

• 结论 \(1\)：原序列的前缀最大值（称为“旧的”）一定还是某个序列的前缀最大值（称为“新的”）。

  • 非常显然，证明从略。

• 结论 \(2\)：任意合法构造都可以转化归约到某一个序列中的前缀最大值全是旧的的构造上。

  • 不妨假设 \(A\) 中有至少一个新的，则把它丢到对面，显然使它不是前缀最大值的那个或那些数，在放它时已经在它前面。

  • 同理把对面的一个新的丢过来，于是 \(cnt_1,cnt_2\) 均 \(-1\)，仍然合法。

• 不妨设（对称的两种都试一下）以后的 \(A\) 中全是旧的，并记以后的 \(B\) 中有 \(k_1\) 个旧的，\(k_2\) 个新的，记共有 \(all\) 个旧的。

• 于是对于任意长的 \(01\) 序列的前缀，其合法，当且仅当 \(cnt_1+(all-k_1)=cnt_2+(k_1+k_2)\)。

• 变换得到 \(cnt_1-cnt_2+all=2k_1+k_2\)。式左为定值，式右相当于剩余的原序列在“旧的记两次，新的记一次”意义下的 LIS 长度。

• 然后我们可以证明，如果 \(2k_1+k2=x(x\geqslant 2)\) 成立，那么 \(2k_1+k_2=x-2\) 也成立。因为我们可以把一个 \(k_1\) 丢到对面去，在这个式子的意义下相当于 \(-2\)，\(k_1\) 不够就扔 \(k_2\)。

• 故我们要验证的其实是某一段后缀的带权 LIS 在奇偶情况下分别的最大值。显然可以 \(O(n\log n)\) 实现，然后按位贪心即可。

[AGC007F] Shik and Copying String

• 题意：给出字符串 \(S\)，每次操作可以将 \(S_i\) 变为 \(S_{i-1}\) 或不变（从左向右考虑这个过程），求令 \(S=T\) 的最小操作次数。

• 数据范围：\(|S|,|T|\leqslant 10^6\)。

• 从右向左考虑 \(T_i\)，不妨称 \(T_i\) 在 \(S_0\) 中的来源为 \(fr_i\)，则 \(fr_i=\max_{j=1\sim fr_{i+1}-[T_i\neq T_{i+1}] \And [S_j=T_i]} j\)，即可以认为是把 \(T\) 中连续段合并到左端点后，\(S\) 中还未被覆盖的 \(T_i\) 中最靠左的一个。

• 这一匹配是容易的，双指针扫一遍即可。问题是：如何知道操作要做几次？毕竟多个字符的扩展可能是相互掣肘的。

• 考虑画出网格折线图，上方为 \(S_0\)，下方为 \(T\)，在 \(fr_i\) 和 \(i\) 之间连边，当然是折线，第 \(i\) 行第 \(j\) 列（行自 \(0\) 始）为操作 \(i\) 次后的 \(S_j\)。

• 故发现若从右向左考虑 \(T\)，则已有的折线构成一个“折线壳”。不妨定义拐点为 \(S_j=S_{j-1}\) 的 \(j-1\)，则可以得出如下结论：

• 每次为 \(T_i\) 加入新的变换时相当于在这个壳左下方再套一层，换言之，把所有和 \(i\) 同列或在左边的折点向左、下各平移一格，其余折点删掉，可能创建一个新的折点。

• 任意时刻的折点数目除二都为答案的一个下界。折点可以用队列+偏移维护之（当然远没有说得这么容易...），总复杂度应为 \(O(n)\)。

[AGC023F] 01 on Tree

• 题意略。较典的一类题中的一个子类？

• 首先我们知道，如果能取 \(0\)，无脑取 \(0\)。又显然自顶向下的做法不可做，有多个 \(1\) 时退化成 \(k\) 关键字排序，故考虑自底向上，先把所有 \(0\) 连给它们的非 \(0\) 父亲。

• 此时应该剩下一车 \(1+x0\)，当然根节点可能没有 \(1\)。考虑怎么进一步合并这个东西，换言之，如果我已经把这棵子树的大门叩开，我应该在其中整怎样的顺序？

• 这里有一个奇怪的假定：对于一个父亲来说，一旦解锁了某个儿子，就会一下子把它出完。没有见到证明。

• 但在此基础上，我们可以考虑邻项交换贪心。已知各个儿子方向的 \(cnt_{0/1}\)，设 \(i\) 比 \(j\) 更优也即更早出，则有 \(cnt_{i,1}\times cnt_{j,0}\leqslant cnt_{j,1}\times cnt_{i,0}\to \dfrac{cnt_{i,1}}{cnt_{i,0}}\leqslant \dfrac{cnt_{j,1}}{cnt_{j,0}}\)。

• 注意一下除零，然后用 multiset 之类维护一下即可。

P4437 [HNOI/AHOI2018] 排列

• 题意：试构造一个合法排列 \(p_{1\sim n}\)，使其权值最大。

  • 合法排列：设有 \(a_{x_1,x_2,\dots ,x_k}=v\)，则 \(p\) 中 \(v\) 的出现必须早于 \(a_x\) 的出现。这里 \(a_i\in [0,n]\)。

  • 权值：对于排列 \(p_{1\sim n}\)，其权值为 \(\sum\limits_{i=1}^n i\times w_{p_i}\)。

• 数据范围：\(n\leqslant 5\times 10^5\)，保证答案不炸 ll。

• 首先注意到 \(0\sim n\) 这些数字构成某种拓扑关系，当然我们不会填 \(0\)，或者说总是已经填过 \(0\)。可以以此拓扑排序判无解。

• 然后考虑怎么求最大权值，自然而然想到一个拓扑排序，但显然是错的。

• 参考上一题思路，想到合法时构成一个以 \(0\) 为根的树，于是考虑对连通块维护 \(wsum,sum,cnt\) 分别表示带权和（权即为在块内序号），和还有块内点数或者说数字数。容易合并，即下式：

\[\begin{cases} wsum=wsum+sum'\times cnt+wsum' \\ sum=sum+sum' \\ cnt=cnt+cnt'\end{cases} \]

• 那么一个直观的贪心是每次选出全局 \(sum\) 最小的，毕竟我们希望小的往前放嘛，等效于大的往后放，而显然倒序考虑很麻烦甚至可能不可做。

• 但显然是错的，仔细思考发现这个还是个邻项交换模型，即：

\[sum'\times cnt+sum''\times (cnt+cnt')\geqslant sum''\times cnt+sum'\times(cnt+cnt'') \]

• 于是：

\[sum''\times cnt'\geqslant sum'\times cnt'' \]

• 即：

\[\dfrac{sum''}{cnt''}\geqslant \dfrac{sum'}{cnt'} \]

• 好了，那么用 \(\dfrac{sum}{cnt}\) 当 \(pri\) 就好了，每次在全局贪出来 \(pri\) 最小的合并给父连通块，使用并查集容易维护。

• 总复杂度 \(O(n\log n)\)。

P4785 [BalticOI 2016 Day2] 交换

• 题意：

标签：偏序,cnt,sum,times,leqslant,贪心
From： https://www.cnblogs.com/weixin2024/p/17043844.html