CF666E Forensic Examination 题意 给定一个字符串 $s$，以及 $m$ 个字符串 $t_{1 \dots m}$。 $q$ 次询问，每次询问 $s[p_l:p_r]$ 在字符串 $t_{l\dots r}$ 中的哪个串里作为子串出现的次数最多，如果有...

CF700E Cool Slogans 题意 给定一个长度为 $n$ 的字符串 $s$。 你要构造一个最长的字符串序列 $t_{1\dots k}$，满足： 对于 $i \in [1,k]$，$t_i$ 为 $s$ 的子串。 对于 $i \in [2,k]$，$t_i$ 在 $t_{i-...

因为 SA 就很有用了，所以一直不想学 SAM。突然不知道为什么就想学了，可能是为了吊打兔兔吧。 后缀自动机 (SAM) 是一个能解决许多字符串相关问题的有力的数据结构。 直观上，SAM 可以理解为将字符串的所...

CF643D Bearish Fanpages 题意 给定一个 $n$ 个点的基环森林，第 $i$ 个点与 $f_i$ 之间有一条边。 保证在任意时刻，这个基环森林中的环长至少为 $3$。 当一种「神秘事件」发生时，对于第 $i$ 个点，设与...

CF666D Chain Reaction 题意 平面直角坐标系中有四个整点。 你可以将每个点水平或者垂直移动到一个整点，使得这四个点恰好成为一个平行于坐标轴的正方形的顶点（正方形不能退化成一个点）。 如果存在移动...

CF708E Student's Camp 题意 有一个 $(n+2) \times m$ 的网格。 除了第一行和最后一行，其他每一行每一天最左边和最右边的格子都有 $p$ 的概率消失。 求 $k$ 天后，网格始终保持连通的概率。 $n,m \le 1.5...

CF696F ...Dary! 题意 给定一个 $n$ 个点的严格凸多边形。 你要最小化 $r$，使得可以在这个多边形内或多边形上找到两个点，以它们为圆心以 $r$ 为半径作两个圆，满足多边形的每条边所在的直线与至少一个圆...

CF685C Optimal Point 题意 立体直角坐标系中有 $n$ 个整点。 求一个整点满足到这 $n$ 个整点的曼哈顿距离的最大值最小。 $n \le 10^5$。 题解 显然先二分答案。 考虑如何 check，假设此时二分到的值...

CF643F Bears and Juice 题意 有 $n$ 只熊和 $p$ 张床，还有若干个无限大的酒桶（至少一个），其中恰好只有一个酒桶里装着酒，其它酒桶里都装着果汁。 熊一开始不知道哪桶里面是酒，于是进行了一次挑战，...

CF708D Incorrect Flow 题意 给定一张 $n$ 个点 $m$ 条边的网络，源点为 $1$，汇点为 $n$。 对于每条边 $(u,v)$，有容量 $c$，当前流量 $f$。 但这个图是错误的，可能存在 $c < f$，或者流量不守恒的情...