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

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

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

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

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

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

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

看一下下面这个例子：

CPP

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)

的性质：

规定 $a<c$ ，则 $a$ 是倒数第二个买的 $w_i=1$ 的糖果，而 $c$ 是最后一个买的糖果， $b$ 是第一个被跳过的 $w_i=2$ 的糖果，毕竟是找出一组 $u_a+u_c<u_b$ ，那么左边的值越小越好，右边的值越大越好。注意 $a$ 不一定是倒数第二个买的糖果。
$a>b$ ， $p_a<p_b$ ，可以理一下： $a>b$ 是因为 $u_a<u_b$ ，而 $p_a<p_b$ 是因为如果 $p_a>p_b$ 那么根据 $v$ 数组的定义，小 R 就不会拿 $a$ 而是拿 $b$ 了。
$a$ 到 $c$ 之间不存在 $w_i=1$ 的糖果。
$u_b\in (u_a,2u_a)$ 。

先考虑枚举

(a,b)

。

现在是让小 R 在买完糖果

a

和一堆

w_i=2

的糖果后，仅剩

1

块钱去买糖果

c

。

分类讨论

u

中的下标

i

：

$i \in [1,b-1]$ ，则 $m\gets m-w_i$ 。
$i \in [b+1,a-1]$ ，如果 $w_i=1$ ，则 $m\gets m-1$ ；否则 $m \gets m$ 。
$i=a$ ，则 $m\gets m-1$ 。

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

w_i=2

的糖果在

v

中的大小关系，与在

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

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

ans=2^n-\sum_{r=1}^{n} \sum_{l=1}^{r-1}C_{r-2}^{m-l-1}\times 2^{n-k},u_l \in (u_r,2u_r)

其中，

k

表示满足

u_l \le u_r+u_k

的最大下标。

预处理

2

的幂次和组合数后，时间复杂度为

O(n^2)

。

代码如下：

CPP

#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";
    }
}

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

文章操作

相关推荐

评论

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