CSP2025模拟赛6

用户头像 发布于 2025-08-20 115 次阅读 OI

S+CSP2025模拟赛6

A. 劫富济贫

题意可以简化为在 $k$ 次操作后，
使最穷的人最富，最富的人最穷。
所以考虑二分答案两个端点，把找到的答案减一下就可以了。
注意当 $k$ 特别大是，差距可以来到 $1$ 以内，所以特判一下。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
int k,n,lmax,rmin;
int a[N],qz[N],hz[N];
int checkl(int x){
	int p=upper_bound(a+1,a+1+n,x)-a-1;
	return p*x-qz[p];
}
int checkr(int x){
	int p=lower_bound(a+1,a+1+n,x)-a;
	return (qz[n]-qz[p-1])-(n-p+1)*x;
}
void findl(){
	int l=a[1],r=a[n],mid,ans=0;
	while(l<=r){
		mid=l+r>>1;
		if(checkl(mid)<=k) ans=mid,l=mid+1;
		else r=mid-1;
	}
	lmax=ans;
}
void findr(){
	int l=a[1],r=a[n],mid,ans=0;
	while(l<=r){
		mid=l+r>>1;
		if(checkr(mid)<=k) ans=mid,r=mid-1;
		else l=mid+1;
	}
	rmin=ans;
}
signed main(){
	freopen("rich2poor.in","r",stdin);
	freopen("rich2poor.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++) qz[i]=a[i]+qz[i-1];
	findl();
	findr();
	if(checkl(qz[n]/n)<=k&&checkr((qz[n]+n-1)/n)<=k) {
        cout<<(qz[n]%n?1:0)<<endl;
    }
	else cout<<max(0ll,rmin-lmax);
	return 0;
}
C++

B. 完美式子

可以发现：$a-(b-(c-d)-e)=a-(b-c)-(d-e)$
也就是说括号嵌套其实等价于不嵌套。
那么就可以不考虑嵌套的情况。
剩下的就可以dp，
设 $dp_{i,j,0/1}$ 表示选到第 $i$ 个数字，有 $j$ 个括号，当前数字的正负为 $-(-1)^{0/1}$ 时的最大答案。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,M=25;
int n,m;
int a[N],dp[N][M][2],ans=INT_MIN;
signed main(){
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(n==1){
		cout<<a[1]<<endl;
		return 0;
	}
	memset(dp,-0x3f,sizeof dp);
	dp[2][0][0]=a[1]-a[2];
	for(int i=3;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(j) dp[i][j][1]=dp[i-1][j-1][0]+a[i];
			dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][1]+a[i]);
			dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1])-a[i];
			if(i==n) ans=max(ans,max(dp[i][j][0],dp[i][j][1]));
		}
	}
	cout<<ans;
	return 0;
}
C++

C. 线段

找到当先数之前相等的位置并标记下来，
找到左右端点的移动范围，
在反向循环统计答案。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e3+5;
int n,ans;
int a[N],l[N],r[N];
int dp[N];
signed main(){
	freopen("segment.in","r",stdin);
	freopen("segment.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		int idx1=0,idx2=0;
		for(int j=1;j<i;j++) if(a[i]==a[j]) r[idx1=j]=i;
		for(int j=idx1;j;j--){
			if(a[i]==a[j]) l[idx2=j]=i+1;
			else l[j]=min(l[j],idx2);
		}
		for(int j=i-1;j;j--){
			if(a[i]==a[j]) dp[j]=0;
			else if(!r[j]) dp[j]=dp[j+1]+i-j;
			else dp[j]=dp[l[j]]+(l[j]-j)*(i-r[j]);
			ans+=dp[j];
		}
	}
	cout<<ans;
	return 0;
}
C++