题解：P14636 [NOIP2025] 清仓甩卖 / sale

Reply_ · 2025-11-29 15:51:56 · 题解

退役喽！考场上被控三小时才做出来，但是思维并不难，至少我的做法是蓝题水平。

特殊性质非常良心啊，从特殊性质开始想。先按照原价从小到大排序。考虑 m=2 的情况，如果是个非法状态，那么必然是有一个代价为 1 的在第一位，一个代价为 2 的在第二位，且在第二位往后还有一个代价为 1 的。我们计这三个原价分别为 x,y,z，那么非法状态条件即为 x+y<z，因为此时由于考虑到 y 的时候钱只剩 1 了，将会购买 x+z。

还注意到这个代价为 2 的肯定是原价最大的，枚举第一个代价为 1 的，利用二分或双指针找到下一个代价为 1 的可能的范围便可轻松计算，这个范围的左端点肯定是 1，右端点记为 pos，答案为 2^{pos}。最后将所有状态减去非法状态即可。

考虑正解，枚举上式的 y 和 x 的位置，分别计为 i,j，那么参考下图（虽然很丑）：

横线上方是下标，下方是值的位置。

还是计算非法状态，显然我们 j 的取值是粉色这一段，即 \frac{a_i}{2}< a_j < a_i，显然红色这一段最后会在 i 的前面被购买，绿色这一段如果价格取 1 的话也会在 i 前面被购买，最后一个 1 的位置会在蓝色这一段，这一段中随便取，与特殊性质相同。考虑 i 前面的取值方案。

由于 j 这个点我们一定要取到 1，考虑到 i 的时候需要剩下 1 元钱，那么绿色+红色这一段的需要消耗的钱数为 m-2。

红色这一段每个数要么是 1 要么是 2，绿色这一段要么是 0 要么是 1。朴素想法是枚举每一段用了多少，但是这样时间会爆，其实本质上这两段没有很大的区别，我们将红色的这一段全都提出来一个 1，这样红色绿色两段我们就能合并为一段，再用组合数计算即可得到前面的方案数，和后面的蓝色方案数乘法原理处理即可。

考场上做法过了大样例，但是由于退役了代码就咕咕了，等发代码之后可能会补上吧。