题解：P14636 [NOIP2025] 清仓甩卖 / sale（民间数据）

Hanjiang · 2025-11-29 17:58:21 · 题解

首先对题意进行一下扫盲：

并不是指对于任意定价方案能达到的原价总和最大值。

而是指对于某个给定的定价方案，它利用小 R 的策略买糖果时，能否达到对于这个给定的定价方案的原价总和最大值。

大家一定要好好看样例解释啊！

然鹅我就是因为没看，被hack了十五分钟。

那么我们思考一下，在什么情况下，这个按照性价比降序排序的策略不最优。

看一下下面这个例子：

m=5
u_i  6 5 10 8 2 
w_i  1 1 2  2 1

我们用 u_i 来代替 a_i。

我们模拟一下这个策略，先对 \frac{u_i}{w_i} 降序排序（已经完成）。

那么首先会购买前三个糖果，然后因为钱不够，不能买第四个糖果，只能跳过这个，最后买第五个糖果。

那么原价为 6+5+10+2。

但是我们可以不选第二个和第五个糖果，而购买第四个糖果。

那么原价为 6+10+8，更加优秀。

这启发我们，这个策略可能在某些情况下买两个 w_i=1，而这比买一个 w_i=2 的劣。

观察这个策略买的糖果的位置，可以发现：

买的糖果的区间可以表示为 [1,p]\cup\{c\}。

究其根本，是因为在买了第 p 个糖果后，只剩下 1 块钱，被迫放弃后面所有的 w_i=2 的糖果，最后在后面捞一个 w_i=1 的糖果，也就是第 c 个糖果。

记在 [1,p] 中买得原价最小的 w_i=1 的糖果下标为 a，[p+1,c-1] 中原价最大 w_i=2 的糖果下标为 b。

那么如果 u_a+u_c<u_b，那么就可以把糖果 a 和 c 换成糖果 b，得到更优的结果。

于是这道题考虑反着做，计算所有使策略不优的定价方案数，也就是存在三元组 (a,b,c) 的定价方案个数，然后和总可能数 2^n 做差就行。

我们将原数组 u 进行降序排序，以及定义一个新数组 v 为根据 \frac{u_i}{w_i} 降序排序的数组。而下文中的 a,b,c 表示的是糖果在 u 的下标，p_a,p_b,p_c 表示的是糖果在 v 的下标。

观察 (a,b,c) 的性质：

1. 规定 a<c，则 a 是倒数第二个买的 w_i=1 的糖果，而 c 是最后一个买的糖果，b 是第一个被跳过的 w_i=2 的糖果，毕竟是找出一组 u_a+u_c<u_b，那么左边的值越小越好，右边的值越大越好。注意 a 不一定是倒数第二个买的糖果。

先考虑枚举 (a,b)。

现在是让小 R 在买完糖果 a 和一堆 w_i=2 的糖果后，仅剩 1 块钱去买糖果 c。

分类讨论 u 中的下标 i：

可以画图理解一下，明白一点：

中的大小关系，与在 u 中的大小关系是一致的...

如果实在不明白，再看看性质 1 中关于 b 的描述吧。

根据上述分讨，可以先让 m 在 [1,b-1]\cup {a} 中减一个 1。

然后在 [1,b-1]\cup[b+1,a-1] 中选一些位置，让 m 再减一个 1，使 m 变到 1。方案数为 C^{m-b-1}_{a-2}。

现在加上 c，只要使 u_a+u_c<u_b 就好，那么考虑从 n\rightarrow 1 枚举 u_i，找到第一个 u_a+u_i\ge u_b 的位置，则方案数乘上 2^{n-i}。因为在 i 之后的位置的 w_i 可以为 1 或 2，而 i 之前的位置的 w_i 只能为 2，由 (a,b,c) 的性质 1 和 3 可得。

将 b 从 a-1\rightarrow 1 枚举，发现 u_b 单调不降，则用一个双指针维护 c 就可以了。

则将 u 数组降序排序后，最终答案为：

其中，k 表示满足 u_l \le u_r+u_k 的最大下标。

预处理 2 的幂次和组合数后，时间复杂度为 O(n^2)。

代码如下：

#include <iostream>
#include <algorithm>
#define maxn 5005
#define int long long
#define mod 998244353
using namespace std;
int c,t,n,m,a[maxn],qw2[maxn],fac[maxn],inv[maxn];
int C(int n,int m){
    if(n<0||m<0||n<m) return 0;
    return fac[n]*inv[n-m]%mod*inv[m]%mod;
}
signed main(){
    qw2[0]=fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(int i=1;i<=maxn-5;i++) qw2[i]=qw2[i-1]*2%mod;
    for(int i=2;i<=maxn-5;i++) fac[i]=fac[i-1]*i%mod;
    for(int i=2;i<=maxn-5;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=2;i<=maxn-5;i++) inv[i]=inv[i-1]*inv[i]%mod;
    cin>>c>>t;
    while(t--){
        int ans=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+n+1),reverse(a+1,a+n+1);
        for(int r=1;r<=n;r++){
            int k=n;
            for(int l=r-1;l>=1;l--){
                if(a[r]<a[l]&&a[l]<a[r]*2){
                    while(a[l]>a[r]+a[k]) k--;
                    ans=(ans+C(r-2,m-l-1)*qw2[n-k])%mod;
                }
            }
        }
        cout<<(qw2[n]-ans+mod)%mod<<"\n";
    }
}