专栏文章

【听课记录】25.11-LCA-Week6

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min9vga2
此快照首次捕获于
2025/12/01 22:56
3 个月前
此快照最后确认于
2025/12/01 22:56
3 个月前
查看原文

11.05 优化 - 构造

  • 贪心
调整法，若调整规则使方案 SS 不变劣，则只有无法调整的方案可能是最优解。
对于集合 SS 上的二元关系 <\lt，若满足非自反性、反对称性、传递性、不可比性的传递性则称其满足严格弱序。若元素满足弱序关系，可以使用邻项交换，且最优解中任意交换两个相邻元素都不会变优。
模拟费用流（反悔贪心）。
  • 构造（Ad-Hoc）
组合模式（注意力）。

CF632C The Smallest String Concatenation

题意

给定 nn 个字符串 sis_i，总长为 mm，任意重排后最小化新串字典序。m≤5×104m\le 5\times 10^4。

题解

对于一个答案排列 pp，若存在相邻元素满足 spi+1spi<spispi+1s_{p_{i+1}}s_{p_{i}}\lt s_{p_i}s_{p_{i+1}}，将这两项交换一定不劣。于是最终排列任意相邻元素均满足 spispi+1≤spi+1spis_{p_{i}}s_{p_{i+1}}\le s_{p_{i+1}}s_{p_{i}}。如果可以找出一种权值 f(S)f(S) 满足弱序关系，且 f(spi)≤f(spi+1)f(s_{p_i})\le f(s_{p_{i+1}}) 与 spispi+1≤spi+1spis_{p_{i}}s_{p_{i+1}}\le s_{p_{i+1}}s_{p_{i}} 等价，则可以说明最优解唯一。
考虑比较 ab,baab,ba 的 a,ba,b 两串，通过复制若干份可得 a∣b∣,b∣a∣a^{\left|b\right|},b^{\left|a\right|} 两个等长的串。由于若干 a,ba,b 任意拼接得到的最优串一定是 aa 在前 bb 在后，于是 ab≤baab\le ba 可以表示为 a∣b∣b∣a∣≤b∣a∣a∣b∣a^{\left|b\right|}b^{\left|a\right|}\le b^{\left|a\right|}a^{\left|b\right|}。由于长度相同，这相当于比较 a∣b∣,b∣a∣a^{\left|b\right|},b^{\left|a\right|}。于是令 f(S)f(S) 表示 SS 无限复制得到的串，以字符串为权值即可。这样就证明了排序做是对的。
然而排序时若暴力比较，单次复杂度是 O(∣a∣+∣b∣)\mathcal O(\left|a\right|+\left|b\right|)，可能有 O(nm)\mathcal O(nm) 的最劣复杂度，比较爆炸。考虑优化比较，令 aa 为较短的串，先暴力比较 a,ba,b 前 ∣a∣\left|a\right| 位，若全相同会对 bb 和其后缀比较，可以用 Z 函数预处理实现 O(1)\mathcal O(1) 查询。还相同的话是一个后缀与 aa 比较，可以直接暴力。于是做到了单次 O(min⁡(∣a∣,∣b∣))\mathcal O(\min(\left|a\right|,\left|b\right|)) 的比较。
考虑使用归并排序，并分析其复杂度。总共有 O(log⁡n)\mathcal O(\log n) 层，每层放入排序结果的总串长为 mm。同时排序中若产生 O(len)\mathcal O(len) 的比较复杂度，会将长度至少为 lenlen 的串放入排序结果，于是总复杂度也是 O(mlog⁡n)\mathcal O(m\log n) 的。
还有线性做法，据说是 Trie 树上的奇技淫巧，不管了。

典题

题意

给定 nn 个二元组 (t,w)(t,w)，任意重排为 pp，最小化 ∑wpi(∑j<itpj)\sum w_{p_i}(\sum_{j\lt i}t_{p_j})。
考虑相邻的 (t1,w1),(t2,w2)(t_1,w_1),(t_2,w_2)，这样排序较优需要满足 t1w2≤t2w1t_1w_2\le t_2w_1，两边除以 w1w2w_1w_2 可得 t1w1≤t2w2\frac {t_1}{w_1}\le \frac {t_2}{w_2}，也即 tw\frac tw 从小到大排序最优。以下令 f=twf=\frac tw。

Ex 题意

给定 kk 个二元组 (t,w)(t,w) 序列，要求每组内先后顺序不能改变，合并成一个序列，仍然最小化该式。
考虑同一个序列中相邻两项，若 fi≥fi+1f_i\ge f_{i+1} 则填完 ii 后一定接着填 i+1i+1，证明可以考虑最终序列中若这两项之间有元素，对其 t,wt,w 均求和后求 f′f' 值。若 fi≥f′f_i\ge f' 则可以提到 ii 之前，若 f′≥fi+1f'\ge f_{i+1} 则可以放到 i+1i+1 之后。由于 fi≥fi+1f_i\ge f_{i+1}，两个条件至少有一个成立，于是一定能调整到 i,i+1i,i+1 相邻。
之后通过这样的邻项合并可得若干 ff 不降的序列，之后贪心取当前 ff 最小的可取元素即可。

Ex Ex 题意

nn 个点的树，每个点有一个二元组 (t,w)(t,w)，序列中要求父亲在儿子前面，仍然最小化该式。UVA1205 和 ABC376G 大概是 t=1t=1 的版本。
每次找非根节点中权值最小的，若其父亲被填入序列，则必然将该点立刻填入序列。于是将其与父亲合并，产生 tfwut_{f}w_u 的代价，得到一个 (tu+tf,wu+wf)(t_u+t_f,w_u+w_f) 的新点。此时父亲的权值变小了，可以用堆维护这个过程，复杂度 O(nlog⁡n)\mathcal O(n\log n)。

