CSP2025模拟赛8

用户头像 发布于 2025-08-23 124 次阅读 OI

S+CSP2025模拟赛8

A. 输出字符串

按照题意模拟即可。
（不要用数组，要用vector，用数组直接MLE）
代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<string> a[30];
int pnt[30];
int main(){
	freopen("zigzag.in","r",stdin);
	freopen("zigzag.out","w",stdout);
	cin>>n>>k;
	while(n--){
		string x;
		cin>>x;
		a[x[0]-'a'].push_back(x);
	}
	for(int i=0;i<26;i++) sort(a[i].begin(),a[i].end());
	while(k--){
		char c;
		cin>>c;
		cout<<a[c-'a'][pnt[c-'a']]<<endl;
		pnt[c-'a']=(pnt[c-'a']+1)%a[c-'a'].size();
	}
	return 0;
}

B. 最优排列翻转

从每一个可行的反转中心开始枚举，
可以将 $p_i=i$ 的点预处理下来并前缀和，
就可以优化。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n;
int p[N],sum[N];
vector<pair<int,int> > g[N*2];
int main(){
	freopen("reverse.in","r",stdin);
	freopen("reverse.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i];
		sum[i]=sum[i-1]+(p[i]==i);
		g[p[i]+i].push_back({min(i,p[i]),max(p[i],i)});
	}
	int ans=0;
	for(int i=2;i<=n*2;i++){
		if(g[i].empty()) continue;
		sort(g[i].begin(),g[i].end());
		reverse(g[i].begin(),g[i].end());
		int cnt=0;
		for(auto pr:g[i]){
			cnt++;
			ans=max(ans,cnt-(sum[pr.second]-sum[pr.first-1]));
		}
	}
	cout<<ans;
	return 0;
}

C. 比赛

倍增，
访问时在倍增数组上往上跳，
同时取路径上的最小值。
代码：

#include<bits/stdc++.h>
#define int long long
#define pi1 pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2e5+7,M=21;
int n,m,q;
int fa[N][M],dp[N][M],ans[N],dep[N];
vector<int> g[N];
vector<pi1> _g[N];
int calc(int u,int h){
	int res=1e18;
	for(int i=0;h;i++,h>>=1){
		if(h&1){
			res=min(res,dp[u][i]);
			u=fa[u][i];
		}
	}
	return res;
}
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	fa[u][0]=f;
	dp[u][0]=ans[f];
	for(int i=1;i<M;i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
		dp[u][i]=min(dp[u][i-1],dp[fa[u][i-1]][i-1]);
	}
	for(auto e:_g[u]) ans[u]=min(ans[u],calc(u,e.se)+e.fi);
	for(auto v:g[u]){
		if(v==f)
		continue;
		dfs(v,u);
	}
}
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(dp,0x3f,sizeof(dp));
	memset(ans,0x3f,sizeof(ans));
	ans[0]=ans[1]=0;
	cin>>n>>m>>q;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1,x,k,v;i<=m;i++){
		cin>>x>>k>>v;
		_g[x].push_back({v,k});
	}
	dfs(1,0);
	while(q--){
		int x;
		cin>>x;
		cout<<ans[x]<<"\n";
		}
	return 0;
}