11.13 写题

AGC006

已单独开坑。

CF1083A

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

CF1083B

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

然后可以直接把 lcplcp 给丢掉了。现在,对于 ss 的每一个 00 位置,我们如果在这里放 11 ,我们可以有 11 个贡献为 ni+1n-i+1 的串,一个贡献为 nin-i 的串,两个贡献为 ni1n-i-1 的串,四个 ni2n-i-2 的串 \dots

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

然后贪心拿前 kk 大。

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

CF1083C

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

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

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

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

复杂度 O(nlogn)O(n\log n)

CF1083E

按照 xx 排序, yy 单调递减。然后一个很一眼的 dpdp

dp[i]=max{dp[j]xjyi+xiyjai}dp[i] = \max\{dp[j] - x_jy_i + x_iy_j - a_i\}

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

CF1083F

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

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

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

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

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

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

\