专栏文章

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

xxxsevenWishBloom
P14636题解参与者 34已保存评论 52

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
17 条
当前快照
1 份
快照标识符
@mimyd6n7
此快照首次捕获于
2025/12/01 17:34
3 个月前
此快照最后确认于
2025/12/01 17:34
3 个月前
查看原文
看到好多人说难写难调，我的做法实现貌似很简单啊！
考虑什么情况会算错。
如果性价比最高的是 wi=2w_i =2 的物品，选了一定不会出错，因为不选它也没有更好的能选。
但如果选了 wi=1w_i=1 的物品，可能会在后面没钱选一个 wi=2w_i=2 的物品，只能再选择一个 wi=1w_i=1 但是很弱的物品，导致两件加起来没有那件贵的强。
也就是说，记 wi=1w_i=1 的两件物品为 x,zx,z，wi=2w_i=2 的物品为 yy，我们会把最优方案 …y\dots y 选成 …x…(y)z\dots x \dots (y)z，其中最后一个省略号的物品全部有 wi=2w_i=2。
我们称上述错误中第一件 wi=1w_i=1 的物品是特殊物品，wi=2w_i=2 的物品为正确物品。
尝试直接对这个结构进行计数。首先把所有 aa 排序。
然后，枚举特殊物品 xx 和正确物品 yy。正确物品的价值比特殊物品要高，但性价比更低，因此要保证 ax<ay<2×axa_x \lt a_y \lt 2\times a_x 。
对于性价比大于 yy 的物品，我们一定会选择。
  • 对于原价已经大于 aya_y 的物品，无论价格总会被选，会消耗 11 或 22 元。这样的物品有 n−yn-y 个。
  • 对于原价在 axa_x 和 aya_y 之间的物品，w=1w=1 时性价比优于 yy 会被选，会消耗 00 或 11 元。这样的物品有 y−x−1y-x-1 个。
  • 对于原价在 ay2\frac{a_y}{2} 和 axa_x 之间的物品，由之前错解的形态可知一定不会被选，只能 w=2w=2 并消耗 00 元。
以上三种情况涵盖了 xx 以外性价比大于 yy 的所有情况，可知之后我们只有 11 元钱了，它会用来选择 zz。
也就是说，上述所有物品中我们会花掉 m−2m-2 元钱。先扣掉 1/21/2 元中的 11 元，变成在 n−x−1n-x-1 个物品中选 m−2−(n−y)m-2-(n-y) 个花掉 11 元。组合数可以 O(1)O(1) 计算。
对于原价小于 axa_x 的部分，我们只需要让 ap+ax≥aya_p + a_x \ge a_y 的部分都不成为 zz 即 w=2w=2，剩余的随便选即可。
相当于找到最大的 pp 满足 ap+ax<aya_p+a_x \lt a_y，前面的方案数即为 2p2^p。pp 显然可以在枚举 yy 时使用双指针求出。
时间复杂度 O(n2)O(n^2)，代码非常好写。
CPP
#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;
}
希望这篇题解能够帮到你！

评论

共 52 条评论，欢迎与作者交流。

正在加载评论...