ZigZagK的博客
[主席树二分+复杂度分析]牛客IOI周赛28-提高组 C【下克上の天邪鬼】题解
题目概述下克上の天邪鬼解题报告顺着 ${\lfloor{a_i\over 2}\rfloor}\le a_j<a_i$ 想,不难想到利用这个 $\lfloor{a_i\over 2}\rf...
[思维+后缀数组+调和级数]LOJ2083【「NOI2016」优秀的拆分】题解
题目概述LOJ2083解题报告想了很久匹配做法,不会做,实际上是性质题……如果能求出 $pre_i$ 表示以 $i$ 结尾的 $AA$ 个数和 $suf_i$ 表示以 $i$ 开头的 $BB$ ...
[除法分块+Min25筛]2021 CCPC 威海 I【Distance】题解
题目概述Distance解题报告$i$ 走到 $j$ 不管怎么走,每个相差的素数都必须走一遍,所以...
[cdq分治+阈值优化+NTT]2022ICPC网络赛第一场 I【Permutation】题解
题目概述给出一个排列 $\{a_n\}$ ,对于这个排列的所有循环同构,求出排列的排名,对所有排名求和。解题报告对于一个固定的 $\{a_n\}$ ,根据康托展开,可以得到排名:$$ 1+\su...
[后缀数组+复杂度分析]2022牛客暑期多校训练营7 I【Suffix Sort】题解
题目概述Suffix Sort解题报告一直在想Hash,然后寄了……实际上应该分析一下性质。首先有一个比较显然的想法是将 $S$ 变为另一个数组,$a_i$ 表示 $S_i$ 与上一个相同字符的...
[DP+复杂度分析]2022“杭电杯”中国大学生算法设计超级联赛(7)【Counting Good Arrays】题解
题目概述HDU7217解题报告一个显然的想法:定义 $f_{i,j}$ 表示放了 $i$ 位,第 $i$ 位为 $j$ 的方案数,那么:$$ f_{i,j}=\sum_{d|j}f_{i-1,d...
[后缀自动机parent树+虚树]2022牛客暑期多校训练营1 B【Spirit Circle Observation】题解
题目概述Spirit Circle Observation解题报告找性质题最烦了.jpg。首先建SAM,考虑一个直观的做法。直接考虑枚举SAM里的节点,然后在节点上考虑 $a999\cdots$...
[线段树合并/分裂]2022牛客暑期多校训练营1 F【Cut】题解
题目概述Cut解题报告这题思路是不难的,但是如果没写过类似的就会巨难写(细节比较多)……把 $[l,r]$ 内的排序其实就是认为 $[l,r]$ 这一块按照权值线段树的顺序进行排列(正序或者倒序...
[阈值优化+分块]洛谷5309【[Ynoi2011] 初始化】题解
题目概述Luogu5309解题报告题目保证 $y\le x$ ,因此每次都是全局 $i\bmod x=y$ 的 $a_i$ 加上 $z$ 。不难想到 $x>\sqrt n$ 时,我们直接暴...
[线段树+复杂度分析+差分+树状数组]2021牛客暑期多校训练营7 B【xay loves monotonicity】题解
题目概述xay loves monotonicity解题报告首先我们很自然联想到楼房重建那道题,定义 $Find(p,l,r,i)$​​​ 表示在 $[l,r]$​​​ 的节点 $p$​​​ 前...