比赛链接

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})$

设可重复选$i$个元素的最大值为$b_i$，可以证明当$n > 19$后有$b_i=b_{i-2}$。证明如下，首先显然有$b_i \ge b_{i-2}$，选两个一样的即可；其次假设$b_i > b_{i-2}$，则说明$i-2$个元素并不能达到最大值，即并不能达到满秩，因此至少$i-1$个元素才能达到满秩，当$n > 19$至少$19$个元素才能满秩，然而由数据范围可以知道秩最大为$18$，矛盾，因此假设不成立，有$b_i \le b_{i-2}$。综上可得$b_i=b_{i-2}$。因此我们将可以得到的值对应下标设为$1$，然后$\text{FWT}$卷积$19$次，然后每次将不为$0$的项改为$1$即可。

solved by Bazoka13

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

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

upsolved by JJLeo

字符串匹配。字符集为正整数，要求模式串每一位都小于等于文本串，文本串长度为$n$，模式串长度为$m$。$(1 \le n \le 150000, 1 \le m \le \min\{n, 40000\})$

$\text{Shift-And}$算法。考虑如何构造出辅助表，即模式串的每一位能否匹配文本串的每一位。只需从小到大将两个串排序，然后从小到大扫一遍将对应的位从$0$改为$1$即可。然而这样空间复杂度为$O(\dfrac{nm}{w})$会$\text{MLE}$，事实可以发现本质只有$m$种不同的$\text{bitset}$，将每一位和每个$\text{bitset}$进行一下对应即可，空间复杂度降为$O(\dfrac{m^2}{w})$，时间复杂度为$O(\dfrac{nm}{w})$。

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

区间$[l,r]$可以变成$[l-1,r],[l+1,r],[l,r-1],[l,r+1]$，现在有$m$个方案可以让你花费$c$禁止掉两个不同区间之间的双向变换，求最小代价使得$[1,n]$无法变成$l=r$的区间，或判断无解。$(2 \le n \le 500, 0 \le m \le n(n-1))$

题目可以转化成如下的平面图，所有有限制的边长度为花费，无限制的边长度为正无穷，转对偶图求最短路即可。

solved by JJLeo

给出一个目标排列$a$，长度为$n$，大质数$k$，现在求一个置换使得$1,2, \cdots ,n$经过$k$次变换成为$a$，或判断无解。$(1 \le n \le 10^5, 10^8 \le k \le 10^9)$

upsolved by JJLeo