题目概述Jewel Grab解题报告因为 $k\le 10$ ，其实就是个暴力题。记录 $pre_x$ 表示 $x$ 前面第一个颜色相同的位置（没有就记成 $0$ ），如果不能跳过，那么一定是在...

题目概述Ayano and sequences解题报告其实并不是很难，但感觉考场上性价比不高 🤔 ，也可能只是我们队做的太慢了 😭 。这个问题如果在线做会发现涉及到时间和区间两个维度，并不是很好...

题目概述Hold the Line解题报告直接线段树套set是过不了的，我们需要一个小常数的做法。考虑离线，这样第 $i$ 次事件插入 $x$ 位置时，就可以认为是 $i$ 时刻 $x$ 才出现...

题目概述Alice's Dolls解题报告定义 $f_{n,k}$ 表示要得到 $n$ 个物品，$x^k$ 的期望。$n>1$ 的情况十分复杂，但是根据期望的线性性，$n>1$ 的情...

题目概述Distance解题报告$i$ 走到 $j$ 不管怎么走，每个相差的素数都必须走一遍，所以...

题目概述给出一个排列 $\{a_n\}$ ，对于这个排列的所有循环同构，求出排列的排名，对所有排名求和。解题报告对于一个固定的 $\{a_n\}$ ，根据康托展开，可以得到排名：$$ 1+\su...

题目概述Generating Strings解题报告裸的回文自动机回退。对于一个长度为 $len$ 的回文串，在 $s$ 中出现一次的权值为 $(N-len+1)\cdot26^{N-len}$...

题目概述LCS Spanning Tree解题报告听说这题卡倍增SA，表示强烈谴责😡（不过我没想到SA怎么做）。由于需要求任意两个字符串之间的最长公共子串，因此考虑广义SAM，在构造时，记录一下...

题目概述String Problem解题报告首先很显然，对于前缀 $i$ ，答案一定是某一个位置到 $i$ 。用后缀数组可以做，但是思考起来比较麻烦。考虑后缀自动机，在建立后缀自动机的时候我们记...

题目概述Karshilov's Matching Problem解题报告首先不难想到对 $n$ 个匹配串建AC自动机，在 $fail$ 树上求和就可以得知匹配到 $p$ 点时的权值和。然后我们观...