本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-30 17:44:41

记录

A 题唐了吃一发，后边还行，D 题想了一会最终也写出来了，E 感觉很困难没做出。

本来忘了写记录了，现在补一下。

题解

A. Catch the Coin

首先必须要走至少 $\left|x\right|$ 步以到达同一列，同时如果能在某一时刻走到金币正下方，就一定能通过操作来抓住掉下来的金币。所以一直向斜下方走到金币那一列，只要能与金币在同一位置或在正下方即能拿到。

B. Substring and Subsequence

枚举把整个 $a$ 放在 $b$ 的哪个位置之后，然后贪心地尽可能多地匹配上子序列即可。

C. Two Movies

发现若某人对两部电影评价不同，则让其选择评价高的一者一定不劣。否则记录下对两部电影都好评/差评的次数，贪心地尽可能减小两部电影的分数差即可。

D. Smithing Skill

发现金属充足时，一定会先选择损耗最小的一种来获取经验直到不足以制造武器，这样就可以保证剩余的金属不超过 $10^6$。

接下来要考虑统一处理所有的金属量，使得最终可以实现 $O(1)$ 查询。设 $f_i$ 表示剩余 $i$ 金属时最多可以制造的武器数，再设 $s_i$ 表示需要金属不超过 $i$ 的方案中损耗金属的最小值，则 $f_i=\max(f_{i-s_i}+1,f_{i-1})$。预处理好之后分别对 $m$ 个查询答案即可。

E. Distance to Different

发现询问的方案数等价于把整个长度为 $n$ 的序列分成 $x(x\ge k)$ 段的方案数，所以设 $f_{i,j}$ 表示把 $i$ 个元素分成 $j$ 段的方案数，由于段数多后没有特殊限制，所以可以把 $x>k$ 的方案数全部压到 $j=k+1$ 里，得到 $f_{i,j}=\sum_{i'=j-1}^{i-1}f_{i',j-1}$，前缀和处理一下复杂度就对了。

还要注意若存在一段序列中间长度为 $2$ 的段，那么 $b_i=b_{i+1}=1$，与分成两段 $1$ 的结果相同，所以要把这种情况减去。当然若在序列两段则可以取到 $2$，因为这样会使得端点的值为 $2$。