[后缀自动机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$ 相等 $...
[阈值优化+分块]洛谷5309【[Ynoi2011] 初始化】题解
题目概述Luogu5309解题报告题目保证 $y\le x$ ，因此每次都是全局 $i\bmod x=y$ 的 $a_i$ 加上 $z$ 。不难想到 $x>\sqrt n$ 时，我们直接暴...
[后缀自动机+拓扑]LOJ3049【「十二省联考 2019」字符串问题】题解
题目概述LOJ3049解题报告把串反过来，那么 $B$ 是 $A$ 前缀就变成 $B$ 是 $A$ 后缀，也就是 $B$ 是 $A$ 在SAM上的parent树祖先，或者B和A在SAM同一个节点...
[矩阵乘法+线段树]Codeforces1701F【Points】题解
题目概述CF1701F解题报告对于 $x$ ，设 $[x-d,x-1]$ 上共有 $cnt$ 个点，那么以 $x$ 作为结尾的三元组个数为 ${cnt\choose 2}={1\over 2}(...
[广义后缀自动机]2021 ICPC 澳门 I【LCS Spanning Tree】题解
题目概述LCS Spanning Tree解题报告听说这题卡倍增SA，表示强烈谴责😡（不过我没想到SA怎么做）。由于需要求任意两个字符串之间的最长公共子串，因此考虑广义SAM，在构造时，记录一下...
[后缀自动机]The 2021 ICPC Asia Shenyang Regional Contest M【String Problem】题解
题目概述String Problem解题报告首先很显然，对于前缀 $i$ ，答案一定是某一个位置到 $i$ 。用后缀数组可以做，但是思考起来比较麻烦。考虑后缀自动机，在建立后缀自动机的时候我们记...
[AC自动机+倍增]The 2021 China Collegiate Programming Contest (Harbin) L【Karshilov's Matching Problem】
题目概述Karshilov's Matching Problem解题报告首先不难想到对 $n$ 个匹配串建AC自动机，在 $fail$ 树上求和就可以得知匹配到 $p$ 点时的权值和。然后我们观...
[矩阵乘法+线段树]The 2021 ICPC Asia Nanjing Regional Contest E【Paimon Segment Tree】题解
题目概述Paimon Segment Tree解题报告首先肯定考虑离线，把询问 $[L,R],[x,y]$ 拆成 $([L,R],[0,y])-([L,R],[0,x-1])$ 。然后我们按顺序...
