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

xxseven · 2025-11-29 19:54:03 · 题解

看到好多人说难写难调，我的做法实现貌似很简单啊！

考虑什么情况会算错。

如果性价比最高的是 w_i =2 的物品，选了一定不会出错，因为不选它也没有更好的能选。

但如果选了 w_i=1 的物品，可能会在后面没钱选一个 w_i=2 的物品，只能再选择一个 w_i=1 但是很弱的物品，导致两件加起来没有那件贵的强。

也就是说，记 w_i=1 的两件物品为 x,z，w_i=2 的物品为 y，我们会把最优方案 \dots y 选成 \dots x \dots (y)z，其中最后一个省略号的物品全部有 w_i=2。

我们称上述错误中第一件 w_i=1 的物品是特殊物品，w_i=2 的物品为正确物品。

尝试直接对这个结构进行计数。首先把所有 a 排序。

然后，枚举特殊物品 x 和正确物品 y。正确物品的价值比特殊物品要高，但性价比更低，因此要保证 a_x \lt a_y \lt 2\times a_x 。

对于性价比大于 y 的物品，我们一定会选择。

• 对于原价已经大于 a_y 的物品，无论价格总会被选，会消耗 1 或 2 元。这样的物品有 n-y 个。
• 对于原价在 a_x 和 a_y 之间的物品，w=1 时性价比优于 y 会被选，会消耗 0 或 1 元。这样的物品有 y-x-1 个。
• 对于原价在 \frac{a_y}{2} 和 a_x 之间的物品，由之前错解的形态可知一定不会被选，只能 w=2 并消耗 0 元。

以上三种情况涵盖了 x 以外性价比大于 y 的所有情况，可知之后我们只有 1 元钱了，它会用来选择 z。

也就是说，上述所有物品中我们会花掉 m-2 元钱。先扣掉 1/2 元中的 1 元，变成在 n-x-1 个物品中选 m-2-(n-y) 个花掉 1 元。组合数可以 O(1) 计算。

对于原价小于 a_x 的部分，我们只需要让 a_p + a_x \ge a_y 的部分都不成为 z 即 w=2，剩余的随便选即可。

相当于找到最大的 p 满足 a_p+a_x \lt a_y，前面的方案数即为 2^p。p 显然可以在枚举 y 时使用双指针求出。

时间复杂度 O(n^2)，代码非常好写。

#include<bits/stdc++.h>
using namespace std;
const int N=10005,P=998244353;
int n,m,a[N];
int pow2[N],C[N][N];
void init(){
    pow2[0]=1; for(int i=1;i<=10000;++i) pow2[i]=(2ll*pow2[i-1])%P;
    C[0][0]=1;
    for(int i=1;i<=10000;++i) {
        C[i][0]=1;
        for(int j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int ID,T; cin>>ID>>T;
    init();
    while(T--) {
        cin>>n>>m;
        for(int i=1;i<=n;++i) cin>>a[i];
        sort(a+1,a+n+1);

        int ans=0;
        for(int i=1;i<=n;++i) {
            int pos=0;
            for(int j=i+1;j<=n;++j) {
                if(a[i]==a[j]||(m-2-(n-j))<0) continue;
                if(a[j]>=a[i]*2) break;
                while(pos<n&&a[pos+1]+a[i]<a[j]) pos++;
                ans=(ans+1ll*C[n-i-1][m-2-(n-j)]*pow2[pos])%P;
            }
        }
        cout<<(pow2[n]-ans+P)%P<<'\n';
    }
    return 0;
}

希望这篇题解能够帮到你！