比赛链接

upsolved by JJLeo

给定$n$个字符串，设$x$是最大的使$s_i$长度为$x$的前缀和$s_j$长度为$x$的后缀相等的数，有$f(s_i,s_j)=x$，求$\sum_{i=1}^n \sum_{j=1}^n {f^2(s_i,s_j)} \pmod {998244353}$。$(1 \le n \le 10^5, 1 \le \sum |s_i| \le 10^6)$

考虑每个前缀有多少个后缀和它相等，可以用广义后缀自动机，也可以把哈希开到$\text{long long}$用$\text{unordered_map}$过。但这样直接算会算重，考虑去重：求出每个字符串的$\operatorname{next}$数组，则将$\operatorname{cnt}[\operatorname{next}[i]]$减去$\operatorname{cnt}[i]$即可。

solved by 2sozx

给定平面上 $n$ 个点，问最多有多少个点与圆点共同在一个圆上。$n \le 2000$

我们枚举其中的两个点，设两个点的坐标为 $(x_1,y_1),(x_2,y_2)$ ，则这两个点和圆点所确定的圆的圆心为 $$(\frac{y_1y_2^2-y_2y_1^2+y_1x_2^2-y_2x_1^2}{2(x_2y_1-x_1y_2)},\frac{x_1y_2^2-x_2y_1^2+x_1x_2^2-x_2x_1^2}{2(x_1y_2-x_2y_1)})$$ 之后根据我们的枚举方法，每个圆心所能被统计到的次数 $T$ 和圆上的点数 $x$ 有 $T=\frac{x(x-1)}{2}$，最后取 $\max$ 即可

solved by JJLeo

给定一棵树，求最少需要多少条链才能覆盖所有边，可重复覆盖。

类似找重心的方式，叶节点权值为$1$，非叶节点权值为$0$，找到一个点使得以其为根则每个儿子所在子树的叶子节点都不超过总叶子节点的一半。维护一个大根堆，每次剩余找叶子节点最多的两个子树拉两个叶子节点进行配对，如果奇数个叶子节点多余的一个和根节点配对即可。

solved by 2sozx

签到

签到

upsolved by JJLeo

给出一些$n$个值$a_1,a_2, \cdots , a_n$，问可重复地挑选$1,2,3, \cdots n$个值异或和的最大值。$(1 \le n \le 2 \times 10^5, 0 \le a_i < 2^{18})$

solved by Bazoka13

$A[i][j]$的值是$lcm(i,j)$，求所有$k*k$子矩阵里最大值的和。

对行对列单调队列处理就好了

upsolved by JJLeo

solved by 2sozx

给定一个 $multiset$ ，起始为空，有三种操作，前两种是插入删除，第三种是查询 $x$ 问集合中是否有两个元素 $a,b$ 使得 $a,b,x$ 构成三角形。$q \le 2 \times 10^5,x \le 10^9$

我们先考虑查询。

• $x > \max(a,b)$ 时，我们可以通过 $multiset$ 查询小于等于 $x$ 的最大两个元素是否能够与 $x$ 构成三角形即可。
• $\min(a,b) < x < \max(a,b)$ 时，也可以通过 $multiset$ 查询小于 $x$ 的最大元素和大于 $x$ 的最小元素即可。
• $x < \min(a,b)$ 时，我们即为查询是否存在相邻的 $a,b$ 使得 $x < |a-b|$ ，这个可以通过权值线段树进行取 $\min$ 操作即可。

由于权值为 $1\sim10^9$ 因此我们需要动态开点。

upsolved by JJLeo

solved by JJLeo

upsolved by JJLeo