2800 CF tag DS 做题记录

· · 个人记录

hb 让做 2800-3200 的 DS。

CF19D

好像对于评分再高的题，通过人数最多的那几题也会非常简单。

对于每个 x 坐标维护一个 set，同时在线段树上维护 x 坐标区间的最大 y，因为只有单点修改所以这个维护非常简单，每次询问在线段树上二分 y 足够大的最小的 x 即可，然后在 set 里查询。

https://codeforces.com/contest/19/submission/165765098

CF547E

比较容易想到的思路是先把所有串放到一起，然后再把每个串放回去跑一遍统计 一下。

复杂度瓶颈在于跳 fail 的过程，建出 fail 树然后用线段树维护当前 trie 树上的结点所对应的串在 s_{[l,r]} 出现的次数，每次线段树合并即可，查询就是简单的区间和。

https://codeforces.com/contest/547/submission/165786540

CF1039D

不知道为啥这题有 ds 的 tag。

考虑求单个 k 的答案，这个树形 dp 是简单的，令 f_u 表示 u 的子树的答案，g_u 表示在答案的前提下以 u 为链顶的最长链长度，转移时先有 f_u=\sum_{v\in son(u)}f_v ，然后考虑最大的两个 g_v，如果 g_{v1}+g_{v2}+1\ge k，则有 f_u++，否则 g_u=\max_{v\in son(u)}g_v+1。最后答案即为 f_{root}.

考虑根号分治，令 B=\sqrt n，对于 k\le B，直接每个 k 暴力跑一遍即可。对于 k\ge B，发现答案的上界为 \lfloor\frac{n}{k}\rfloor\le \frac{n}{B}。

所以考虑枚举答案，然后二分找出每个答案对应的区间即可，这部分的复杂度为 O(\frac{n\log n}{B})。

实际为了快一点卡常需要将 B 调大，当 B=\sqrt{n\log n} 时最优。

还有个卡常的就是在 dfs 序上 dp 要比直接 dfs 快上很多。

https://codeforces.com/contest/1039/submission/165847443

CF163E

这题有点板子了，毕竟是远古题。

将一开始的 k 个模式串的 ACAM 建出来。

考虑查询的时候相当于把串放上去暴力地跳，然后对于每个结点暴力跳 fail 统计有多少个模式串。

对于跳 fail 的过程，建出 fail 树后就变成了单点修改，链查询，这玩意并不好看所以可以转为子树修改，单点查询，dfs 序上 BIT 即可。

https://codeforces.com/contest/163/submission/165861488

CF204E

事实证明，SAM 只要理解了 endpos 集合和 maxlen 以及后缀树，就算建 SAM 的过程记板子也大部分题完全够用了。

一堆串首先广义 SAM，每个点用线段树维护它是否在第 i 个串里，这玩意线段树合并是简单的。

然后直接维护 sum 就可以求出一个子串在多少个串里出现过，在后缀树上递推求出 to_u 表示后缀树上最深的满足出现不少于 k 次的祖先，那么 u 的贡献就是 O(maxlen_{to_u})。

https://codeforces.com/contest/204/submission/166024790

CF280D

考虑对这个问题建立费用流模型。

从源点向每个点连一条费用为 0 流量为 1 的边，每个点向汇点连一条费用为 0 流量为 1 的边，然后每个点 i\in [l,r] ，由 i 向 i+1 连费用为 ai 流量为 1 的边，那么选这条边相当于选 ai，每次选的都是一个区间。查询时只需要在这上面增广 k 次即可。

考虑反悔贪心模拟费用流，每次增广其实就是贪心地找到当前的最大子段和，而反向边的负边权相当于区间取反。

那么问题很简单了，我们只需要重复 k 次，每次取出最大子段和并取反即可。

取反是好维护的，不难发现取反后的最大子段和就是原来的最小子段和的相反数。

https://codeforces.com/contest/280/submission/166092926

CF549F

每次要把最大值搞出来，无非就是两种做法，一个是单调栈+扫描线，一个是笛卡尔树。

考虑前一种做法，扫描线下来后发现要支持一个区间修改，区间查询某个值的出现次数，这个操作我大概只会 O(n\sqrt n)，但是块太多每个块的 10^6 数组开不下，修改块长加上分块的强大常数指不定就 T 了。

考虑后者，考虑对于一个结点 u，无非考虑 u 和两个儿子区间的贡献，以及两个儿子区间相互之间的贡献。

u 和儿子的贡献是简单的，对于两个儿子互相的贡献，枚举 size 较小的那个儿子，然后在另一个儿子那边找即可。

