Petrozavodsk Summer 2019. Day 5 选做

· · 个人记录

https://qoj.ac/contest/1510

B. qoj8085（最小割，dp，状态设计）

最大流转最小割，等价于删除最小个数的点使得第 i 列与第 j 列不连通。

固定其中一者 i，扫描线 j，记录当前可达点集 S，dp 状态为 f_{S,j}。每次转移结束后下传删第 j+1 层点的贡献，得到一个对于单个 i 复杂度 \mathcal O(n2^kk) 的做法。拓展到求所有 (i,j) 的和，依然扫描线 j。类似于扫描线加入左端点的手法，对于一个 f 记录所有点的信息，而 f_S 值域很小，这样状态就是 f_{S,j,v} 表示扫到 j 有多少个 i 的 dp_{S,j}=v。时间复杂度 \mathcal O(n2^kk^2)。

*C. qoj8086（交互，网格图分治）

从任意一个点向更大的走过去一直走可以走到最大值，但是路径长度是 n^2 级别的。用一个类似于二分的手法来定位，也就是网格图分治。取一个靠中间的分界列。

第一次递归时，把这一列都问一遍，求出这一列的最大值 v 以及它左右侧三个位置的最大值 l,r。如果 v>\max(l,r) 那么 v 就是 global max；若 l<v<r，那么最大值在右侧，否则右侧的路径无法来到左边，l>v>r 同理。不会出现 l>v<r。

后续递归时就存在边界值了，在上述的基础上考虑询问过的最大值在哪一侧即可。不然不可能走到另一侧。询问次数不超过 3n+12\log n。

E. qoj8088（容斥，数据随机）

固定排列集求方案数，考虑容斥。钦定一个颜色集合，要求其出现位置两两偏序，这样分成的若干层内部是一个多重集组合数相乘。长度较小时直接考虑这张偏序关系图，长度较大时这个图的边数很少，并且边权是固定的所以容易做到与边数同阶的递推。总边数期望是 \sum_{l}2^{-l}n^2(k-l+1)=\mathcal O(n^2k)，时间复杂度 \mathcal O(nk^2+n^2k)。

H. qoj8091（最短路，图论，dp，dijkstra）

设计 dp 状态 f_u 表示 u\to n 的最优期望时间。边之间成功率最开始都是 \frac{3}{4}，考虑对于后继按照 f 进行排序。第一条边成功率是 \frac{3}{4}，剩下 \frac{1}{4} 的概率变成 \frac{1}{2}。继续做，发现策略形如尝试一个前缀之后再一直尝试一个单点。

问题是这样需要求出 \{f\}，初始只有 f_n=0 已知。显然与 n 相邻的点的 f 都可以求，进一步地，考虑 dijkstra 算法，每次取出 \min f，然后对邻边进行松弛。其前缀序列就是自动有序的，相当于枚举了在哪里结束一直试这个单点。维护当前情况的代价，时间复杂度 \mathcal O(n\log n)。

I. qoj8092（点分树，树上圆理论）

枚举不使用哪个点，求出剩余点的邻域交集大小。求和后减去 k-1 倍全体邻域交集大小就是答案。考虑树上邻域取交的结果怎么刻画，发现就是某条边或者某个点的邻域（树上圆理论）。对于每条边中间插入一个虚点，这样就全在点上了。合并即取出树上路径讨论中点即可。前后缀处理信息，这样就不用撤销了。预处理 \text{lca} 可以做到 \mathcal O(1) 合并。最终要求某个点的邻域大小，可以直接上点分树求一下。时间复杂度 \mathcal O((n+\sum k)\log n)。

K. qoj8094（kmp，border 理论）

动态支持 fail 树上挂叶子，以及查询某个点的子树大小。离线的话造一个重链剖分是容易的，在线可以直接平衡树维护括号序，或者直接套用 border 的性质：一个串的 border 可以划分为 \log n 段等差数列，就实现了重剖的功能。每条链维护支持最后插入的 BIT。时间复杂度 \mathcal O(n\log^2n)。