AT_abc364 补题报告【G】

zhangjinxuan

前言

我感觉我写这些内容对自己有很大益处，尤其是考试补题，因为补题不仅仅是一个“能多几个 AC”的作用，还是一个吸取教训、总结、提升自己的一个重要途径。从某种意义上来说这是写给自己的。

每一场（方便公开）的比赛如果改完题目（达到能力上限）就会来总结。由于 lz 水平有限，所以一些帖子的学术性问题欢迎在本贴讨论指出错误。

---

ABC 的比赛就从 C 开始补起吧，比赛题目：https://atcoder.jp/contests/abc364/tasks

万不得已都是不会做 AB 的，但这次做了（望轻喷。

问题 C

$n$ 个物品有两个状态 $a_i b_i$，选出最少的物品使得 $a_i$ 总和大于 $x$ 或者 $b_i$ 总和大于 $y$

其实非常的诈骗，因为发现他要求的是最小的一个数量，那么显然的一个想法就是让某一个维度直接挤满，于是就先对 $a_i$ 从大到小排序，判断最小的，再对 $b_i$ 从大到小排序，判断最小的。

贪心显然可证。

场切：https://atcoder.jp/contests/abc364/submissions/56021163

问题 D

$n$ 个数字 $a_i$，然后每次询问 $b_i, k_i$ 表示 $n$ 个数字与 $b_i$ 的差的绝对值的第 $k$ 小值（也就是输出距离）。

首先可以把所有的 $a_i$ 丢进一个数据结构（set，值域线段树均可，能查值域区间总数即可），然后就可以二分了（距离），二分之后在数据结构中查询 $[b_i - mid, b_i + mid]$ 的点数量，和 $k$ 做比较很快就可以缩小范围。

场切使用的是线段树：https://atcoder.jp/contests/abc364/submissions/56016374

问题 E

$n$ 个物品有两个状态 $a_i, b_i$，选出最多的物品使得 $a_i$ 总和大于 $x$ 或者 $b_i$ 总和大于 $y$

没有场切，鉴定为听歌导致的。

首先容易发现这个与普通背包不一样的东西除了是二维，还有一个东西是大于的时候才停止放置。

让我们尝试分开思考这个问题，这对我们思考任意一个问题都有帮助。

只考虑二维的问题，并且把条件改成 $a_i$ 总和小于 $x$ 并且 $b_i$ 总和 小于 $y$

正常的就是 $dp_{i,j,k}$ 表示后（前） $i$ 个物品，第一维容积剩余 $j$，第二维容积剩余 $k$ 取得的答案，发现这个答案只有 $O(n)$ 级别，于是考虑把状态与答案互换。

新的状态就是 $dp_{i,j,k}$ 表示后（前） $i$ 个物品，取了 $j$ 个物品，第一维容积剩余 $k$，第二维容积最小的答案是什么。

如果我们知道了这个有什么用？直接枚举答案和第一维容积即可，如果我们发现这个值是小于 $y$ 的，这就是一个方案。

然后如果把条件换回来之后会怎样？因为 dp 一定取得的是最优秀的策略，所以我们再选择一个元素就会立即违反这个条件，注意在没有选择之前是不会违反这个条件的

然而违反这个条件的代价就是答案多了一个，这显然是一个我们期望的结果，于是直接对于枚举的选择个数 +1 并且对于答案更新即可。

需要注意的是不能选出 $n+1$ 个物品出来。

赛后：https://atcoder.jp/contests/abc364/submissions/56063350

问题 F

有 $q$ 组边，第 $i$ 组边形如第 $i+n$ 个点向 $[l_i, r_i]$（$1\le l_i \le r_i \le n$）所有的点连了一条边，边权为 $c_i$，判断连通性并输出最小生成树的权。

考虑使用 kruskal 的最小生成树思想，就可以直接对这 $q$ 组边按照 $c_i$ 的大小关系排序。

排序之后，kruskal 的思想就是要维护一个并查集。

怎么在这上面维护一个并查集呢？先让我们假设我们有一个已经维护好的并查集，在得到 $[l_i, r_i]$ 之后，我们需要求解的就是需要保留多少的边。

那么显然，我们需要把这第 $i+n$ 的点作为一个过渡，要把 $[l_i, r_i]$ 的所有不同根的并查集向这个过渡点连边，这样就是一定保证连通的了。

而快速判断不同的并查集数量可以这么维护，用 $pr_i, pl_i$ 表示第 $i$ 个并查集在这个 $1\sim n$ 的序列上组成了一个 $[pl_i, pr_i]$ 的连通块，这个可以证明，不管任意时候，任意的并查集在序列上都是一个连通的块。

因为我们的合并就是把所有的点的连通块维护，所以一个并查集他总是一个左右互相合并的过程。

容易发现，只要能够顺利维护 $pr_i, pl_i$，所有的事情都可以做。

显然只有在连边的时候会影响，如果是 $[l, r]$，我们肯定就会想办法找到 $l$ 所在并查集的右端点范围的右边的那一个并查集，很简单，就是 $pr_l+1$。如果这个是没有超出范围的，就尝试将 $pr_l+1$ 所在的并查集与 $i$ 所在的并查集合并即可。就会发现此时的操作区间已经缩小到了 $[pr_l+1, r]$。

就重复执行这种过程即可。

证明时间复杂度？我的想法就是因为这种情况一个位置 $i$ 至多会被合并 $\log n$ 次，也就是并查集的时间复杂度，所以时间复杂度是肯定有保障的。

如果你发现此处证明不严谨或者错误，欢迎回复指正。

问题 G

听说是一个模板题，洛谷 P6192 【模板】最小斯坦纳树，但是感觉特别小众，就不改了，之后学了干脆写一个学习笔记，大家随时都可以在这里催。

总结教训

多看题，挑最可做的做，然后一定要读完题目，搞懂样例的意思。

对于一道有点不好做的题目尝试拆成多个子问题（或削弱版）再尝试组合。

dp 的化如果发现答案级别很小可以考虑和状态调换。

简柠啦