HDU6326 Problem H. Monster Hunter

题意

给定一棵树，除根节点 11 外每个点上有一个怪物，需要消耗 aia_i 生命清除，之后可以获得 bib_i 生命。走到一个点前需要清除其父亲节点上的怪物，求要清除所有怪物需要的最小初始生命。多组数据，∑n≤106,1≤ai,bi≤109\sum n\le 10^6,1\le a_i,b_i\le 10^9。

题解

考虑没有树的限制，可以任意排序时怎么做。对于相邻两项 (ai,bi),(aj,bj)(a_i,b_i),(a_j,b_j)，此时贡献为 max⁡(ai,aj+ai−bi)\max(a_i,a_j+a_i-b_i)，若交换则贡献为 max⁡(aj,ai+aj−bj)\max(a_j,a_i+a_j-b_j)，要最小化贡献。以 max⁡(ai,aj)\max (a_i,a_j) 为基准，若 ai−bi,aj−bja_i-b_i,a_j-b_j 不同号容易比较，一定是 ai≤bia_i\le b_i 的排在前面，这也是容易感性理解的。
讨论同号情况，若均满足 a≤ba\le b，则是将 ai,aja_i,a_j 之一减小后取最大值。显然只有减小初始最大值有效，于是一定会把初始最大值放在后面，即按照 aa 从小到大排序。若均满足 a>ba\gt b，有 ai<ai+aj−bj,aj+ai−bi>aha_i\lt a_{i}+a_j-b_j,a_j+a_i-b_i\gt a_h。将原式简写成 max⁡(A,B),max⁡(C,D)\max(A,B),\max(C,D) 后有 A<D,B>CA\lt D,B\gt C，手推一下就会发现原式比较大小与 B,DB,D 比较大小是等价的。于是变为比较 aj+ai−bi,ai+aj−bja_j+a_i-b_i,a_i+a_j-b_j 的大小，得到按 bb 从大到小排序最优。
综上，前面 a≤ba\le b 部分按 aa 升序排序，后面 a>ba\gt b 部分按 bb 降序排序，容易发现这样的大小关系具有传递性等性质，也可以编出一个权值 f(a,b)f(a,b) 并以此排序。上树之后考虑邻项合并，即找到当前非根节点中权值最优的点，将其与父亲合并。用堆和并查集维护即可，复杂度 O(nlog⁡n)\mathcal O(n\log n)。

CF865D Buy Low Sell High

题意

给出每天的价格，每天可买入一次或卖出一次，也可以什么都不做，最大化净收益。n≤3×105n\le 3\times 10^5。

题解

考虑依次决策每天的行动，可以在这天买入，之后某天卖出；或者找之前价格最低的一天买入，在当天卖出。使用堆维护此前没用过的价格，若最小值比 aia_i 小则可以匹配。然而这样贪心是错误的，原因是最优解中可能跳过中间的元素进行匹配。
考虑支持反悔操作，对于前面选择过的 (i,j)(i,j) 配对，需要支持将其改成 (i,k)(i,k)，其中 i<j<ki\lt j\lt k。注意到此时收益会增加 ak−aja_k-a_j，于是对于每个 (i,j)(i,j) 均在堆中额外加入一个 aja_j 作为代价即可，当然每天仍需加入一个 aia_i 表示直接在这天买入。由于 jj 在反悔后实际上不被操作，两个均取是没有问题的。复杂度 O(nlog⁡n)\mathcal O(n\log n)。

QOJ9222 Price Combo

11.07 构造

CF862C Mahmoud and Ehab and the xor

题意

给定 n,xn,x，构造 nn 个不超过 10610^6 且两两不同的非负整数使得异或和恰为 xx。n,x≤105n,x\le 10^5。

题解

只有 n=2,x=0n=2,x=0 无解，先判掉就行。
  • 增量
考虑构造若干个异或和为 00 的元素，比如 1,2,31,2,3，以及任意 4t,4t+1,4t+2,4t+34t,4t+1,4t+2,4t+3，之后按照对 44 取模的结果分讨一下，用不超过 44 个数凑出 xx，再拼上若干个大小为 44 的组即可。
  • 随机 + 微调
考虑随机出 (n−1)(n-1) 个数，此时其异或和 SS 大概是均匀随机的，判断最后一个数 S⊕xS\oplus x 是否出现过即可。由于可选值域比 nn 大不少，合法概率较高，期望线性次就能取到一组解。
去随机的话，随机或直接填 (n−2)(n-2) 个数，之后后两个数 i⊕j⊕S=xi\oplus j\oplus S=x，这会形成若干个数对。由于值域足够大，根据抽屉原理一定存在合法的数对。只需要特判一下 x=0x=0 的情况即可。
  • 组合模式
这题好像没咋体现啊，不过构造题主要是这三种做法。

CF468B Two Sets

分析一下发现是必须在同一个集合内。

P3588 [POI 2015 R2] 沙漠 Desert

优化建图，差分约束。
差分约束同时最优化所有非定点的值。
子问题：分治、倍增、递归、增量、差分、迭代、微调。

11.09 优化

  • 匹配
点覆盖：用点集覆盖所有边。
独立集：没有公共边的点集。
两者互为补集，即任意一个点覆盖的补集一定是合法独立集，反之亦然。
Konig 定理：二分图中，最小点覆盖中的顶点数量等于最大匹配中的边数量。
二分图最大权匹配：补上 00 边可转化为最大权完美匹配。
顶标：给每个点一个标号，满足边权不大于两端标号和。
这样匹配权值一定不超过标号总和，于是找到一组标号和一个匹配权值相等，即为最大匹配权值和。
需要相等边组成的子图存在完美匹配，仍然考虑增广过程。

评论

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

正在加载评论...