A

设合成了 $x$ 个钻石锹，$y$ 个钻石剑。那么可以列出来

$$ \begin{aligned} \text{maximize } x+y\\ \text{s.t. }\begin{cases} x+2y \leq a\\ 2x+y \leq b \end{cases} \end{aligned} $$

可以得到 $3x+3y \leq a+b \Rightarrow x+y \leq \frac{a+b}{3}$。

并且我们可以发现两个显然的限制是 $x+y \leq \min\{a,b\}$，直接输出就好了。发现只有这三个限制。

B

每次操作区间 $[l,r]$：

• 这个区间全 $0$：操作后也是 $0$，没影响
• 这个区间有一个 $1$：操作后所有的位置都可能是 $1$，标记一下就好

初始的区间是 $[x,x]$ 直接操作下去就好。

C

每一个串长度都是 $n+m-1$ 的，画一下图可以发现

• $n+m-1$ 是偶数：对角线上的数字都相等
• $n+m-1$ 是奇数：除了从左往右数 $\frac{n+m}{2}$ 个对角线，其他对角线都要满足数字相等。

画图就是找到 $(1,1)\to (1,2)\to \ldots \to (1,m) \to (2,m) \to \ldots (n,m)$ 和 $(1,1) \to (1,2) \to \ldots \to (1,m-1) \to (2,m-1) \to \ldots \to (n,m-1) \to (n,m)$，由于前面一大块都是相等的，回文过去也是相等的，把相等的数连线，发现是对角线（：

D

不好想。。

题目要求 $(x+y,a) = 1$，我们设 $g=(x,y)$，那么有 $x' = \frac{x}{g},y' = \frac{y}{g}$，也就是 $g(x'+y')=x+y$。我们注意到 $x|a,y|a$，所以 $g|a$，所以 $g|(g(x'+y'),a) = (x+y,a)$。所以必须 $g=1$。选出两个互质的因子就好了。

E

由于 $b$ 是单调递增的，我们考虑对 $a$ 做后缀和 $suf$，每个分割的位置一定满足 $b_i = suf_j$，乘法原理就行了。

F

首先思考一下暴力dp：设 $f_{i,j}$ 表示走了 $i$ 条边，在点 $j$ 的答案。我们发现最多走 $m$ 次一定可以到达任意一条边，之后我们的最优策略一定是在这条边反复横跳。设点 $v$ 所有相邻的边的边权最大值为 $mx_v$，我们选择点 $v$ 开始反复横跳的答案就是 $F_v(k)=(k-m)mx_v+f_{m,v}$。

现在相当于要求 $\sum_{i=1}^q \max_{v=1}^n F_v(i)$。发现相当于多个一次函数取最大值，对这些直线建一个下凸壳就好了。不得不说下凸壳有一些实现细节，应该是好久没写了吧。。

G

显然的想法是设 $f_{i,j}$ 表示 $s$ 匹配到前 $i$ 位，$t$ 匹配到前 $j$ 位，删除的最少字符，有转移：

• $f_{i,j}+1 \to f_{i+1,j}$
• $f_{i,j} \to f_{i+1,j+1}(s_{i+1}=t_{j+1})$
• $f_{i,j} \to f_{i+1,j-1}(s_{i+1}= \cdot)$

但是发现这样处理不出来我们加入一些毫不相关的字符然后全删掉的情况：对于这种情况我们预处理 $nxt_i$ 表示 $i$ 开头最短的一段区间，执行操作后全被删光，加入一种新转移 $f_{i,j} \to f_{nxt_i,j}$ 即可。