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， 设 dp_{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++
CSP2025模拟赛6
笔记