【比賽記錄】2025CSP-S模擬賽26

A	B	C	D	Sum	Rank
60	-	-	20	80	16/24

A. 集合

首先發現固定左端點 \(l\)，好的子區間的右端點是從 \(l\) 開始的一段連續的位置。這是因為一個好的區間，其子區間必然也是好的。于是雙指針，用權值線段樹維護連續段即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int n,m,a[maxn],cnt[maxn];
struct seg{
	int len,sum,ls,rs,lc,rc;
	seg(int len=0,int sum=0,int ls=0,int rs=0,int lc=0,int rc=0)
		:len(len),sum(sum),ls(ls),rs(rs),lc(lc),rc(rc){}
	il seg operator+(const seg &x)const{
		seg res;
		res.lc=lc,res.rc=x.rc;
		res.ls=ls,res.rs=x.rs;
		res.len=len+x.len;
		res.sum=max(sum,x.sum);
		if(rc+1==x.lc){
			res.sum=max(res.sum,rs+x.ls);
			if(ls==len){
				res.ls=len+x.ls;
			}
			if(x.rs==x.len){
				res.rs=x.len+rs;
			}
		}
		return res;
	}
}tr[maxn<<2];
il void pushup(int id){
	tr[id]=tr[lid]+tr[rid];
}
il void upd(int id,int l,int r,int p,seg v){
	if(l==r){
		tr[id]=v;
		return ;
	}
	int mid=(l+r)>>1;
	if(p<=mid){
		upd(lid,l,mid,p,v);
	}
	else{
		upd(rid,mid+1,r,p,v);
	}
	pushup(id);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	ll ans=0;
	for(int l=1,r=1;r<=n;r++){
		if(cnt[a[r]]++==0){
			upd(1,1,n,a[r],seg(1,1,1,1,a[r],a[r]));
		}
		while(tr[1].sum>m){
			if(--cnt[a[l]]==0){
				upd(1,1,n,a[l],seg());
			}
			l++;
		}
		ans+=r-l+1;
	}
	cout<<ans;
	return 0;
}
}
int main(){return asbt::main();}

B. 差后隊列

首先考慮 pop 操作，從前往后掃，維護當前時刻除了最大值之外的和的期望，設當前有 \(cnt\) 個數，則 \(ans_i=\frac{sum}{cnt}\)。

