本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-11 15:20:48

记录

只切到 C，D 数论和 E 计数没做出来，后来补了。

题解

A. Shovels and Swords

贪心，假设有 $a>b$，先把 $a-b$ 的差值用 $2$ 个 $a$ 和 $1$ 个 $b$ 消耗掉，若 $b$ 不够直接结束，否则已有 $a=b$，先用两者各 $3$ 个做，最后若余下 $2$ 个还能再做一个。

B. Shuffle

发现 $1$ 最终的可能位置永远是一段连续区间，因此维护该区间左右端点，每次操作若与目前的区间有交，则答案与操作区间取并集即可。

C. Palindromic Paths

显然要走 $x=n+m-2$ 步，发现要求即为对于 $i\in[0,\frac{x}{2})$ 的所有 $i$，要求所有第 $i$ 步的格子和第 $x-i$ 步的格子全部颜色相同，所以开桶记录每一步的格子颜色情况，取黑白中较少的一种修改即可。

D. Two Divisors

发现无解情况只有 $x=p^k$ 时，选出的数相加与 $x$ 一定有公因数 $p$。因此考虑把 $x=p^kq$ 的最小质因子 $p$ 拿出来，除掉所有 $p$ 后剩下 $q$，$p,q$ 即为一组可行解。

考虑证明，$\gcd(p+q,a)=\gcd(p+q,p^kq)$，由于 $p$ 是质数且 $p\neq q$，因此 $p+q$ 一定不为 $q$ 的倍数，且 $q$ 中无 $p$ 这一质因子，因此 $p+q$ 一定不为 $p$ 的倍数，所以 gcd 一定为 $1$

E. Two Arrays

发现 $b_i$ 单增，考虑把 $a$ 变为单增序列，设 $c$ 为 $a$ 后缀最小值，则对于每个 $b_{i}$，分界处必然要选在所有 $c_k=b_{i}$ 的位置之前，才能保证该区间最小值等于 $b_i$。

因此每个 $b_i$ 分界的选择方案数有 $c$ 中 $b_i$ 的出现次数个。特别地，若 $b_1\ne c_1$ 则无解，乘法原理统计答案即可。