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; }`
CSP2025模拟赛8
笔记