专栏文章

NOIP2025 T2 题解

220_200
P14636题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mimxu2xn
此快照首次捕获于
2025/12/01 17:19
3 个月前
此快照最后确认于
2025/12/01 17:19
3 个月前
查看原文
场上心态崩溃，无法 debug，被这题送退役了。
这种题，要计数，显然需要先会判定一个方案是否合法。而且一般合法条件非常强，不然没办法计数。以下讨论一个方案不合法的条件。
首先可以将 aa 数组降序排序。以下所有价格序列默认递减。
考虑把原序列 aa 拆成两个序列 A,BA,B，分别表示新定价为 22 和 11 的。为了减少特判，假定 AA 和 BB 后面都有无限多个 00，这样不会出现 mm 元钱用不完的情况。
容易证明，不管是性价比策略，还是实际最优策略，A,BA,B 中购买的都是一段前缀。
设 p,qp,q 分别是 A,BA,B 序列中购买的最后一个，则有 2p+q=m2p+q=m。
如果按照性价比排序的策略买，则应该满足 Ap+1<2Bq−1,Ap≥2Bq+1A_{p+1}\lt 2B_{q-1},A_p\ge 2B_{q+1}，即 p,qp,q 都不会因为下一个性价比更高而导致策略改变。
如果是原价最大的策略，那么应该是 f(p)=∑i=1pAi+∑i=1qBi,ans=f(p)min⁡f(p)=\sum_{i=1}^pA_i+\sum_{i=1}^qB_i,ans=f(p)_{\min}。
当 p′←p+1p'\gets p+1 时，q′←q−2q'\gets q-2，f(p′)←f(p)+Ap+1−Bq−Bq−1f(p')\gets f(p)+A_{p+1}-B_q-B_{q-1} 。由于 A,BA,B 都是递减的，g(p)=Ap+1−Bq−Bq−1g(p)=A_{p+1}-B_q-B_{q-1} 也递减，故 f(p)f(p) 取最大值等价于满足 g(p−1)≥0g(p-1)\ge 0 且 g(p)≤0g(p)\le 0。
所以，一种方案不合法，即按照性价比策略取不到最优解，等价于以下不等式：
Ap+1<2Bq−1A_{p+1}\lt 2B_{q-1} and Ap≥2Bq+1A_p\ge 2B_{q+1} and （Bq−1+Bq<Ap+1B_{q-1}+B_{q}\lt A_{p+1} or Ap<Bq+1+Bq+2A_p\lt B_{q+1}+B_{q+2}）
由于 A,BA,B 递减，所以 Ap>Ap+1,Bq−1>Bq>Bq+1>Bq+2A_p>A_{p+1},B_{q-1}>B_q>B_{q+1}>B_{q+2}。
如果该条件满足，则第二个不等式成立，那么第四个一定不成立，所以第三个不等式必须要成立。而如果第三个不等式成立，则第二个不等式也一定成立。
所以实际上只有第一个和第三个不等式是有用的，条件等价于 Bq−1+Bq<Ap+1<2Bq−1B_{q-1}+B_q\lt A_{p+1}\lt 2B_{q-1}
现在可以开始计数了，暴力枚举 Bq,Bq−1,Ap+1B_q,B_{q-1},A_{p+1} 在原序列 aa 中对应的下标 i,j,ki,j,k 以及 pp 的值，则 qq 可以直接确定，且 i>j>ki>j>k， ai+aj<ak<2aja_i+a_j<a_k<2a_j。方案数可以直接组合数，即为 (k−1p)(j−k−1q−2−(k−p−1))2n−i\binom{k-1}{p}\binom{j-k-1}{q-2-(k-p-1)}2^{n-i}。
代入 2p+q=m2p+q=m 化简一下，∑(k−1p)(j−k−1q−2−(k−p−1))=∑(k−1p)(j−k−1m−k−1−p)=(j−2m−k−1)\sum\binom{k-1}{p}\binom{j-k-1}{q-2-(k-p-1)}=\sum\binom{k-1}{p}\binom{j-k-1}{m-k-1-p}=\binom{j-2}{m-k-1}。 所以不需要枚举 pp。
而注意到 ii 的贡献只有 2n−i2^{n-i} 一项，且对于固定的 jj ，kk 对应的 ii 是一个单调递增的后缀，所以可以用双指针解决。
有一个重要的细节，ii 需要枚举到 n+1n+1，因为需要考虑 qq 取到 BB 后面补的 00 的情况。贡献系数应该为 2max⁡(n−i,0)2^{\max(n-i,0)}。
最后答案即为 2n2^n 减去不合法的方案数。
时间复杂度 O(n2)O(n^2)。
~去掉头文件和组合数预处理总共就十行，不知道场上在调什么鬼。~
代码CPP
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<ll,ll>
#define ve vector<ll>
#define fi first
#define se second
#define pb push_back
#define mid (l+r>>1)
#define lx (x<<1)
#define rx (x<<1|1)
using namespace std;
const ll N=5008,P=998244353;
ll T,n,m,ans,a[N],pw[N],c[N][N];
void init(){
	pw[0]=1;
	for(ll i=1;i<N;i++)pw[i]=pw[i-1]*2%P;
	for(ll i=0;i<N;i++)
		for(ll j=0;j<=i;j++)
			c[i][j]=(j?c[i-1][j]+c[i-1][j-1]:1)%P;
}
void slv(){
	cin>>n>>m,a[n+1]=ans=0;
	for(ll i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1,greater<ll>());
	for(ll j=2;j<=n;j++){
		ll p=j+1,s=0;
		for(ll i=j+1;i<=n+1;i++)
			(s+=pw[max(n-i,0ll)])%=P;
		for(ll k=max(m-j,0ll)+1;k<min(j,m);k++)
			if(a[k]<2*a[j]){
				while(p<=n+1&&a[p]>=a[k]-a[j])
					(s-=pw[max(n-p,0ll)])%=P,p++;
				(ans+=c[j-2][m-k-1]*s)%=P;
			}
	}
	cout<<(pw[n]-ans+P)%P<<'\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T>>T,init();
	while(T--)slv();
	return 0;
}

评论

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

正在加载评论...