CSP-S复赛真题解析
2023年CSP-S复赛真题
密码锁
题意：
分析：
代码：
正解代码
#include<bits/stdc++.h>
using namespace std;
int n;
int va[10][10];
int vb[10];
int sum;
int check()
{
for(int i=1;i<=n;i++)
{
vector<int > v;
for(int j=1;j<=5;j++)
{
if(va[i][j]!=vb[j]) v.push_back(j);
}
if(v.size()==0) return false;
if(v.size()>=3) return false;
if(v.size()==1) continue;
if(v.size()==2)
{
if(v[1]-v[0]>=2) return false;
int sum1 = va[i][v[0]]-vb[v[0]];
int sum2 = va[i][v[1]]-vb[v[1]];
int ned1 = (sum1%10+10)%10;
int ned2 = (sum2%10+10)%10;
if(ned1!=ned2) return false;
}
}
return true;
}
void dfs(int now)
{
if(now>5)
{
if(check()) sum++;
return ;
}
for(int i=0;i<=9;i++)
{
vb[now] = i;
dfs(now+1);
}
}
int main()
{
//freopen()
//freopen()
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=5;j++)
{
cin>>va[i][j];
}
}
dfs(1);
cout<<sum;
}
消消乐
题意：
分析：
代码：
暴力解
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int solve(int l,int r)
{
stack<int > st;
for(int i=l;i<=r;i++)
{
if(st.size())
{
if(s[i]==st.top()) st.pop();
else st.push(s[i]);
}
else st.push(s[i]);
}
return (st.size()==0);
}
int main()
{
cin>>n>>s;
int sum = 0;
for(int i=0;i<s.size();i++)
{
for(int j=i;j<s.size();j++)
{
sum += solve(i,j);
}
}
cout<<sum;
}
结构体
题意：
分析：
代码：
种树
题意：
分析：
代码：
2022年CSP-S复赛真题
假期计划
题意：
分析：
代码：
暴力解
#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
const int N = 2510;
int n,m,k;
int va[N];
int dist[N][N];
vector<int > e[N];
void bfs(int A)
{
for(int i=1;i<=n;i++) dist[A][i] = 1e18;
queue<int > q;
q.push(A);
dist[A][A] = -1;
while(q.size())
{
int now = q.front();
q.pop();
if(dist[A][now]>=k) continue;
for(auto spot:e[now])
{
if(dist[A][spot]>dist[A][now]+1)
{
dist[A][spot] = dist[A][now]+1;
q.push(spot);
}
}
}
}
signed main()
{
cin>>n>>m>>k;
for(int i=2;i<=n;i++) cin>>va[i];
while(m--)
{
int a,b;
cin>>a>>b;
e[a].pb(b);
e[b].pb(a);
}
for(int i=1;i<=n;i++) bfs(i);
int maxn = 0;
for(int A=1;A<=n;A++)
{
for(int B=1;B<=n;B++)
{
for(int C=1;C<=n;C++)
{
for(int D=1;D<=n;D++)
{
set<int > s;
s.insert(A);s.insert(B);
s.insert(C);s.insert(D);
if(s.size()!=4||*s.begin()==1) continue;
if(dist[1][A]==1e18||dist[A][B]==1e18||dist[B][C]==1e18||dist[C][D]==1e18||dist[D][1]==1e18) continue;
maxn = max(maxn,va[A]+va[B]+va[C]+va[D]);
}
}
}
}
cout<<maxn;
return 0;
}
正解
#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define int long long
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 2510;
int n,m,k;
int va[N];
int vis[N][N];
int dist[N][N];
int maxn;
vector<int> e[N];
vector<int> v[N];
priority_queue<PII > q[N];
void bfs(int A)
{
for(int i=1;i<=n;i++) dist[A][i] = 1e18;
queue<int > q;
q.push(A);
vis[A][A] = 1;
dist[A][A] = -1;
while(q.size())
{
auto now = q.front();
q.pop();
if(dist[A][now]>=k) continue;
for(auto spot:e[now])
{
if(vis[A][spot]==0)
{
vis[A][spot] = 1;
dist[A][spot] = dist[A][now]+1;
q.push(spot);
}
}
}
}
void get(int B,int C)
{
for(auto A:v[B])
{
for(auto D:v[C])
{
if(A==B||A==C||A==D||B==C||B==D||C==D) continue;
maxn = max(maxn,va[A]+va[B]+va[C]+va[D]);
}
}
}
signed main()
{
IOS;
cin>>n>>m>>k;
for(int i=2;i<=n;i++) cin>>va[i];
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
e[a].push_back(b);
e[b].push_back(a);
}
for(int i=1;i<=n;i++) bfs(i);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==1||j==1||i==j) continue;
if(dist[i][j]!=1e18&&dist[1][j]!=1e18)
{
q[i].push({va[j],j});
}
}
}
for(int i=1;i<=n;i++)
{
while(q[i].size()&&v[i].size()<=3)
{
v[i].push_back(q[i].top().se);
q[i].pop();
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(dist[i][j]!=1e18) get(i,j);
}
}
cout<<maxn<<"\n";
return 0;
}
策略游戏
题意：
分析：
代码：
暴力解
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+10;
int n,m,q;
int va[N];
int vb[N];
signed main()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++) cin>>va[i];
for(int i=1;i<=m;i++) cin>>vb[i];
while(q--)
{
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
int maxn = -1e18;
for(int i=l1;i<=r1;i++)
{
int minn = 1e18;
for(int j=l2;j<=r2;j++)
{
minn = min(minn,va[i]*vb[j]);
}
maxn = max(maxn,minn);
}
cout<<maxn<<"\n";
}
return 0;
}
星战
题意：
分析：
代码：
数据传输
题意：
分析：
代码：
2021年CSP-S复赛真题
廊桥分配
题意：
分析：
代码：
暴力解
#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 1e5+10;
int n,m1,m2;
PII va[N],vb[N];
priority_queue<int,vector<int>,greater<int>> q1,q2;
int solve(int sum1,int sum2)
{
while(q1.size()) q1.pop();
while(q2.size()) q2.pop();
int ans = 0;
for(int i=1;i<=m1;i++)
{
while(q1.size()&&q1.top()<va[i].fi) q1.pop();
if(q1.size()<sum1)
{
ans++;
q1.push(va[i].se);
}
}
for(int i=1;i<=m2;i++)
{
while(q2.size()&&q2.top()<vb[i].fi) q2.pop();
if(q2.size()<sum2)
{
ans++;
q2.push(vb[i].se);
}
}
return ans;
}
signed main()
{
cin>>n>>m1>>m2;
for(int i=1;i<=m1;i++) cin>>va[i].fi>>va[i].se;
for(int i=1;i<=m2;i++) cin>>vb[i].fi>>vb[i].se;
sort(va+1,va+1+m1);
sort(vb+1,vb+1+m2);
int maxn = 0;
for(int i=0;i<=n;i++)
{
if(i*(m1+m2)>1e7) break;
maxn = max(maxn,solve(i,n-i));
}
cout<<maxn;
return 0;
}
正解
#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 1e6+10;
int n,m1,m2;
PII va[N],vb[N];
int cnt1[N],cnt2[N];
priority_queue<PII,vector<PII>,greater<PII>> q1,q2;
priority_queue<int,vector<int>,greater<int>> k1,k2;
void solve1()
{
for(int i=1;i<=n;i++) k1.push(i);
for(int i=1;i<=m1;i++)
{
while(q1.size()&&va[i].fi>=q1.top().fi)
{
k1.push(q1.top().se);
q1.pop();
}
if(k1.size())
{
cnt1[k1.top()]++;
q1.push({va[i].se,k1.top()});
k1.pop();
}
}
for(int i=1;i<=n;i++) cnt1[i] = cnt1[i]+cnt1[i-1];
}
void solve2()
{
for(int i=1;i<=n;i++) k2.push(i);
for(int i=1;i<=m2;i++)
{
while(q2.size()&&vb[i].fi>=q2.top().fi)
{
k2.push(q2.top().se);
q2.pop();
}
if(k2.size())
{
cnt2[k2.top()]++;
q2.push({vb[i].se,k2.top()});
k2.pop();
}
}
for(int i=1;i<=n;i++) cnt2[i] = cnt2[i]+cnt2[i-1];
}
signed main()
{
cin>>n>>m1>>m2;
for(int i=1;i<=m1;i++) cin>>va[i].fi>>va[i].se;
for(int i=1;i<=m2;i++) cin>>vb[i].fi>>vb[i].se;
sort(va+1,va+1+m1);
sort(vb+1,vb+1+m2);
solve1();solve2();
int anw = 0;
for(int i=0;i<=n;i++) anw = max(anw,cnt1[i]+cnt2[n-i]);
cout<<anw;
return 0;
}
括号序列
题意：
分析：
代码：
回文
题意：
分析：
代码：
交通规划
题意：
分析：
代码：
2020年CSP-S复赛真题
儒略日
题意：
分析：
代码：
动物园
题意：
分析：
代码：
正解
#include<bits/stdc++.h>
#define PII pair<int,int>
#define fi first
#define se second
#define int unsigned long long
using namespace std;
const int N = 1e6+10;
int n,m,c,k;
int va[N];
int lim[N];
int vis[N];
signed main()
{
cin>>n>>m>>c>>k;
for(int i=1;i<=n;i++) cin>>va[i];
while(m--)
{
int a,b;
cin>>a>>b;
lim[a] = b;
}
for(int j=0;j<=k-1;j++)
{
if(lim[j]==0) vis[j] = 1;
for(int i=1;i<=n;i++)
{
if((va[i]>>j)&1) vis[j] = 1;
}
}
int sum = 0;
for(int j=0;j<=k-1;j++) sum += (vis[j]==1);
if(sum==64&&n==0) cout<<"18446744073709551616";
else cout<<(1ull<<(sum-1))-n+(1ull<<(sum-1));
return 0;
}
函数调用
题意：
分析：
代码：
暴力解
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+10;
const int mod = 998244353;
int n,m,q;
int va[N];
vector<int > opt[N];
void solve(int id)
{
if(opt[id][0]==1)
{
int a = opt[id][1],b = opt[id][2];
va[a] = (va[a]+b)%mod;
}
if(opt[id][0]==2)
{
int x = opt[id][1];
for(int i=1;i<=n;i++) va[i] = va[i]*x%mod;
}
if(opt[id][0]==3)
{
for(int i=1;i<opt[id].size();i++)
{
int x = opt[id][i];
solve(x);
}
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>va[i];
cin>>m;
for(int id=1;id<=m;id++)
{
int op;
cin>>op;
opt[id].push_back(op);
if(op==1)
{
int a,b;
cin>>a>>b;
opt[id].push_back(a);
opt[id].push_back(b);
}
if(op==2)
{
int x;
cin>>x;
opt[id].push_back(x);
}
if(op==3)
{
int k;
cin>>k;
for(int i=1;i<=k;i++)
{
int x;
cin>>x;
opt[id].push_back(x);
}
}
}
cin>>q;
for(int i=1;i<=q;i++)
{
int x;
cin>>x;
solve(x);
}
for(int i=1;i<=n;i++) cout<<va[i]<<" ";
return 0;
}
贪吃蛇
题意：
分析：
代码：
2019年CSP-S复赛真题
格雷码
题意：
分析：
代码：
暴力解
#include<bits/stdc++.h>
using namespace std;
vector<string > v;
int main()
{
int n,k;
cin>>n>>k;
v.push_back("0");
v.push_back("1");
for(int i=1;i<=n-1;i++)
{
vector<string > vt;
for(int i=0;i<v.size();i++)
{
vt.push_back("0"+v[i]);
}
for(int i=v.size()-1;i>=0;i--)
{
vt.push_back("1"+v[i]);
}
v = vt;
}
cout<<v[k];
}
正解
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
signed main()
{
int n,k;
cin>>n>>k;
__int128 sum = (__int128)1<<n;
int pre = -1;
while(sum!=1)
{
if(pre==-1)
{
if(k<sum/2)
{
cout<<0;
pre = -1;
}
else
{
cout<<1;
k -= sum/2;
pre = 1;
}
}
else
{
if(k<sum/2)
{
cout<<1;
pre = -1;
}
else
{
cout<<0;
k -= sum/2;
pre = 1;
}
}
sum /= 2;
}
return 0;
}
括号树
题意：
分析：
代码：
暴力解
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n;
char va[N];
int sum[N];
vector<int > e[N];
int check(string s)
{
stack<char > st;
for(int i=0;i<s.size();i++)
{
if(s[i]=='(') st.push(s[i]);
else
{
if(st.size()==0) return 0;
if(st.top()==')') return 0;
st.pop();
}
}
if(st.size()==0) return 1;
return 0;
}
int get(string s)
{
int res = 0;
for(int l=0;l<s.size();l++)
{
for(int r=l;r<s.size();r++)
{
string t;
for(int i=l;i<=r;i++) t += s[i];
res += check(t);
}
}
return res;
}
void dfs(int now,string now_s)
{
now_s += va[now];
sum[now] = get(now_s);
for(auto spot:e[now])
{
dfs(spot,now_s);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>va[i];
for(int i=2;i<=n;i++)
{
int x;
cin>>x;
e[x].push_back(i);
}
dfs(1,"");
int anw = 0;
for(int i=1;i<=n;i++) anw ^= i*sum[i];
cout<<anw;
}
树上的数
题意：
分析：
代码：
Emiya 家今天的饭
题意：
分析：
代码：
划分
题意：
分析：
代码：
树的重心
题意：
分析：
代码：