又一套 Free 题

便宜，货海星。

A

定义一个数字串是字符集为0123456789的串。给出$m$个总长度$\le 50$的数字串$s_1,\cdots,s_m$，给出$n$。求长度为$n$，且$m$个数字串在其中都至少出现一次的数字串的个数。

$n\le 10^9,m\le 4$。

建 AC 自动机，先枚举一下$m$个字符串中强制哪些不出现。然后矩阵快速幂。

$O(2^m(\sum s_i)^3\log_2n)$。

B

给出一个长度为$n$的整数序列$A$，要求将其分成若干段，每一段的长度在$[L,R]$之间，且每一段的价值为：设这一段的权值和为$x$，那么价值为$ax^2+bx+c$。

求最大价值。

$1\le L\le R\le n\le 2\times 10^5,|A_i|,|a|,|b|,|c|\le 10^4,a<0$。

斜率优化，那么转移区间是单调的。那么实际上可以线段树维护区间凸包。插入点的时候如果这个区间满了再构建这个区间的凸包。

$O(n\log_2^2n)$。

对于这种转移区间单调的，还可以考虑双栈，左边的栈只能删除（撤消），右边的只能插入。这样也可以转化为动态凸包问题。

C

给出一棵$n$个点边带非负权的树，求一条路径使得：

• 最大边和最小边之差不超过$m$。
• 路径总长度乘上最小边的长度最大。

$n\le 1\times 10^5$。

可以把边权理解为插入时间。那么按时间分治（线段树分治），然后只有插入。那么维护直径即可。当递归到单点的时候，就知道了最小边的长度，更新答案即可。

$O(n\log_2^2n)$（可撤消并查集）。