S+CSP2025模拟赛8

A. 输出字符串

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

#include
using namespace std;
int n,k;
vector 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>c;
		cout

`#include
using namespace std;
int n,k;
vector 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;i26;i++) sort(a[i].begin(),a[i].end());
	while(k--){
		char c;
		cin>>c;
		couta[c-'a'][pnt[c-'a']]
		pnt[c-'a']=(pnt[c-'a']+1)%a[c-'a'].size();
	}
	return 0;
}`

B. 最优排列翻转

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

#include
using namespace std;
const int N=5e5+5;
int n;
int p[N],sum[N];
vector > g[N*2];
int main(){
	freopen("reverse.in","r",stdin);
	freopen("reverse.out","w",stdout);
	cin>>n;
	for(int i=1;i>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

`#include
using namespace std;
const int N=5e5+5;
int n;
int p[N],sum[N];
vectorint,int> > g[N*2];
int main(){
	freopen("reverse.in","r",stdin);
	freopen("reverse.out","w",stdout);
	cin>>n;
	for(int i=1;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;i2;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
	return 0;
}`

C. 比赛

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

#include
#define int long long
#define pi1 pair
#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 g[N];
vector _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>n>>m>>q;
	for(int i=1,u,v;i>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1,x,k,v;i>x>>k>>v;
		_g[x].push_back({v,k});
	}
	dfs(1,0);
	while(q--){
		int x;
		cin>>x;
		cout

`#include
#define int long long
#define pi1 pair
#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];
vectorint> g[N];
vector _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
		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
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1,x,k,v;i
		cin>>x>>k>>v;
		_g[x].push_back({v,k});
	}
	dfs(1,0);
	while(q--){
		int x;
		cin>>x;
		coutans[x]"\n";
		}
	return 0;
}`