NOIP 2025 T2 清仓甩卖题解

传送门：P14636 [NOIP2025] 清仓甩卖

题目概览

题目难度：省选/NOI-

知识点：组合数学；双指针；枚举

简要题意

有

n

颗糖果，其中第

i

(

1 \le i \le n

) 颗糖果的原价为

a_i

元。设第

i

(

1 \le i \le n

) 颗糖果的清仓价格为

w_i \in \{1,2\}

元，则它的性价比被定义为

\frac{a_i}{w_i}

。

小 R 带了

m

元钱买糖果。采用了以下购买策略购买糖果：将所有糖果按照性价比从大到小排序，然后依次考虑每一颗糖果。若他在考虑第

i

(

1 \le i \le n

) 颗糖果时剩余的钱至少为

w_i

元，则他会购买这颗糖果；否则他会跳过这颗糖果，继续考虑下一颗。特别地，若存在两颗糖果的性价比相同，则他会先考虑原价较高的糖果；若存在两颗糖果的性价比与原价均相同，则他会先考虑编号较小的糖果。

在所有

2^n

种定价方案中，有多少种定价方案使得按照上述购买策略能购买到的糖果的原价总和最大。求出满足要求的方案数对

998,244,353

取模。

多组测试数据，设

N

为单个测试点内所有测试数据的

n

的和。对于所有测试数据，均有：

$1 \le t \le 5 \times 10^4$ ；
$1 \le n \le 5,000$ ， $N \le 5 \times 10^4$ ， $1 \le m \le 2n - 1$ ；
对于所有 $1 \le i \le n$ ，均有 $1 \le a_i \le 10^9$ 。

题解

观察小 R 购买的贪心策略，他一定是先买了前面连续的一段糖果，买到第

u

颗糖果时钱不够了。要想造成他购买的与最优方案不符，只能是在决策第

u

颗糖果是剩余

1

元，此时他会等到下一个

1

元糖果

v

的出现，此时最优答案可能是把最后买到的

1

元糖果

v

和之前买过的一个

1

元糖果

k

删除，替换成

2

元糖果

u

，即满足条件

a_u>a_v+a_k

。

我们不用真正计算性价比并排序，而是根据原价

a_i

排序，可以把排序后的序列分成三个部分：（

lim

是部分 C 的左端点，稍后介绍求法）

部分 A：第 $1$ 个糖果至第 $u-1$ 个糖果
部分 B：第 $u+1$ 个糖果至第 $lim-1$ 个糖果
部分 C：第 $lim$ 个糖果至第 $n$ 个糖果

三个部分糖果特点如下：

部分 A：都一定是在第 $u$ 颗糖果之前购买
部分 B：若 $w_i=1$ ，则是在 $u$ 之前购买；若 $w_i=2$ ，则是在 $u$ 之后购买
部分 C：都一定是在第 $u$ 颗糖果之后购买

下面确定 B,C 的分界。依据部分 B 糖果的特点，B 中的糖果

i

满足：

a_i>\frac{a_u}{2}(w_i=1)

，可转化为

2a_i>a_u

，如果该式不成立就是部分 C，所以部分 C 的左端点 lim 可以用指针寻找第一个小于等于

a_u

的

2a_i

。

对于枚举的每一个

(u,v)

，开始计算总方案数。

较为容易的是糖果

v

后面的部分，可以任选价格，记本段长度

last=n-v+1

，方案数为

2^{last}

设

cnt_1

为 A 中

w_i=2

的糖的个数，

cnt_2

为 B 中

w_i=1

的糖的个数。

决策糖果

u

时还剩

1

元，所以在这之前一共画了

m-1

元，可以列出等式

m-1=u-1+cnt_1+cnt_2

，可以转化为

cnt_1+cnt_2=m-u

，AB 部分中共有

lim-2

颗糖果，所以总方案数是

2^{last}C_{lim-2}^{m-u}

。

但不要忘记，满足

a_u>a_v+a_k

就能判定为不合法，所以我们可以尝试求出合法的方案数，用总方案数减去合法方案数求不合法方案数。

可以发现，我们能在部分 B 中把第

i

颗糖果的价值调整为 1，之前说过，一旦调整为

1

就意味着这颗糖果会在

u

之前被卖，就有可能作为上面式子中的

k

。还可以把刚刚的式子转化为

a_k<a_u-a_v

，推断随着

v

的不断增大，

a_u-a_v

不断增大，

a_k

取值的上界会越来越宽松，所以可选的

k

就是部分 B 的一段后缀，且左端点

l

在

v

的增大中越来越靠左，同样可以用指针维护左端点

l

。

记可选

k

的区间长度为

len=lim-l

，只有可选

k

区间里都填

2

才能合法，所以合法的方案数为

2^{last}C_{lim-2-len}^{m-u}

。

所以不合法方案数为

2^{last}(C_{lim-2}^{m-u}-C_{lim-2-len}^{m-u})

。

最终答案就是用总方案数

2^n

减去不合法方案数：

2^n-\sum_{u=1}^{n}\sum_{v=u}^{n}2^{last_v}(C_{lim_v-2}^{m-u}-C_{lim_v-2-len_v}^{m-u})

。

NOIP 2025 T2 清仓甩卖题解

文章操作