CSP-S复赛真题解析

🕗 发布于 2024-10-07 17:54 算法

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 家今天的饭

题意：

分析：

代码：

划分

题意：

分析：

代码：

树的重心

题意：

分析：

代码：

原文地址：https://blog.csdn.net/m0_52398496/article/details/142741151

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

初阶C语言-指针
用图理解如下：内存的最小单元是一字节，对每一字节去编号对应的就是指针（地址）。
阅读更多2024-10-07
Three.js基础内容(二)
这章介绍了three.js的模型属性和纹理贴图。
阅读更多2024-10-07
哪个牌子充电宝质量好又靠谱？年度四大热门款充电宝清单来了
大家其实可以发现，其实市面上充电宝价格都是参差不齐的，大家可以想象一下一款东西如果卖你十几二十块，可想而知这款产品的一个成本上是会有多低，并且在材料方面选用的肯定不是特别好的，廉价充电宝可能缺乏必要的
阅读更多2024-10-07
html超链接怎么去掉下划线
扩展资料：超级文本标记语言是标准通用标记语言下的一个应用，也是一种规范，一种标准，它通过标记符号来标记要显示的网页中的各个部分。浏览器按顺序阅读网页文件，然后根据标记符解释和显示其标记的内容，对书写出
阅读更多2024-10-07
18448 最小生成树
给定结点数为n，边数为m的带权无向连通图G，所有结点编号为1,2,3....n。求图G的最小生成树的边权和。输入格式第一行两个正整数n和m。n,m
阅读更多2024-10-07
【C++】入门基础介绍（下）输入输出，函数重载，缺省与引用
7. C++输入与输出8. 缺省参数9. 函数重载10. 引用10. 1 引用的概念10. 2 引用的特性10. 3 引用的使用10. 4 const引用10. 5 指针和引用的关系11. inlin
阅读更多2024-10-07
文件处理不再难:带你轻松攻克C语言文件操作
函数名功能适用范围fgetc字符输入函数所有输入流fputc字符输出函数所有输出流fgets文本行输入函数所有输入流fputs文本行输出函数所有输出流fscanf格式化输入函数所有输入流fprintf
阅读更多2024-10-07
用Python制作数据可视化仪表盘：使用Dash与Plotly构建实时交互式仪表盘
本文详细介绍了如何使用Python的Dash和Plotly库构建交互式数据可视化仪表盘，适用于实时数据展示和动态图表生成。首先，介绍了Dash的基本布局和使用Plotly生成图表的基础知识。随后，通过
阅读更多2024-10-07
CSP-S复习：图论题选讲
今天跟着南外复习的图论，十道题，感觉质量不错，就拿出来总结一下。
阅读更多2024-10-07
推理攻击-Python案例
通过这种方法，攻击者能够对训练数据集中的类别分布进行合理推测，尽管这一过程并不保证百分之百准确，但足以展示模型在某些方面可能泄漏的信息。这种类型的攻击强调了在设计和部署机器学习模型时，保护训练数据隐私
阅读更多2024-10-07