ZigZagK的博客
[离线+后缀自动机+LCT]2022牛客暑期多校训练营(加赛)C【Cmostp】题解
题目概述Cmostp解题报告建出SAM,考虑离线,每次添加一个前缀节点 $p_i$ 的时候,就是把 $p_i$ 到 $fail$ 树根路径上的节点的最右终止端点改为 $i$ 。查询 $[L,R]...
[离线+可持久化树+线段树分治+并查集按秩合并+哈希]2022牛客暑期多校训练营8 I【Equivalence in Connectivity】题解
题目概述Equivalence in Connectivity解题报告好像确实有维护动态图的方法……但是可能是考场上写不出的那种……考虑离线,建出可持久化树,如果用并查集维护图的连通性,会发现不...
[后缀数组+复杂度分析]2022牛客暑期多校训练营7 I【Suffix Sort】题解
题目概述Suffix Sort解题报告一直在想Hash,然后寄了……实际上应该分析一下性质。首先有一个比较显然的想法是将 $S$ 变为另一个数组,$a_i$ 表示 $S_i$ 与上一个相同字符的...
[KMP+后缀数组+主席树]2022牛客暑期多校训练营6 L【Striking String Problem】题解
题目概述Striking String Problem解题报告神仙题,根本想不到。记 $n$ 为 $S$ 长度,$m$ 为 $T$ 长度,$U_i$ 表示 $S[l_1,r_1]+\cdots+...
[三维不重复数点]2022牛客暑期多校训练营4 E【Jobs (Hard Version)】题解
题目概述Jobs (Hard Version)解题报告首先我们先考虑二维不重复数点问题:不难发现按照 $x$ 排序后,只有 $y$ 递降的那些点是有用的,其他点肯定都被包含在了某些点中。假设前一...
[离线+Trie+倍增]2022牛客暑期多校训练营2 F【NIO with String Game】题解
题目概述NIO with String Game解题报告感觉赛时榜都歪飞了……这题明明不难却只有20个队过。由于对 $t_i$ 只有单字符加的操作,因此最终所有 $t_i$ 长度和不会很长,可以...
[树上解方程+组合数化简]2022牛客暑期多校训练营3 D【Directed】题解
题目概述Directed解题报告这题竟是脑子题……显然这是个树上解方程的题目,设 $D_x$ 为 $x$ 的度数,$fa$ 为 $x$ 的父亲,$u$ 为 $x$ 儿子:$$ f_{x}={1\...
[后缀自动机parent树+虚树]2022牛客暑期多校训练营1 B【Spirit Circle Observation】题解
题目概述Spirit Circle Observation解题报告找性质题最烦了.jpg。首先建SAM,考虑一个直观的做法。直接考虑枚举SAM里的节点,然后在节点上考虑 $a999\cdots$...
[线段树合并/分裂]2022牛客暑期多校训练营1 F【Cut】题解
题目概述Cut解题报告这题思路是不难的,但是如果没写过类似的就会巨难写(细节比较多)……把 $[l,r]$ 内的排序其实就是认为 $[l,r]$ 这一块按照权值线段树的顺序进行排列(正序或者倒序...
[背包回退+二进制状压DP+NTT]2022牛客暑期多校训练营1 H【Fly】题解
题目概述Fly解题报告首先想到DP:$f_{i,j,0/1/2}$ 表示前 $i$ 个二进制位(从低位到高位),到 $i$ 这位时背包大小为 $j$ ,并且状态为 $0$ 小于 $1$ 相等 $...