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

A	B	C	D	Sum	Rank
100	60	15	-	175	8/22

A. 開掛

首先我們希望總步數(shù)最小，排序后掃一次使每個(gè)數(shù)成為大于它的最小的數(shù)即可。

然后根據(jù)排序不等式，我們希望修改操作盡可能的集中，倒著掃即可。此時(shí)需要確定比這個(gè)數(shù)大的最小的數(shù)，我使用了線段樹。動(dòng)態(tài)開點(diǎn)會(huì)被卡空間，提前離散化一下即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ull unsigned ll
#define lid id<<1
#define rid id<<1|1
#define lwrb lower_bound
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5,inf=2e9;
int n,a[maxn],b[maxn],c[maxn],d[maxn],cnt,tr[maxn<<2];
il void build(int id,int l,int r){
	tr[id]=l;
	if(l==r){
		return ;
	}
	int mid=(l+r)>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
}
il void upd(int id,int l,int r,int p){
	if(l==r){
		tr[id]=inf;
		return ;
	}
	int mid=(l+r)>>1;
	if(p<=mid){
		upd(lid,l,mid,p);
	}else{
		upd(rid,mid+1,r,p);
	}
	tr[id]=min(tr[lid],tr[rid]);
}
il int query(int id,int L,int R,int l,int r){
	if(L>=l&&R<=r){
		return tr[id];
	}
	int mid=(L+R)>>1,res=inf;
	if(l<=mid){
		res=min(res,query(lid,L,mid,l,r));
	}
	if(r>mid){
		res=min(res,query(rid,mid+1,R,l,r));
	}
	return res;
}
namespace cplx{
	bool end;
	il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
//	cout<<cplx::usdmem();
//	freopen("sample_openhook6.in","r",stdin);
	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++){
		cin>>b[i];
	}
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++){
		d[i]=a[i];
		if(d[i-1]>=d[i]){
			d[i]=d[i-1]+1;
		}
	}
	build(1,1,n);
	for(int i=n;i;i--){
		int t=query(1,1,n,lwrb(d+1,d+n+1,a[i])-d,n);
//		cout<<t<<'\n';
		c[++cnt]=d[t]-a[i];
		upd(1,1,n,t);
	}
	sort(c+1,c+cnt+1);
	ull ans=0;
	for(int i=cnt,j=1;i;i--,j++){
		ans+=c[i]*1llu*b[j];
	}
	cout<<ans;
	return 0;
}
}
int main(){return asbt::main();}

B. 叁仟柒佰萬

首先可以暴力 DP，枚舉 \(\operatorname{mex}\)，設(shè) \(f_i\) 表示以 \(i\) 為結(jié)尾的方案數(shù)。然后可以發(fā)現(xiàn)有貢獻(xiàn)的 \(\operatorname{mex}\) 只有全局 \(\operatorname{mex}\)。證明如下：

設(shè)全局 \(\operatorname{mex}\) 為 \(k\)。若最終的 \(\operatorname{mex}=x\)，分類討論：

\(x<k\)，由于全局 \(\operatorname{mex}\) 為 \(k\)，則必然有一個(gè)區(qū)間中有 \(x\)，即該區(qū)間的 \(\operatorname{mex}\ne x\)，矛盾。

\(x>k\)，由于全局 \(\operatorname{mex}\) 為 \(k\)，則序列中沒有 \(k\)，此情況不可能。

故最終的 \(\operatorname{mex}\) 只能為 \(k\)。

于是就不用枚舉 \(\operatorname{mex}\) 了。轉(zhuǎn)移式長(zhǎng)這樣：

\[f_i=\sum_{j=0}^{p}f_j \]

