【听课记录】25.11-LCA-Week6

· · 个人记录

11.05 优化 - 构造

调整法，若调整规则使方案 S 不变劣，则只有无法调整的方案可能是最优解。

对于集合 S 上的二元关系 \lt，若满足非自反性、反对称性、传递性、不可比性的传递性则称其满足严格弱序。若元素满足弱序关系，可以使用邻项交换，且最优解中任意交换两个相邻元素都不会变优。

模拟费用流（反悔贪心）。

组合模式（注意力）。

CF632C The Smallest String Concatenation

题意

给定 n 个字符串 s_i，总长为 m，任意重排后最小化新串字典序。m\le 5\times 10^4。

题解

对于一个答案排列 p，若存在相邻元素满足 s_{p_{i+1}}s_{p_{i}}\lt s_{p_i}s_{p_{i+1}}，将这两项交换一定不劣。于是最终排列任意相邻元素均满足 s_{p_{i}}s_{p_{i+1}}\le s_{p_{i+1}}s_{p_{i}}。如果可以找出一种权值 f(S) 满足弱序关系，且 f(s_{p_i})\le f(s_{p_{i+1}}) 与 s_{p_{i}}s_{p_{i+1}}\le s_{p_{i+1}}s_{p_{i}} 等价，则可以说明最优解唯一。

考虑比较 ab,ba 的 a,b 两串，通过复制若干份可得 a^{\left|b\right|},b^{\left|a\right|} 两个等长的串。由于若干 a,b 任意拼接得到的最优串一定是 a 在前 b 在后，于是 ab\le ba 可以表示为 a^{\left|b\right|}b^{\left|a\right|}\le b^{\left|a\right|}a^{\left|b\right|}。由于长度相同，这相当于比较 a^{\left|b\right|},b^{\left|a\right|}。于是令 f(S) 表示 S 无限复制得到的串，以字符串为权值即可。这样就证明了排序做是对的。

然而排序时若暴力比较，单次复杂度是 \mathcal O(\left|a\right|+\left|b\right|)，可能有 \mathcal O(nm) 的最劣复杂度，比较爆炸。考虑优化比较，令 a 为较短的串，先暴力比较 a,b 前 \left|a\right| 位，若全相同会对 b 和其后缀比较，可以用 Z 函数预处理实现 \mathcal O(1) 查询。还相同的话是一个后缀与 a 比较，可以直接暴力。于是做到了单次 \mathcal O(\min(\left|a\right|,\left|b\right|)) 的比较。

考虑使用归并排序，并分析其复杂度。总共有 \mathcal O(\log n) 层，每层放入排序结果的总串长为 m。同时排序中若产生 \mathcal O(len) 的比较复杂度，会将长度至少为 len 的串放入排序结果，于是总复杂度也是 \mathcal O(m\log n) 的。

还有线性做法，据说是 Trie 树上的奇技淫巧，不管了。

典题

题意

给定 n 个二元组 (t,w)，任意重排为 p，最小化 \sum w_{p_i}(\sum_{j\lt i}t_{p_j})。

考虑相邻的 (t_1,w_1),(t_2,w_2)，这样排序较优需要满足 t_1w_2\le t_2w_1，两边除以 w_1w_2 可得 \frac {t_1}{w_1}\le \frac {t_2}{w_2}，也即 \frac tw 从小到大排序最优。以下令 f=\frac tw。

Ex 题意

给定 k 个二元组 (t,w) 序列，要求每组内先后顺序不能改变，合并成一个序列，仍然最小化该式。

考虑同一个序列中相邻两项，若 f_i\ge f_{i+1} 则填完 i 后一定接着填 i+1，证明可以考虑最终序列中若这两项之间有元素，对其 t,w 均求和后求 f' 值。若 f_i\ge f' 则可以提到 i 之前，若 f'\ge f_{i+1} 则可以放到 i+1 之后。由于 f_i\ge f_{i+1}，两个条件至少有一个成立，于是一定能调整到 i,i+1 相邻。

之后通过这样的邻项合并可得若干 f 不降的序列，之后贪心取当前 f 最小的可取元素即可。

Ex Ex 题意

