P14636 [NOIP2025] 清仓甩卖

过了所有大样例和洛谷数据。虽然 4h 才切，但也算是一雪前耻了。

前置知识

上一场 ABC 不是白打的。

Hint

正难则反，取不到最大原价总和只有两种情况：

最优解选性价比较低的 $2$ ，小 R 选性价比较高的 $1$ 。
最优解选性价比中的 $2$ ，小 R 选性价比较高的 $1$ 和性价比较低的 $1$ ，且两个 $1$ 的原价之和低于 $2$ 的原价。

显然上述的

2

是最优解中选取的性价比最低的

2

，上述的

1

是小 R 选取的性价比最低的

1

。

按原价从大到小排序，枚举：

对于第一种情况，枚举最优解的 $2$ （记为 $i$ ）以及小 R 的 $1$ （记为 $j$ ），则 $a_i>a_j>\frac{1}{2}a_i$ ，而所有 $k>j$ 必有 $w_k=2$ ，枚举 $u$ 为 $1\sim i-1$ 中 $2$ 的数量，则方案数为：

\sum_{u=0}^{i-1}\dbinom{i-1}{u}\dbinom{j-i-1}{m-(i-1)-u-2}=\dbinom{j-2}{m-i-1}

对于第二种情况，枚举最优解的 $2$ （记为 $i$ ）以及小 R 的较高的 $1$ （记为 $j$ ），则 $a_i>a_j>\frac{1}{2}a_i$ ，设 $p$ 为使得 $a_k+a_{j}< a_{i}$ 的最小下标 $k$ ，枚举 $u$ 为 $1\sim i-1$ 中 $2$ 的数量，则方案数为：

2^{n-p+1}\cdot\sum_{u=0}^{i-1}\dbinom{i-1}{u}\dbinom{j-i-1}{m-(i-1)-u-2}=2^{n-p+1}\cdot\dbinom{j-2}{m-i-1}

时间复杂度

\mathcal{O}(\sum n^2)

，空间复杂度

\mathcal{O}(n^2)

或

\mathcal{O}(n)

。

[NOIP2025] 清仓甩卖 - sale.cpp

CPP

1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>
using namespace std;
const int maxn=5010;
const int mod=998244353;
int dp[maxn][maxn],pre[maxn],a[maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    dp[0][0]=pre[0]=1;
    for(int i=1;i<=maxn-10;i++){
        dp[i][0]=1;
        pre[i]=pre[i-1]<<1;
        if(pre[i]>=mod) pre[i]-=mod;
        for(int j=1;j<=i;j++){
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
            if(dp[i][j]>=mod) dp[i][j]-=mod;
        }
    }
    int c,t;cin>>c>>t;
    while(t--){
        int n,m;cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n,greater<int>());
        long long ans=0;
        for(int i=1;i<=n;i++){
            if(m-i-1<0) break;
            int p=n+1;
            for(int j=max(i+1,m-i+1);j<=n;j++){
                if(a[i]==a[j]) continue;
                if(a[i]>=(a[j]<<1)) break;
                while(p>1 and a[p-1]+a[j]<a[i]) p--;
                ans+=1ll*dp[j-2][m-i-1]*pre[n-p+1]%mod;
            }
        }
        cout<<(pre[n]-ans%mod+mod)%mod<<"\n";
    }
    return 0;
}

P14636 [NOIP2025] 清仓甩卖

文章操作

相关推荐

评论

P14636 [NOIP2025] 清仓甩卖