P14636 [NOIP2025] 清仓甩卖 / sale

题意

给定 $n$ 个商品，原价 $a_i$，你有 $m$ 元钱，每个商品都要定价 $1$ 块或者 $2$ 块，在所有 $2^n$ 种定价方案中，按照性价比为第一关键字（大的在前）、原价（大的在前）为第二关键字、下标为第三关键字（小的在前）从大到小排序，然后贪心从前往后买，能买到的商品的 原价总和 与最优策略下能买到的商品原价总和相等的方案数。 输出答案对 $998244353$ 取模。

思路

观察一下数据范围，发现 $m$ 最多能到 $2n-1$。再一看，发现子任务16,18没有给下发文件，那肯定说明答案是个能一眼看出来的东西了。因此，从子任务16($m = 2n-1$) 出发，发现只有全定价为 $2$ 的时候不能买到所有商品，而且按照贪心策略剩下一个性价比最低的不买肯定是最优的，因此所有 $2^n$ 种方案都满足，性质 $A$ 那都所有商品价格一样了，贪心肯定就是最优的。

直接输出 $2^n$，获得 $8$ 分。

void so16(){
	ans = pw[n];
	printf("%lld\n",ans);
}

接下来看到子任务7~9,14,15都是m = 2的，最多才买两件商品，那就搞一下。 先把所有商品按原价从大到小排序（考虑到$/2$会有小数，所以干脆把所有商品价格$\times 2$，反正不影响）

①首先考虑贪心策略下只买一件（即定价为2的），那显然贪心策略下必定是买原价最高的那一件了（定价为2），那么贪心想是最优的话，后面就不能有两件定价为$1$的商品原价和超过最高的这个，那么我枚举第一个定价为 $1$ 的位置 $i$，第二件的可选位置是一段后缀，可以双指针维护一下，设第一个满足条件的位置为 $j$，答案就是 $2^{n - j + 1}$。 还有一种情况就是全部定价为2，这种情况肯定是满足的了。

    ans = 1;//quan 2
    ll pmx = p[1].w / 2;
    int j = n;
    rep(i,2,n){//2
        if(p[i].w > pmx) continue;
        ll res = pmx * 2 - p[i].w;
        while(j > 1 && p[j].w <= res) j--;
        int r = n - max(i + 1,j + 1) + 1;
        add(ans,pw[r]);
    }

②接下来考虑贪心策略下买了两件定价为 $1$ 的。首先如果原价最大的商品定价为1了，那肯定是满足的，方案数为 $2^{n-1}$，接下来考虑枚举第一个定价为 $1$ 的商品 $i$（注意，已经按原价排序了），这种情况下如果买两个 $1$ 不是最优的，那么一定是买原价最大的（定价为2的）那个，因此第二个定价为 $1$ 的商品原价得够大才行($a[i]+a[j]>a[1]$)，那么可选的 $j$ 就是 $[i+1,j]$ 的一段区间（这段区间里至少要有一个1），$j$ 后面的随便定价，双指针维护即可，答案是 $(2^{j-i}-1)\times 2^{n-j}$。需要注意还有一种情况，就是 $a[i] == a[1]$ 时，后面的商品可以随意定价，这个时候答案是 $2^{n-i}$。

add(ans,pw[n - 1]);//第一个是1
    j = n;
    rep(i,2,n){//1
        if(pmx >= p[i].w) break;
        ll res = pmx * 2 - p[i].w;
		if(res == 0){
			add(ans,pw[n - i]);
			continue;
		}
        while(j > 1 && p[j].w < res) j--;
        int r = j - i;
        if(r <= 0) break;
        add(ans,(pw[r] + mo - 1) % mo * pw[n - j] % mo);
    }

至此，可以获得 $28$ 分。

