【VP 记录】EDU089

· · 个人记录

记录

只切到 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 则无解，乘法原理统计答案即可。