2024.9 做题记录

9.1

arc108e

当已经选了 \(a_l,a_r\) 时，\((l,r)\) 与外面无关。区间 dp，\(dp_{l,r}=\frac{\sum_{k=l,a_l<a_k<a_r}^r dp_{l,k}+dp_{k,r}}{num_{l,r}}+1\)。维护 \(num_{l,r},\sum dp_{l,k},\sum dp_{k,r}\) 转移。

9.2

P5188

模拟赛 T2。

容斥强行不选 \(s\) 这些材料，矩阵快速幂。

CF1949H

模拟赛 T3。

按对角线向后推，计算经过次数。不能经过 \(3\) 次。经过次数形如 \(0,\dotsb,0,1,2,\dotsb,2,1,0,\dotsb,0\) 或 \(0,\dotsb,0,2,2,0,\dotsb,0\)。维护两个 \(1\) 的位置 \(l,r\) 或是不是状态 2。如果 \(0,\dotsb,0,1,2,1,0,\dotsb,0\) 的 \(2\) 被禁止，去到状态 2，否则如果有 \(2\) 的位置被禁止则无解。如果 \(l,r\) 有被禁止，每次 \(2\) 的区间 \((l,r)\) 会增加 \(1\)，否则 \((l,r)\) 会缩短 \(1\)，\(2\times n\) 个对角线后结束。

P10998

按 \(d_u<d_v<d_w\) 排序，对于每个 \(u\) 对 \((v,w)\) 进行三元组计数。

\(m\) 条边的三元组计数 \(O(m^{1.5})\)。如果 \(d_u\le m^{\frac{2}{3}}\)，有 \(\sum d_u=m\)，复杂度 \(O(m^{\frac{1}{3}}(m^{\frac{2}{3}})^{1.5})=O(m^{\frac{4}{3}})\)。否则 \(u,v,w\) 至多 \(m^{\frac{1}{3}}\) 个，复杂度 \(O(m^{\frac{1}{3}}((m^{\frac{1}{3}})^2)^{1.5})=O(m^{\frac{4}{3}})\)。

P4843

有源汇上下界最小流，建超级源汇点补齐流量，跑最大流，从汇点向源点连容量 \(+\infty\)，再跑最大流。答案为汇点到源点的流量。

P4043

最小费用可行流，建超级源汇点补齐流量，费用加上下界流量乘代价，从汇点向源点连容量 \(+\infty\) 代价 \(0\) 的边。费用加上超级源汇点的最小费用最大流。

CF1288F

将边 \((u,v)\) 拆为 \((u,v,1,r)\) 和 \((v,u,1,b)\)，分别表示红边或蓝边，都不流就不染色。左边的红点的右边的蓝点流出大于流入，连 \((s,i,1,+\infty,0)\)，反之连 \((i,t,1,+\infty,0)\)。最小费用可行流。如果超级源点出边满流则合法。

9.3

P9338

要求前缀和时刻大于零。设 \(c_i\) 为第 \(i\) 个 A 前有多少个 B，\(w(l,r)=\sum_{i=l}^r max(c_i-l+1,0)\)，外层 wqs 二分。拆开 max，预处理 \(*p_i\) 为最小的位置使得 \(c_{p_i}−i>0\)，内层 \(dp_i=\min dp_j+sum_j-sum_{p_j-1}-j\times(i-p_j+1)\)，斜率优化。

CF2006E

等价于度数 \(\le 2\) 的点到其余点的距离最大值。动态维护直径，每次中心偏移 \(1\)，dfn 序上子树加，全局 min。度数 \(=3\) 就不贡献，度数 \(>3\) 无解。

Q9123

升序排序，二分答案 \(x\)。对于每个 \(i\) 可以 \(O(n)\) 计算 \((i,j,k)\) 的答案。设阈值 \(B\)，前 \(B\) 个的贡献 \(O(nB)\) 计算。如果没超过 \(k\)，\(B\) 的 \((B,j,k)\) 贡献 \(\le \frac{k}{B}\)。后边只需要前 \(\frac{k}{B}\) 小的 \((j,k)\) 对，\(O(\frac{k}{B}\log n)\) 预处理加 \(O(n+\frac{k}{B})\) 计算。\(B\) 取 \(\sqrt{\frac{k}{B}}\)。

Q5095

模拟赛 T3。

最优策略决策为从下往上每个人删掉存在的最劣的数。\(O(n^3)\) 模拟，开始点下移时每个人的决策点单调，复杂度 \(O(n^2)\)。