思考一会儿发现特殊性质 $B$ 好像不太好搞，那就看一下任务17的 $m=2n-2$。不难发现，如果有至少两件商品定价为 $1$ 那就能买下所有商品，全定价 $2$ 的话最后一件不买也没问题，那么问题就出在恰好一件商品定价为 $1$。不难发现，原价最低的商品定为 $1$ 的时候，可能不如不买它去买原价第二大的。那就是不合法的情况需要满足原价次小的商品的原价要严格大于原价最小的商品的原价，同时原价次小的商品原价/2后要小于原价最低的商品的原价，这样贪心策略才会去买原价小的。

至此，已经能够获得 $32$ 分。

void so17(){
	ans = pw[n];
	if(p[n - 1].w > p[n].w && p[n].w > p[n - 1].w / 2) add(ans,mo - 1);
	printf("%lld\n",ans);
}

接下来就考虑子任务1~5的 $n<=10$ 的情况了。直接暴力状压枚举每件商品的定价，然后分别按照贪心策略和01背包去求 $m$ 块钱能买到的最大原价是否相等。注意排序的时候按题目的优先级要求来。

这样，已经可以拿到 $52$ 分。

void so1(){
	ans = 0;
	int mm = (1 << n) - 1;
	rep(i,0,mm){
		rep(j,0,n - 1) if(i >> j & 1){
			p[j] = {a[j + 1],j,1};
		}else p[j] = {a[j + 1] / 2,j,2};
		sort(p,p + n,[&](node a,node b){
        	return a.w > b.w || (a.w == b.w && a.w * a.s > b.w * b.s) || (a.w == b.w && a.w * a.s == b.w * b.s && a.id < b.id);
    	});
		ll res = m,sum = 0;
		rep(j,0,n - 1) if(res >= p[j].s) {
			sum += p[j].w * p[j].s;
			res -= p[j].s;
		}
		rep(j,0,m) d[j] = 0;
		rep(j,0,n - 1){
			dep(k,m,p[j].s) d[k] = max(d[k],d[k - p[j].s] + p[j].w * p[j].s);
		}
		if(d[m] == sum) add(ans,1);
	}
	printf("%lld\n",ans);
}

到这其实这个题的部分分几乎已经拿满了，进一步，考虑 到底啥时候贪心策略才会达不到原价总和最大，这里就可以借助 $n<=10$ 的这块的下发文件测试了。我们不用01背包，考虑分类讨论。题目样例给的答案是 $6$，所有情况是 $8$ 种，有 $2$ 种不满足，一种样例解释给了，就是说 $121$ 的情况，也就是我买了两件定价 $1$ 的，但是不如不买这两件 $1$ 的而是去买两件中间一个定价为 $2$ 的。这只是一种，那还有一种就是 $12$，也就是最后剩了 $1$ 块钱，那么不如不买最后一个买的定价为 $1$ 的，而是买后面一个性价比低一点但是原价更高的定价为 $2$ 的。把这两种情况暴力讨论并替代01背包，发现下发样例的答案是完全对的。

void so1(){
	ans = 0;
	int mm = (1 << n) - 1;
	rep(i,0,mm){
		rep(j,0,n - 1) if(i >> j & 1){
			p[j] = {a[j + 1],j,1};
		}else p[j] = {a[j + 1] / 2,j,2};
		sort(p,p + n,[&](node a,node b){
        	return a.w > b.w || (a.w == b.w && a.w * a.s > b.w * b.s) || (a.w == b.w && a.w * a.s == b.w * b.s && a.id < b.id);
    	});
		rep(j,0,n) d[j] = 0;
		ll res = m,f = 1,num = 0,now = 0,now1 = 0;
		rep(j,0,n - 1) if(res >= p[j].s) {
			res -= p[j].s;
			d[j] = 1;
		}
		dep(j,n - 1,0) if(d[j] && p[j].s == 1){
			now += p[j].w;
			if(num == 0) now1 += p[j].w;
			num++;
			if(num == 2) break;
		}
		rep(j,0,n - 1) if(num == 2 && !d[j] && p[j].s == 2 && p[j].w * 2 > now){
			f = 0;
			break;
		}else if(num >= 1 && res && !d[j] && p[j].s == 2 && p[j].w * 2 > now1){
			f = 0;
			break;
		}
		add(ans,f);
	}
	printf("%lld\n",ans);
}

