11.13 写题

AGC006

已单独开坑。

CF1083A

显然,点权减边权最大的路径上不可能存在让油量变成 $0$ 的一段。所以找点权减边权最大的路径,这个可以直接 $dp$。

CF1083B

首先,我们把 $s,t$ 都直接拿一遍肯定是前两步的最优操作。相当于除了 $s,t$ 的 $lcp$ 其他部分都拿了两遍。

然后可以直接把 $lcp$ 给丢掉了。现在,对于 $s$ 的每一个 $0$ 位置,我们如果在这里放 $1$ ,我们可以有 $1$ 个贡献为 $n-i+1$ 的串,一个贡献为 $n-i$ 的串,两个贡献为 $n-i-1$ 的串,四个 $n-i-2$ 的串 $\dots$

把这个贡献放到一个差分数组上,这个数字表示一个给下个位置这个位置两倍的差分即可。

然后贪心拿前 $k$ 大。

具体参考代码把。。反正就这么整了下就过掉了。。

CF1083C

离谱。打 vp 的时候想了想不太会看到场上都在写 E 就去整 E 没管了。。然后 C 2800 , D 3500 , E 2400 , F 3300…,而且这四个东西还标签还都是 data structure 。。

这个题思路还算简单,考虑在值域上开一个线段树,维护如果想要同时包含区间内的值的最小路径,或维护不存在这样的路径。这个东西的合并就是一个路径求并的过程,而且如果合并后不是路径直接判掉即可。查询就是线段树上二分,修改就直接单点改。

如果像我一样信仰一波直接倍增 LCA 然后就 T 飞了。。。倍增求 LCA 的话这东西复杂度 $O(n\log^2 n)$ ,试了试由于 pushup 常数不小跑不过去。

然后改成 ST 表就过了。复习一下,ST 表求 LCA 的方法是记一个进入一个点记录一次的欧拉序,回溯到这个点也算数,然后找 $u,v$ 在序列中第一次出现的位置之间的最浅点即可。

复杂度 $O(n\log n)$。

CF1083E

按照 $x$ 排序, $y$ 单调递减。然后一个很一眼的 $dp$ :

显然斜优, $y$ 单减求最大,用单调队列维护一个上凸壳即可。

CF1083F

考虑 $c_i = a_i\oplus b_i$ ,然后现在就是在 $c_i$ 上进行区间异或,求把 $c_i$ 变成 $0$ 的最小代价。这种东西看着就得转差分,设 $d_1 = c_1 , d_i = c_i \oplus c_{i-1} (i \ge 2)$ ,然后 $d$ 数组的前缀和就是之前的 $c_i$ 。于是区间异或就变成了 $d_i \oplus x , d_{i+k} \oplus x$ 。可以想到我们按照模 $k$ 分类,然后就变成了相邻同时异或。

然后考虑,每次操作是作用于相邻两个,同时异或的值就是前缀的异或和。如果一个位置在上一个位置操作后变成了 $0$ 就没有必要再进行操作了,所以可以节省步骤必然是一段前缀异或为 $0$ 的位置。同时,如果全部异或起来不是 $0$ 那么一定没法构造出方案。

然后现在修改就是在差分数组上进行单点修改,也就是进行某个组内的后缀修改。

后缀修改,查询 $0$ 的位置,我们考虑分块,然后块内整体修改打标记非整体重构即可。

注意块的大小。空间复杂度是 $O(k \frac{n}{kB} \times 2^{14})$ ,得把 $B$ 调整到 $\sqrt n$ 级别。

其次,得判一下 $k > \sqrt n$ 的情况,这种情况我们直接暴力,如果分块每个组都开个块可以卡成 $n \times 2^{14}$。

文章作者: yijan
文章链接: https://yijan.co/2020/11/18/1113-xie-ti/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog