【比赛记录】EDU167

· · 个人记录

记录

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。