对于找某个值出现次数，一种想法是启发式合并直接用 map 维护，但是常数非常不优秀会 T。另一种做法是对于每个值维护一个 vector 存出现的位置，然后相当于在 vector 里找到一个区间的位置个数。

总复杂度是 O(nlog^2n)，因为 vector 上二分还带个 \log。

https://codeforces.com/contest/549/submission/166144066

CF1654F

虽说我也不知道为什么这题会带上 DS 的 tag，但是这题还是很好的。

一个很显然的性质，令 T(x,k) 表示整个串下标 xor 上 x 后的串的前 2^k 位。

则有 T(x,k)=T(x,k-1)+T(x\ xor\ 2^{k-1},k-1)，然后只用枚举 k，利用 k-1 时每个 x 的排名求出当前 x 的排名即可。

https://codeforces.com/contest/1654/submission/166235278

CF983E

这个相对典一点，不过也是好题。

首先一个比较显然的思路，令 f_{u,k} 表示 u 往上跳 2^k 条路径能到的深度最小的点，考虑怎么求 f_{u,0}，相当于找包含 u 的路径中 LCA 最小的那个，这个看似要树上差分，其实直接每条路径更新 f_{u,0} 和 f_{v,0}，然后再 dfs 一遍，令 f_{u,0} 对 \min_{v\in son(u)}{f_{v,0}} 取 \min 即可。

考虑如何求解，每次在不碰到 LCA 的前提下先一直两个点往上跳，到了最后一步，那么有可能两个点在一个路径上，也有可能两个点各自跳到 LCA，相当于查询是否存在一条路径满足一个点在 u 的子树，另一个在 v 的子树，将其抽象到 dfs 序就是两个区间 [dfn_u,dfn_u+siz_u-1] 和 [dfn_v,dfn_v+siz_v-1]，那么相当于每个路径单点加，然后矩阵查询是否有值，这个不想动脑了，直接莽主席树。

注意判 u 和 v 中有一个在 LCA 上的情况，这个是简单的，直接跳一步就好。

https://codeforces.com/contest/983/submission/166924941

CF794F

先考虑每一位维护一棵线段树，每个结点维护这一段关于某个数字有多少个贡献，修改是可以暴力搞的，因为只有 10 个数字。每次修改标记的复杂度是 O(10) 的，算上位数总的复杂度为 O(q\times 10^2 \log n)。

不知道能不能过，发现每一位其实可以直接合起来。对于原本的做法，每一位 k 要额外 \times 10^k，我们直接将每个数字 \times 10^k 的值记录到同一个线段树即可。

复杂度 O(10q\log n) 。

https://codeforces.com/contest/794/submission/166908218

CF671C

首先这里的最大公因数即 \gcd 可以直接当作公因数处理，这个是显然的，因为题目本身就要求 \max。

考虑对于某个 d，处理出它的所有倍数出现的位置 p_{1...m}。

考虑去掉一段区间后 d 仍有贡献，那么剩下的数一定可以用三种情况表示。