每次找非根节点中权值最小的，若其父亲被填入序列，则必然将该点立刻填入序列。于是将其与父亲合并，产生 $t_{f}w_u$ 的代价，得到一个 $(t_u+t_f,w_u+w_f)$ 的新点。此时父亲的权值变小了，可以用堆维护这个过程，复杂度 $\mathcal O(n\log n)$。 ### HDU6326 Problem H. Monster Hunter #### 题意 给定一棵树，除根节点 $1$ 外每个点上有一个怪物，需要消耗 $a_i$ 生命清除，之后可以获得 $b_i$ 生命。走到一个点前需要清除其父亲节点上的怪物，求要清除所有怪物需要的最小初始生命。多组数据，$\sum n\le 10^6,1\le a_i,b_i\le 10^9$。 #### 题解 考虑没有树的限制，可以任意排序时怎么做。对于相邻两项 $(a_i,b_i),(a_j,b_j)$，此时贡献为 $\max(a_i,a_j+a_i-b_i)$，若交换则贡献为 $\max(a_j,a_i+a_j-b_j)$，要最小化贡献。以 $\max (a_i,a_j)$ 为基准，若 $a_i-b_i,a_j-b_j$ 不同号容易比较，一定是 $a_i\le b_i$ 的排在前面，这也是容易感性理解的。 讨论同号情况，若均满足 $a\le b$，则是将 $a_i,a_j$ 之一减小后取最大值。显然只有减小初始最大值有效，于是一定会把初始最大值放在后面，即按照 $a$ 从小到大排序。若均满足 $a\gt b$，有 $a_i\lt a_{i}+a_j-b_j,a_j+a_i-b_i\gt a_h$。将原式简写成 $\max(A,B),\max(C,D)$ 后有 $A\lt D,B\gt C$，手推一下就会发现原式比较大小与 $B,D$ 比较大小是等价的。于是变为比较 $a_j+a_i-b_i,a_i+a_j-b_j$ 的大小，得到按 $b$ 从大到小排序最优。 综上，前面 $a\le b$ 部分按 $a$ 升序排序，后面 $a\gt b$ 部分按 $b$ 降序排序，容易发现这样的大小关系具有传递性等性质，也可以编出一个权值 $f(a,b)$ 并以此排序。上树之后考虑邻项合并，即找到当前非根节点中权值最优的点，将其与父亲合并。用堆和并查集维护即可，复杂度 $\mathcal O(n\log n)$。 ### CF865D Buy Low Sell High #### 题意 给出每天的价格，每天可买入一次或卖出一次，也可以什么都不做，最大化净收益。$n\le 3\times 10^5$。 #### 题解 考虑依次决策每天的行动，可以在这天买入，之后某天卖出；或者找之前价格最低的一天买入，在当天卖出。使用堆维护此前没用过的价格，若最小值比 $a_i$ 小则可以匹配。然而这样贪心是错误的，原因是最优解中可能跳过中间的元素进行匹配。 考虑支持反悔操作，对于前面选择过的 $(i,j)$ 配对，需要支持将其改成 $(i,k)$，其中 $i\lt j\lt k$。注意到此时收益会增加 $a_k-a_j$，于是对于每个 $(i,j)$ 均在堆中额外加入一个 $a_j$ 作为代价即可，当然每天仍需加入一个 $a_i$ 表示直接在这天买入。由于 $j$ 在反悔后实际上不被操作，两个均取是没有问题的。复杂度 $\mathcal O(n\log n)$。 ### QOJ9222 Price Combo ## 11.07 构造 ### CF862C Mahmoud and Ehab and the xor #### 题意 给定 $n,x$，构造 $n$ 个不超过 $10^6$ 且两两不同的非负整数使得异或和恰为 $x$。$n,x\le 10^5$。 #### 题解 只有 $n=2,x=0$ 无解，先判掉就行。 - 增量 考虑构造若干个异或和为 $0$ 的元素，比如 $1,2,3$，以及任意 $4t,4t+1,4t+2,4t+3$，之后按照对 $4$ 取模的结果分讨一下，用不超过 $4$ 个数凑出 $x$，再拼上若干个大小为 $4$ 的组即可。 - 随机 + 微调 考虑随机出 $(n-1)$ 个数，此时其异或和 $S$ 大概是均匀随机的，判断最后一个数 $S\oplus x$ 是否出现过即可。由于可选值域比 $n$ 大不少，合法概率较高，期望线性次就能取到一组解。 去随机的话，随机或直接填 $(n-2)$ 个数，之后后两个数 $i\oplus j\oplus S=x$，这会形成若干个数对。由于值域足够大，根据抽屉原理一定存在合法的数对。只需要特判一下 $x=0$ 的情况即可。 - 组合模式 这题好像没咋体现啊，不过构造题主要是这三种做法。 ### CF468B Two Sets 分析一下发现是必须在同一个集合内。 ### P3588 [POI 2015 R2] 沙漠 Desert 优化建图，差分约束。 差分约束同时最优化所有非定点的值。 子问题：分治、倍增、递归、增量、差分、迭代、微调。 ## 11.09 优化 - 匹配 点覆盖：用点集覆盖所有边。 独立集：没有公共边的点集。 两者互为补集，即任意一个点覆盖的补集一定是合法独立集，反之亦然。 Konig 定理：二分图中，最小点覆盖中的顶点数量等于最大匹配中的边数量。 二分图最大权匹配：补上 $0$ 边可转化为最大权完美匹配。 顶标：给每个点一个标号，满足边权不大于两端标号和。 这样匹配权值一定不超过标号总和，于是找到一组标号和一个匹配权值相等，即为最大匹配权值和。 需要相等边组成的子图存在完美匹配，仍然考虑增广过程。