到此其实嘴角就开始压不住笑了，因为就这两种情况不满足，我们就可以用总的 $2^n$，去减去这两种不满足的情况。 那么就可以开始写正解了。

①$121$ 情况（买了至少两个1,钱花完了,但是不如买中间一个2） 枚举第一个买的 $1$ 是第 $i$ 件，再枚举中间这个 $2$ 是 $j$ （先假设 $j<i$），那么 $[1,j - 1]$ 都得买，但是定价可以是 $1/2$， $[j+1,i - 1]$ 这一段可买可不买，其中定价为 $1$ 的会被买走。那就是花 $m - 2$ 块钱，买 $[1,j-1]$ 的全部商品和 $[j+1,i-1]$ 的部分商品，那么可以假设 $[1,j-1]$ 的商品全部定价为 $1$，然后剩下的钱用来把$[1,j- 1]$ 的一些商品定价成 $2$ 或者买 $[j+1,i-1]$ 里定价为 $1$ 的商品。那后面的那个 1 满足条件的还是一段后缀（假设是 $[l,n]$），总方案数就是 $C(i-2,m-2-(j-1)) \times (2^{n-l+1}-1)$。

$j>i$ 的情况类似，再讨论一下。（？？？）

int l = 0;
	rep(i,1,n){
		l = i + 1;
		rep(j,1,i - 1)if(p[j].w / 2 < p[i].w){//j是i后面性价比最最高的2块钱的商品
			while(l <= n && 1LL * p[l].w + p[i].w >= p[j].w) l++;
			while(l <= n && p[l].w > p[j].w / 2) l++;
			if(m - 2 < j - 1) break;
			int res = m - 2 - (j - 1);
			int xs = 1LL * zuhe(i - 2,res) * (pw[n - l + 1] + mo - 1) % mo;
			add(ans,mo - xs);
		}
		l = i + 1;
		rep(j,i + 1,n){//j是i后面性价比最最高的2块钱的商品
			while(l <= n && 1LL * p[l].w + p[i].w >= p[j].w) l++;
			while(l <= n && p[l].w > p[j].w / 2) l++;
			if(m - 2 < (j - i - 1) * 2) break;
			int res = m - 2 - (j - i - 1) * 2;
			if(res < i - 1) break;
			res -= (i - 1);
			int xs = 1LL * zuhe(i - 1,res) * (pw[n - l + 1] + mo - 1) % mo;
			add(ans,mo - xs);
		}
	}

②$12$ 情况（买了至少一个1,剩1块钱,不如不买这个1去买后面一个2） 这种情况就简单了，枚举买的最后一个 $1$ 是商品 $i$，第一个没买的定价为 $2$ 的商品是 $j$ （显然 $j<i$，不然买 $i$ 原价更高了，现在考虑的是买 $j$ 更高但是你买了$i$），这种情况下 $j$ 性价比要不如 $i$ 但是原价得更高。和上面情况一样，$[1,j-1]$ 都得买，只是定价是 $1/2$ 的问题，而 $[j+1,i-1]$ 这一段还是只会买定价 $1$ 的。需要注意的是，这种情况下最终剩了 $1$ 块，那么 $[i+1,n]$ 的所有商品只能定价成 $2$。总方案数为 $C(i-2,m-2-(j-1))$。

	rep(i,1,n){
		rep(j,1,i - 1)if(p[j].w / 2 < p[i].w && p[j].w > p[i].w){
			if(m - 2 < j - 1) break;
			int res = m - 2 - (j - 1);
			if(res > i - 2) continue;
			int xs = zuhe(i - 2,res);
			add(ans,mo - xs);
		}
	}

