「杂题乱写」ABC 293 ~ ABC 295

2023-05-28 15:08 由 K8He 发表于 #其他

「杂题乱写」ABC 293 ~ ABC 295

点击查看目录

目录
「杂题乱写」ABC 293 ~ ABC 295
ABC 293
D | Tying Rope
E | Geometric Progression
F | Zero or One
G | Triple Index
Ex | Optimal Path Decomposition
ABC 294
D | Bank
E | 2xN Grid
F | Sugar Water 2
G | Distance Queries on a Tree
ABC 295
D | Three Days Ago
E | Kth Number
F | substr = S
G | Minimum Reachable City

这个 ABC 系列大概会持续下去，每三场写一份。

每三场写一份的一个重要原因是标签上限十个。

因为是 ABC 所以不做 A 题 B 题和 C 题。

ABC 293

身败名裂.jpg

F | Zero or One

考虑直接枚举 \(b\) 判断是否合法，但是复杂度 \(O(n\log_bn)\)。

考虑枚举一个二进制数然后二分出对应的 \(b\)，但是复杂度 \(O(2^{\max(\log_bn)}\times\log_2n\times\log_2n)=O(n\log_2^2n)\)。

那么考虑缝合起来，设一个 \(k\)，枚举 \(1\sim k\) 的 \(b\)，然后 \(b\) 大于 \(k\) 时将 \(n\) 化为 \(b\) 进制数后位数比较小，可以直接枚举 \(\log_k\) 位的所有二进制数。

总复杂度 \(O(k+2^{\log_kn}\log_2^2n)\)，设 \(k=10^4\) 可过。

Ex | Optimal Path Decomposition

这个题一看就挺二分答案的。

设 \(f_{i, j}\) 表示以 \(i\) 为根的子树中，\(i\) 有不超过 \(j\) 个儿子与自己颜色相同时，从 \(i\) 出发的一条路径上的与自己颜色不同的颜色数量最大值。显然 \(0\le j\le2\)。（直接表示颜色数量最大值，不排除自己应该也行，但转移好像不太方便。）

然后二分查找 \(k\)，每次用 \(O(n)\) 的时间算一下 \(f\) 数组，总复杂度 \(O(n\log_2n)\)。

如何转移？设当前枚举到了 \(u\) 的叶子结点 \(v\)，那么当且仅当 \(f_{u,j_1} + f_{v, j_2} + [j_2 = 2] \le k\) 时可以转移。如果 \(f_{v, j_2}\) 完全没机会转移上去说明这棵子树已经不满足条件了，直接令 \(f_{u,0} = f_{u,1} = f_{u,2} = +\infty\)，转移到根上后即可毙掉这种情况。

确实有点抽象，但是代码很短很好写。

\(%傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法傻逼，这个是官方题解做法\)

ABC 294

D | Bank

考虑开个 \(vis\) 数组记录 \(1\sim n\) 中那些数在 \(b\) 数组中，然后随便操作了。

E | 2xN Grid

在两个数组中各开一个指针，移动过程中保证两个指针指向的区间有交，值相等时计算相交长度。

F | Sugar Water 2

连二分都不会了。

我们二分一个浓度 \(x\)，计算浓度小于等于 \(x\) 的混合糖水数量。

化简两杯糖水混起来后浓度小于等于 \(x\) 的不等式：

\[\begin{aligned} \frac{a_i + c_j}{a_i + b_i + c_j + d_j} &\le x\\ a_i + c_j &\le x(a_i + b_i + c_j + d_j)\\ a_i + c_j &\le a_ix + b_ix + c_jx + d_jx\\ (1 - x)a_i - b_ix &\le (x - 1)c_j + d_jx\\ \end{aligned} \]

那么设 \(v1_i = (1 - x)a_i - b_ix, v2_i = (x - 1)c_j + d_jx\)，排序后可以快速二分查找到与第 \(i\) 杯糖水混合后浓度小于 \(x\) 的糖水数量了。

G | Distance Queries on a Tree

树剖板子题。

ABC 295

D | Three Days Ago

不难发现一个子段满足条件必须要求这个子段内的每个数字出现次数为偶数。

状压一下 \(1\sim i\) 每个数字出现次数的奇偶性存进 \(f_i\)，当且仅当 \(f_i=f_j\) 时字段 \([i + 1, j]\) 满足条件。

E | Kth Number

经典结论：

\[E(A_k) = \sum_{i = 1}^{m} i\times P(A_k = i) = \sum_{i = 1}^{m} P(A_k \ge i) \]

枚举到 \(i\) 时，为了满足 \(i\) 至少是第 \(k\) 大，前面至少要有 \(n - k + 1\) 个数垫着。但是还有一些数本来就小于 \(i\)，那么设 \(l\) 为 \(n - k + 1\) 减去原数组中小于 \(i\) 的数的个数（也就是需要的 \(0\) 的个数），\(r\) 为原数组中 \(0\) 的个数，则：

\[P(A_k\ge i) = \sum_{j = l}^{r}\dbinom{r}{j}(\frac{m - i + 1}{m})^{j}(\frac{i - 1}{m})^{r - j} = \frac{1}{m ^ r}\sum_{j = l}^{r}\dbinom{r}{j}({m - i + 1})^{j}({i - 1})^{r - j} \]

有些细节。

F | substr = S

数位 DP 板子！但是允许重叠，所以加一个 KMP。

G | Minimum Reachable City

有意思。

观察到数据范围 \(1\leq p_i \leq i\)，所以说父亲都指向儿子，且任意一个点的儿子编号都比自己大。

「保证最开始时 \(v\) 能到达 \(u\)」，所以 \((u, v)\) 一定是一条返祖边，在树上构成一个强连通分量，这里可以把一个强连通分量放在一个并查集里面。操作 \(1\) 直接把 \(v\rightarrow u\) 路径上经过的点全部合并到一个并查集里面，操作二直接找 \(x\) 所在并查集的根。