然后考慮 push 操作，倒過來掃，每個數在它可以被刪去的位置計算答案。因為除了最大值之外的其它數都是等價的，所以直接維護答案即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e6+5,mod=998244353;
int n,inv[maxn],ans[maxn],L[maxn],R[maxn],tot,hp[maxn],b[maxn];
struct node{
	int opt,x;
}a[maxn];
il void solve(int l,int r){
	for(int i=l,cnt=0,sum=0,mxx=0;i<=r;i++){
		if(a[i].opt){
			if(cnt--==1){
				ans[i]=mxx;
			}
			else{
				ans[i]=sum*1ll*inv[cnt]%mod;
				sum=sum*1ll*(1+mod-inv[cnt])%mod;
			}
		}
		else{
			cnt++;
			if(a[i].x<mxx){
				(sum+=a[i].x)%=mod;
			}
			else{
				(sum+=mxx)%=mod,mxx=a[i].x;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	inv[1]=1;
	for(int i=2;i<=n;i++){
		inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
	}
	for(int i=1,cnt=0,j=1,lst=0;i<=n;i++){
		cin>>a[i].opt;
		if(a[i].opt){
			if(--cnt==0){
				L[++tot]=j,R[tot]=i,j=i+1;
				ans[lst]=i,lst=0;
			}
		}
		else{
			cin>>a[i].x;
			cnt++;
			if(!lst){
				lst=i;
			}
			else if(a[i].x>a[lst].x){
				b[i]=lst,lst=i;
			}
			else{
				b[i]=i;
			}
		}
		hp[i]=cnt;
	}
//	for(int i=1;i<=n;i++){
//		cout<<hp[i]<<" ";
//	}
//	cout<<"\n";
	if(R[tot]!=n){
		tot++;
		L[tot]=R[tot-1]+1,R[tot]=n;
	}
	for(int i=1;i<=tot;i++){
		solve(L[i],R[i]);
	}
	for(int i=n,res=0;i;i--){
		if(a[i].opt){
			if(hp[i]){
				res=(res*1ll*(1+mod-inv[hp[i]])+i*1ll*inv[hp[i]])%mod;
			}
		}
		else{
			ans[b[i]]=res;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}
}
int main(){return asbt::main();}

C. 蛋糕

設 \(dp_{l,r,p}\) 表示區間 \([l,r]\)，只考慮第 \(p\) 層以上的最小權值。記 \(f_{l,r}\) 表示 \([l,r]\) 最小值的下標，\(g_{l,r}\) 表示最大值。

考慮轉移，可以證明只有以下兩種轉移：

\(dp_{l,r,p}\leftarrow dp_{l,f_{l,r}-1,a_{f_{l,r}}}+dp_{f_{l,r}+1,r,a_{f_{l,r}}}+\frac{(2\times a_{g_{l,r}}-a_{f_{l,r}}+1-p)\times(a_{f_{l,r}}-p)}{2}\)
\(dp_{l,r,p}\leftarrow dp_{l,g_{l,r}-1,p}+dp_{g_{l,r}+1,r,p}+a_{g_{l,r}}-p\)

然后還可以證明，有效狀態只有 \(n^2\) 個。哈希表 + 記搜即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e3+5,HM=1e7+19;
const ll inf=1e18;
int n,f[maxn][maxn],g[maxn][maxn],cnt,hd[HM+5];
ll a[maxn];
struct{
	int nxt;
	ll key,val;
}e[4500005];
il void encode(ll key,ll val){
	int t=key%HM;
	e[++cnt].nxt=hd[t];
	e[cnt].key=key,e[cnt].val=val;
	hd[t]=cnt;
}
il ll decode(ll key){
	for(int i=hd[key%HM];i;i=e[i].nxt){
		if(e[i].key==key){
			return e[i].val;
		}
	}
	return -1;
}
il ll hash(int l,int r,ll p){
	return ((l*4000ll+r)<<32)+p;
}
il ll dfs(int l,int r,ll p){
	if(l>r){
		return 0;
	}
	ll tmp=decode(hash(l,r,p));
	if(~tmp){
		return tmp;
	}
	ll res=min(dfs(l,f[l][r]-1,a[f[l][r]])+dfs(f[l][r]+1,r,a[f[l][r]])+(2*a[g[l][r]]-a[f[l][r]]+1-p)*(a[f[l][r]]-p)/2,dfs(l,g[l][r]-1,p)+dfs(g[l][r]+1,r,p)+a[g[l][r]]-p);
	encode(hash(l,r,p),res);
	return res;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		f[i][i]=g[i][i]=i;
		for(int j=i+1;j<=n;j++){
			if(a[f[i][j-1]]<=a[j]){
				f[i][j]=f[i][j-1];
			}
			else{
				f[i][j]=j;
			}
			if(a[g[i][j-1]]>=a[j]){
				g[i][j]=g[i][j-1];
			}
			else{
				g[i][j]=j;
			}
		}
	}
//	for(int l=1;l<=n;l++)for(int r=l;r<=n;r++){
//		cout<<f[l][r]<<" "<<g[l][r]<<"\n";
//	}
	cout<<dfs(1,n,0);
	return 0;
}
}
int main(){return asbt::main();}

D. 字符替換

posted @ 2025-07-25 21:36 zhangxy__hp 閱讀(74) 評論(0) 收藏舉報

刷新頁面返回頂部

zhangxyhp

【比賽記錄】2025CSP-S模擬賽26

A. 集合

B. 差后隊列

C. 蛋糕

D. 字符替換