$2.p_{m-1},p_m$ 还存在。 $3.p_1,p_m$ 还存在。 所以我们只关心一个数的倍数的出现位置中的最左，次左，最右，次右，这个我们可以先求出一个数出现位置中的这些值，然后枚举它的倍数进行转移，这部分的复杂度为 $O(a\ln a)$。 考虑列举三种情况的充要条件。 对于第一种情况，有 $L>p_2$。 对于第二种情况，有 $R<p_{m-1}$。 对于第三种情况，有 $L>p_1,R<p_m$。 相当于对于每个值，得出了三种区间对该值取 $\max$ 的形式。 考虑扫描线式地从左往右枚举 L，对于第二种情况，开局直接对 $[1,p_{m-1}-1]$ 取 $\max$，对于第一种情况，记录 $p_2=L$ 的最大的 val，当扫到 L 的时候，将 $[L+1,n]$ 对 val 取 $\max$。对于第三种情况，对于每个 L 开个 vector，然后对 $[p_1+1,p_m-1]$ 取 $\max$ 即可。 问题转化成了若干次区间取 $\max$ 和区间求和，注意这里不是全局求和的原因是要满足最基本的 $L\le R$。然后直接莽吉司机线段树。 由于每个值只会修改 O(1) 次，所以总的复杂度为 $O(a\ln a+(n+a)\log n)$。 https://codeforces.com/contest/671/submission/166923452 ### CF1383E CF tag 永远是个谜，这明明是一个纯 dp 题。 为了方便，首先我们将两边的 0 全部去掉，最后再乘上两边的 0 的个数 +1 即可。 这个删除原则是简单的，有 0 删 0，否则任意删一个。 为了不算重复，我们令每个匹配的子序列都在原串中的匹配贪心地靠左。 那么一个想法是令 $f_i$ 表示末尾匹配到 i 的子序列个数，然后考虑在这之后添加 0/1 进行转移，那么相当于我们现在要求一个 $nxt_{i,0/1}$，然后直接从 $f_i$ 向 $f_{nxt_{i,0/1}}$ 转移即可。 对于 $nxt_{i,1}$，因为每一段 1 都至少会留一个（合并的段视作同一段），所以这个东西直接就是后面的第一个 1。 对于 $nxt_{i,0}$，若 $s_i=1$，那么显然就是第一个 0，对于 $s_{i+1}=1$。那么剩下的情况就是对于 i 是一段 0 的末尾。 发现这里容易算重的一个地方是在后面匹配的 0 可能可以放到前面匹配，这其实相当于匹配到的段如果不大于当前这一段的段长，那么这个匹配是重复的。 所以只需要找到后面的第一个比当前段长的段即可，这个可以单调栈处理，然后 $nxt_{i,0}$ 跳到 x+len，x 为匹配到的段的第一个位置，len 为当前段长。 总复杂度 O(n)。 https://codeforces.com/contest/1383/submission/167105400 ### CF633G 又是一个难度虚高的无思维难度题。 树上子树操作直接搞 dfs 序下来，那么 u 的子树区间在 dfs 序上对应 $[dfn_u,dfn_u+siz_u-1]$。 问题转变为区间操作，注意到 m 很小，而我们只关心有多少种并不关心具体数量，所以直接对线段树上每个结点开一个 bitset 即可。 区间加就相当于这个区间的 bitset 集体左移，注意还有最左边的一部分位要移到最右边。 这里口胡一下 bitset 的区间清 0 的操作，比如要将后 len 位清零就先右移 len 位再左移回来即可。 在外面预处理一个质数的 bitset，那么答案为区间的 bitset 或起来，然后再与上质数的 bitset，答案就是 1 的个数。 复杂度 $O(\frac{nm\log n}{w})$。实测跑得不慢，只用了 1.2s。 https://codeforces.com/contest/633/submission/167127754 ### CF986E 路径首先差分处理，令 $pre_u$ 表示根到 u 的路径的答案，则有 $ans=\frac{pre_upre_v\gcd(a_{lca},w)}{pre_{lca}}$。 这启发我们把询问离线下来，然后对整棵树 dfs 一遍，dfs 的过程中动态地用一个东西存储当前路径上的东西，然后处理每个点上相关的询问即可。 问题转变为一个数集合，一次询问。 考虑 $\gcd$ 本质是一个对质因数的指数取 $\min$ 的过程，所以将 w 质因数分解后，暴力枚举每个质因数和出现次数即可。 dfs 过程中加入或删除 $val_u$ 同理，插入到对应的桶即可。 复杂度是 $O((n+q)\sqrt{val}+q\log^2val)$，实际用时不慢，1.3s。 https://codeforces.com/contest/986/submission/167354331 ### CF1413F 通过这题重温并大大加深了对树上动态 dp 的理解。 ~~但是毕竟这不是动态 dp 板子题什么的所以我就不把这些理解写出来了。~~ 因为一开始没注意看题，所以这里路径的长度统一定义为**路径上点的数量**，题目问的是边，最后 -1 即可。 令 $f_{u,0/1}$ 表示 u 的子树内，一端是 u 的含有偶/奇数个 1 的路径的最长长度，$f_{u,2}$ 表示 u 的子树内的答案，令 val 表示从 v 向 u 转移时，v 的父边边权。 转移是简单的，$f_{u,2}=\max(f_{v,2},g_{u,2},g_{u,0}+f_{v,val},g_{u,1}+f_{v,val\oplus1}) f_{u,0}=\max(g_{u,0},f_{v,val}+1),f_{u,1}=\max(g_{u,1},f_{v,val\oplus1}+1)

这个写成矩阵是简单的，不过要分 val=0/1 构造两种不同的矩阵，无伤大雅，因为我比较懒这里就不放出矩阵了。

考虑修改的时候如何得到轻儿子的转移，考虑对每个点的轻儿子的 dp 值维护 multiset，需要时取出最大值和次大值即可。

树剖过不了，需要全局平衡二叉树，复杂度 O(4^3m\log n+mlog^2 n)。

4944 ms 也是够极限了。

https://codeforces.com/contest/1413/submission/167614172