本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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 的性质不是很熟悉。

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

$a_{i,j} \le \max(a_{i,k},a_{k,j})$ 的限制，可以理解为一条边的权值不能是任意一个包含它的环的严格次大值。

刚好 MST 的树边也有这个性质，那么如何检测非树边？

假设存在一个不合法的非树边，考虑枚举这个非树边的其中一个端点作为树的根节点，若某个点与根的边权大于它通过树边到根的路径最大值，那么不合法。