其中滿足 \(\operatorname{mex}[p+1,i]=k\) 且 \(\operatorname{mex}[p,i]\ne k\)。顯然 \(p\) 關(guān)于 \(i\) 是不降的，雙指針即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=4e7+5,mod=1e9+7;
il int pls(int x,int y){
	return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){
	x=pls(x,y);
}
il int mns(int x,int y){
	return x<y?x-y+mod:x-y;
}
il void sub(int &x,int y){
	x=mns(x,y);
}
int T,n,a[maxn],f[maxn],vis[maxn];
il void input(){
	int x,y;
	cin>>x>>y;
	for(int i=2;i<=n;i++){
		a[i]=(a[i-1]*1ll*x+y+i)&262143;
	}
}
il int mex(){
	int t=0;
	for(int i=1;i<=n;i++){
		vis[a[i]]=1;
		while(vis[t]){
			t++;
		}
	}
	for(int i=0;i<=n;i++){
		vis[i]=0;
	}
	return t;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		if(n<=3e5){
			for(int i=1;i<=n;i++){
				cin>>a[i];
			}
		}else{
			input();
		}
		int k=mex();
//		cout<<k<<'\n';
		f[0]=1;
		int p=1,cnt=0;
		for(int i=1;i<=n;i++){
			vis[a[i]]++;
			if(cnt<k&&a[i]<k&&vis[a[i]]==1){
				cnt++;
			}
			int t=0;
			if(cnt==k){
				while(p<i&&(a[p]>=k||vis[a[p]]>1)){
					vis[a[p++]]--;
				}
				t=f[p-1];
//				cout<<i<<' '<<p<<'\n';
			}
			f[i]=pls(f[i-1],t);
		}
		cout<<mns(f[n],f[n-1])<<'\n';
		for(int i=0;i<=n;i++){
			f[i]=vis[i]=0;
		}
	}
	return 0;
}
}
int main(){return asbt::main();}

C. 超級(jí)加倍

考慮建出 kruskal 重構(gòu)樹 T1 和 T2，于是題目要求變?yōu)?\(x\) 在 T1 上是 \(y\) 的祖先并且 \(y\) 在T2 上是 \(x\) 的祖先。在 T1 上跑出 dfn 后在 T2 上二維偏序即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=2e6+5;
int n,fa[maxn],dfn[maxn],cnt,sz[maxn];
ll ans;
struct edge{
	int u,v,w;
	il bool operator<(const edge &x)const{
		return w<x.w;
	}
}e[maxn];
struct{
	#define lowbit(x) (x&-x)
	int tr[maxn];
	il void add(int p,int v){
		for(;p<=n;p+=lowbit(p)){
			tr[p]+=v;
		}
	}
	il int query(int p){
		int res=0;
		for(;p;p-=lowbit(p)){
			res+=tr[p];
		}
		return res;
	}
	#undef lowbit
}F;
struct{
	vector<int> e[maxn];
	il void dfs1(int u){
		sz[u]=1,dfn[u]=++cnt;
		for(int v:e[u]){
			dfs1(v);
			sz[u]+=sz[v];
		}
	}
	il void dfs2(int u){
		ans+=F.query(dfn[u]+sz[u]-1)-F.query(dfn[u]-1);
		F.add(dfn[u],1);
		for(int v:e[u]){
			dfs2(v);
		}
		F.add(dfn[u],-1);
	}
}T1,T2;
il int find(int x){
	return x!=fa[x]?fa[x]=find(fa[x]):x;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1,j;i<=n;i++){
		cin>>j;
		if(j){
			e[i-1]={min(i,j),max(i,j),max(i,j)};
		}
		fa[i]=i;
	}
	sort(e+1,e+n);
	for(int i=1;i<n;i++){
		int u=e[i].u,v=e[i].v;
		T1.e[v].pb(find(u));
		fa[find(u)]=find(v);
		e[i].w=-u;
	}
	T1.dfs1(find(1));
	sort(e+1,e+n);
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<n;i++){
		int u=e[i].u,v=e[i].v;
		T2.e[u].pb(find(v));
		fa[find(v)]=find(u);
	}
	T2.dfs2(find(1));
	cout<<ans;
	return 0;
}
}
int main(){return asbt::main();}

D. 虛樹

原

posted @ 2025-10-03 19:21 zhangxy__hp 閱讀(22) 評(píng)論(0) 收藏舉報(bào)

刷新頁面返回頂部

zhangxyhp

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

A. 開掛

B. 叁仟柒佰萬

C. 超級(jí)加倍

D. 虛樹