S+CSP2025模拟赛8
A. 输出字符串
模拟即可
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int n,k,cnt[35];
string s;
vector<string> st[35];
int toint(char c) {
return c-'a'+1;
}
signed main() {
Cios;
freopen("zigzag.in","r",stdin);
freopen("zigzag.out","w",stdout);
cin>>n>>k;
for (int i=1;i<=n;i++) {
cin>>s;
st[toint(s[0])].push_back(s);
}
for (int i=1;i<=26;i++) sort(st[i].begin(),st[i].end());
for (int i=1;i<=k;i++) {
char c;
cin>>c;
cout<<st[toint(c)][cnt[toint(c)]++]<<endl;
if (cnt[toint(c)]>=st[toint(c)].size()) cnt[toint(c)]=0;
}
return 0;
}B. 最优排列翻转
赛时写了一个 $O(n^3)$ 的暴力，拿了 30 分（
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=5e5+10;
int n,now=-1,w,p[N];
//k->i+j-k
signed main() {
Cios;
freopen("reverse.in","r",stdin);
freopen("reverse.out","w",stdout);
cin>>n;
for (int i=1;i<=n;i++) {
cin>>p[i];
w+=p[i]==i;
}
now=w;
for (int i=1;i<=n;i++) {
for (int j=i+1;j<=n;j++) {
int wh=w;
for (int k=i;k<=j;k++) {
wh-=p[k]==k;
wh+=p[k]==(i+j-k);
}
now=max(now,wh);
}
}
cout<<now-w<<endl;
return 0;
}C. 比赛
赛时写了一个不知道什么复杂度反正很高的暴力，然后5000都过不去……，没拿到分，但是也贴一下：
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=2e5+10;
int n,m,q,fa[N];
vector<int> g[N];
struct mapp {
int k,v;
};
vector<mapp> x[N];
void dfs(int u) {
for (int v:g[u]) {
if (v==fa[u]) continue;
fa[v]=u;
dfs(v);
}
}
int dff(int u,int k) {
int vl=INT_MAX;
if (u==1) return 0;
if (k) vl=dff(fa[u],k-1);
for (mapp mp:x[u]) {
vl=min(vl,dff(fa[u],k+mp.k-1)+mp.v);
}
return vl;
}
signed main() {
Cios;
freopen("match.in","r",stdin);
freopen("match.out","w",stdout);
cin>>n>>m>>q;
for (int i=1;i<n;i++) {
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
for (int i=1;i<=m;i++) {
int xi,k,v;
cin>>xi>>k>>v;
x[xi].push_back({k,v});
}
for (int i=1;i<=q;i++) {
int w;
cin>>w;
cout<<dff(w,0)<<endl;
}
return 0;
}
评论（0）
暂无评论