为什么 Edu G 题好多字符串啊?

A

按照题意模拟即可。(可以借鉴一下玩几何冲刺的感想)

B

一开始看错题了,以为每次只能取一个区间。。题目是每次可以取一个子序列。

那么我们就从大到小排序,贪心尽量选择多的数,选到最后一个能让平均值 $\geq x$ 的值即可。

子区间版本我还不会,有谁会可以教教我。

C

只有一个位置不会被爆炸伤害,枚举这个位置就可以了。如果一个位置被爆炸伤害需要的费用就是 $\max\{0,a_i-b_{i-1}\}$,否则就是 $a_i$。

D

打表找规律发现序列形如 $1,2,1,3,1,4,\ldots,2,3,2,4,\ldots\ldots,n-1,n$,然后就可以做了,定位到第一个点的位置然后暴力循环即可。

比如 $n=3$ 的序列就是 1 2 1 3 2 3,$n=4$ 的序列就是 1 2 1 3 1 4 2 3 2 4 3 4

E

首先如果 $a|b$ 那么最短路一定是 $d(b)-d(a)$(每次随便选一个 $p$ 乘上去就行)

其他情况我们的路径肯定是先单调除/乘一个数,再单调乘/除一个数,不会出现交替的情况(因为这样会多加一个数的 $d$),所以我们现在就是要考虑选择 $\gcd(a,b)$ 还是 $\text{lcm}(a,b)$ 中转。

我们断言使用 $\gcd(a,b)$ 中转最优,然后我们就可以分别算出 $a \to \gcd(a,b)$ 和 $\gcd(a,b) \to b$ 的路径条数,直接相乘就好了。

接下来我们考虑如何算出 $a \to \gcd(a,b)$,设一个数唯一分解后的形式是 $a=\prod_{i} p_i^{e_i},\gcd(a,b) = \prod_{i} {p'}_i^{{e'}_i}$,可以设 $\Delta_i = e_i-e'_i$,答案相当于有 $\sum \Delta_i$ 个数,第 $i$ 类有 $\Delta_i$ 个,相同类别的数之间不可区分,问路径方案数这样一个组合问题,也就是多重集排列组合。

证明

一个不知道对不对的乱写的证明

首先最优一定是中间不拐弯的一种走法(先一直除再一直乘),设 $g = \gcd(x,y),l = \text{lcm}(x,y)$,我们只需要证明 $x \to g \to y$ 比 $x \to l \to y$ 优就好了。

也就是要证明:

$$ \begin{aligned} d(x)-d(g)+d(y)-d(g) &\leq d(l)-d(x)+d(l)-d(y)\\ d(x)+d(y) &\leq d(l)+d(g) \end{aligned} $$

考虑 $\gcd,\text{lcm}$ 和因数个数 $d$ 的本质定义,实际上是要证明

$$ \prod_{i=1}^m a_i + \prod_{i=1}^m b_i \leq \prod_{i=1}^m \max\{a_i,b_i\}+\prod_{i=1}^m \min\{a,b\} $$

其中 $\forall i,a_i,b_i \geq 1$。

考虑使用数学归纳法:$m=1$ 时显然成立($a+b \leq a+b$),现在我们先证明 $m=2$ 成立:

不失一般性我们设 $a_1 \leq b_1$,接着分类讨论:

  • 如果 $a_2 \leq b_2$:式子变成了 $a_1a_2+b_1b_2 \leq b_1b_2+a_1a_2$,显然成立;
  • 如果 $a_2 > b_2$:式子变成了 $a_1a_2+b_1b_2 \leq b_1a_2+a_1b_2$,发现这是一个排序不等式的形式($a_1 \leq b_1,b_2 < a_2$ 是排好序的,所以 $a_1b_2+b_1a_2 \geq a_1a_2+b_1b_2$);
    附:排序不等式维基页面

考虑对于 $m > 2$,我们使用数学归纳法,设 $A=\prod_{i=1}^{m-1} a_i,B = \prod_{i=1}^{m-1} b_i,C = \prod_{i=1}^{m-1} \max\{a_i,b_i\},D=\prod_{i=1}^{m-1} \min\{a,b\}$,那么有 $A+B \leq C+D$,我们现在要证明 $Aa_i+Bb_i \leq C\max\{a_i,b_i\}+D\min\{a_i,b_i\}$,只需要注意到 $C \geq \max\{A,B\},D \leq \min\{A,B\}$ 即可类似上面讨论证明。

F

这种匹配的题都可以设 $f_{i,j}$ 表示考虑了 $a$ 串前 $i$ 个和 $b$ 串前 $j$ 个的最小代价,于是有转移:

$$ \begin{aligned} f_{i,j} \to \begin{cases} f_{i+1,j}+p_{i+1},\\ f_{i+1,j},& a[i+1] \leq b_{i+1}\\ f_{i+1,j+1}+p_{i+1}, &a_{i+1} = b_{i+1}\\ \end{cases} \end{aligned} $$

考虑用线段树维护第二维,注意到第三种操作只会修改一个位置即可。(事实上可以写树状数组)

最后是需要一个一个后缀加,单点查询的数据结构,取最大值讨论一下 $p$ 的正负就行了。

G

首先介绍一下字符串匹配的 FFT 做法:

设文本串为 $s$,模式串为 $t$,我们可以设两个位置的匹配函数 $c(i,j) = (s_i-t_j)^2$,于是 $s$ 以 $x$ 开头的一段字符串是否和 $t$ 匹配就是 $f_x = \sum_{i=1}^m c(x+i-1,i)$ 是否为 $0$,拆开后发现是一个卷积的形式,直接做就行了。

对于这个题我们可以发现匹配函数是 $c(i,j) = (s_i-t_j)^2(s_{p_i}-t_j)^2$,也直接做就行了。

注意到我们如果是 $\bmod 998244353$ 等价于在这个质数下取模,但这显然不够会被卡,我们可以有一下解决方案:

  1. 多模数
  2. 每个字符随机权值
  3. 随机模数

感觉 $2$ 比较好。。也不用多背几个 NTT 模数。

懒得把公式抄上去了,对着看下吧

Last modification:September 10th, 2020 at 10:36 am
如果觉得我的文章对你有用,请随意赞赏