Educational Codeforces Round 9 题解

__vector__ · 2025-01-08 19:53:02 · 题解

A

考虑倒推一开始的苹果总数，记为 ans。从最后一个顾客倒序枚举，如果没有赠送，那么 ans \leftarrow 2ans，如果赠送了，ans \leftarrow 2ans+1。

这样，计算出了一开始的苹果总数，然后再根据购买情况计算收益就可以了。

B

将原序列中原本属于 A 的设计为正值，原本属于 B 的值取反。

然后 Bob 显然会选择权值最大的前缀或后缀。

C

结论：字符串 a,b，a 在 b 前面当且仅当 a+b 的字典序小于 b+a 的字典序。

反证法易证。

D

设 f_x 为数组中 x 的因子个数。

答案显然是 \max\limits_{x \in [1,l]}f(x)。

E

本题正解为 FFT，但是暴力也可以通过，考虑暴力怎么写。

恰好 k 个的限制很烦人，如果是小于等于 k 个就简单多了。

实际上，只要有一个权值为 0 的物品就可以满足这个要求。

没有怎么办？

那就将所有物品的权值减去最小值。

然后 dp 就非常简单了。

F

本题我被卡死，主要原因在于我对 MST 的性质不是很熟悉。

很像是一个邻接矩阵，考虑以此解题。