CSP2025模拟赛6

2025年8月20日 ooliver OI

S+CSP2025模拟赛6

A. 劫富济贫

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

#include
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>1;
		if(checkl(mid)>1;
		if(checkr(mid)>n>>k;
	for(int i=1;i>a[i];
	sort(a+1,a+1+n);
	for(int i=1;i

`#include
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
		mid=l+r>>1;
		if(checkl(mid)1;
		else r=mid-1;
	}
	lmax=ans;
}
void findr(){
	int l=a[1],r=a[n],mid,ans=0;
	while(l
		mid=l+r>>1;
		if(checkr(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>a[i];
	sort(a+1,a+1+n);
	for(int i=1;iqz[i]=a[i]+qz[i-1];
	findl();
	findr();
	if(checkl(qz[n]/n)checkr((qz[n]+n-1)/n)
        coutqz[n]%n?1:0)
    }
	else coutmax(0ll,rmin-lmax);
	return 0;
}`

C++

B. 完美式子

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

#include
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>a[i];
	if(n==1){
		cout

`#include
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>a[i];
	if(n==1){
		couta[1]
		return 0;
	}
	memset(dp,-0x3f,sizeof dp);
	dp[2][0][0]=a[1]-a[2];
	for(int i=3;i
		for(int j=0;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
	return 0;
}`

C++

C. 线段

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

#include
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>a[i];
		int idx1=0,idx2=0;
		for(int j=1;j

`#include
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
		cin>>a[i];
		int idx1=0,idx2=0;
		for(int j=1;jif(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
	return 0;
}`

C++