至此，已经能获得 $92$ 到 $96$ 分。

最后两个点超时了，常数太大。 回顾 $121$ 的情况，发现 $j > i$ 其实是不可能的。因为中间的 $2$ 必须原价更高才会导致贪心策略取不到最大，即必须满足 $j<i$，所以这种情况实际上并不存在。

删掉这一部分，最终获得 $100$ 分。当然，中间我尝试从其他地方优化常数，当然是没有什么用啦。 AC代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fLL
#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)
#define dep(i,a,b) for(int i=(a),i##_end=(b);i>=i##_end;--i)
using namespace std;
template<class T>inline T mymin(T x,T y){return x<y?x:y;}
template<class T>inline T mymax(T x,T y){return x>y?x:y;}
template <typename T>
inline void read(T &X){
    X=0;int w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=X*10+(ch^48),ch=getchar();
    if(w) X=-X;
}
const int maxn = 5e3 + 5;
const int mo = 998244353;
int n,m,k,f;
int a[maxn],pw[maxn],d[maxn];
int ans,tmp,cnt,res,xs;
int jc[maxn],inv[maxn];
int power(int a,int n){
	int sum = 1;
	while(n){
		if(n & 1) sum = 1LL * sum * a % mo;
		a = 1LL * a * a % mo;
		n >>= 1;
	}
	return sum;
}
int zuhe(int n,int k){
	if(n < k) return 0;
	return 1LL * jc[n] * inv[k] % mo * inv[n - k] % mo;
}
void add(int &x,int y){
	x += y;
    if(x >= mo) x -= mo;
}
void solve(){
    read(n);read(m);
    rep(i,1,n){
        read(a[i]);
        a[i] *= 2;
    }
    sort(a + 1,a + 1 + n,[&](int a,int b){
        return a > b;
    });
    //其实就两种情况会买少
	//1.买了至少两个1,钱花完了,但是不如买中间一个2
	//2.买了至少一个1,剩1块钱,不如不买这个1去买个2
	ans = pw[n];
	int l = 2,r = 1;
	rep(i,1,n){
		l = i + 1;
		while(r <= n && a[r] / 2 >= a[i]) r++;
		rep(j,r,i - 1){//j是i后面性价比最最高的2块钱的商品
			if(m - 2 < j - 1) break;
			res = m - 2 - (j - 1);
			while(l <= n && 1LL * a[l] + a[i] >= a[j]) l++;
			xs = 1LL * zuhe(i - 2,res) * (pw[n - l + 1] + mo - 1) % mo;
			add(ans,mo - xs);
		}
	}
	// cout<<"debug1: "<<ans<<endl;
	//2.买了至少一个1,剩1块钱,不如不买这个1去买个2
	l = 1;
	r = 1;
	rep(i,1,n){
		while(l <= n && a[l] / 2 >= a[i]) l++;
		while(r <= n && a[r] > a[i]) r++;
		rep(j,l,r - 1){
			if(m - 2 < j - 1) break;
			res = m - 2 - (j - 1);
			xs = zuhe(i - 2,res);
			add(ans,mo - xs);
		}
	}
	printf("%d\n",ans);
}
int main(){
    pw[0] = 1;
    rep(i,1,maxn - 1) pw[i] = 1LL * pw[i - 1] * 2 % mo;
	jc[0] = 1;
	rep(i,1,maxn - 1) jc[i] = 1LL * jc[i - 1] * i % mo;
	inv[maxn - 1] = power(jc[maxn - 1],mo - 2);
	dep(i,maxn - 2,0) inv[i] = 1LL * inv[i + 1] * (i + 1) % mo;
    //cin.tie(0)->sync_with_stdio(false);
    int T=1;
    read(T);read(T);
    while(T--) solve();
    return 0;
}