第十届蓝桥杯大赛软件类省赛 C/C++ 大学 A 组题解
作者：KEY.L
- 2022 年 7 月 20 日
本文字数：3791 字
阅读完需：约 12 分钟
试题 A: 平方和
点击并拖拽以移动
编辑
思路：
暴力模拟跑一遍即可，答案是 2658417853
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){ long long cnt1=0,cnt2=0,cnt3=0; long long ans=0,i,j,t; for(i=1;i<=2019;i++) { j=i; int flag=0; while(j!=0) { if(j%10==0||j%10==1||j%10==2||j%10==9) { flag=1;break; } j/=10; } if(flag) { ans+=i*i; cout<<i<<endl; } } cout<<ans<<endl; return 0;}复制代码
点击并拖拽以移动
试题 B: 数列求值
点击并拖拽以移动
编辑
思路：
一个斐波那契数列的变种，因为项数很多而且求最后四位数组所以也不用想太多，答案是 4659
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long longint a[4];signed main(){ a[1]=1,a[2]=1,a[3]=1; int i,j,ans; for(i=4;i<=20190324;i++) { a[4]=(a[1]%10000+a[2]%10000+a[3]%10000)%10000; a[1]=a[2]%10000; a[2]=a[3]%10000; a[3]=a[4]%10000; } cout<<a[4]<<endl; return 0;}
复制代码
点击并拖拽以移动
试题 C: 最大降雨量
点击并拖拽以移动
编辑
思路：
其实不难想到 49 个法术每天都要用也就是七个星期，而七个星期每次都取中位数，那么贪心的每次都想取最大，所以模拟一下，第一周取最小的 1,2,3 然后取个最大的 49,48,47,46，再排序，取七次即可。最后答案 34
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){ vector<int >ans[7]; int min1=1,max1=49,ans1=0; int i,j; for(i=0;i<7;i++) { while(ans[i].size()!=7) { if(ans[i].size()<3){ ans[i].push_back(min1++); } else { ans[i].push_back(max1--); } } sort(ans[i].begin(),ans[i].end()); for(j=0;j<ans[i].size();j++) cout<<ans[i][j]<<" "; cout<<endl; ans1+=ans[i][3]; cout<<ans[i][3]<<endl; } cout<<ans1<<endl; return 0;}复制代码
点击并拖拽以移动
试题 D: 迷宫
点击并拖拽以移动
编辑
思路：
发现是从起点到终点的最短路，所以首选 bfs，然后要求路径，这里处理一下，把每个点是从哪个点过来的记录一下，然后输出的时候再从尾到头找回去，记得输出要翻转字符串。
代码：
#include<bits/stdc++.h>
using namespace std;
char mp[55][55];int dx[5]= {0,1,0,0,-1},dy[5]= {0,0,-1,1,0};bool vis[55][55];int pre[55*55+1000];int main(){ string ly; int n,m,i,j,t; pair<int,int >PI; cin>>n>>m; getchar(); for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { cin>>mp[i][j]; } } queue<pair<int,int >>qq; map<pair<int,int >,int >ans; map<pair<int,int >,pair<int,int >>edges; qq.push({1,1}); while(!qq.empty()) { pair<int,int > aa=qq.front(); qq.pop(); int x1=aa.first,y1=aa.second; if(x1==n&&y1==m) { cout<<ans[ {x1,y1}]<<endl; } for(i=1; i<=4; i++) { int x2=x1+dx[i],y2=y1+dy[i]; if(vis[x2][y2]==0&&mp[x2][y2]=='0'&&x2>=1&&x2<=n&&y1>=1&&y2<=m) { vis[x2][y2]=1; ans[ {x2,y2}]=ans[ {x1,y1}]+1; edges[ {x2,y2}].first=x1; edges[ {x2,y2}].second=y1; qq.push({x2,y2}); } } } int edx=n,edy=m; string ss=""; map<int ,char >qm; qm[1]='D',qm[2]='L',qm[3]='R',qm[4]='U'; while(1) { int x1=edges[ {edx,edy}].first; int y1=edges[ {edx,edy}].second; for(i=1;i<=4;i++) { if(x1+dx[i]==edx&&y1+dy[i]==edy) { ss+=qm[i]; break; } } edx=x1,edy=y1; if(edx==1&&edy==1){ break; } } reverse(ss.begin(),ss.end()); cout<<ss<<endl; return 0;}/*
4 6010000000100001001110000
30 50010101010010110010010101100101101001000010001010100000100010000010101001000010000000100110011010010101111011010010001000001101001011100011000000010000010000000010101000110100001010000010101010110010110001111100000010100001001010001010000010110000000011001000110101000010101100011010011010101011110111000110110101010010010010100000010001010011100000001010000010100010011010101011111001100001000011101000111000001010100001100010000001000101001100001001110001101000011100100010010101010101010100011010000001000010010000010100101010111010001010101000010111100100101001001000010000010101010100100100010100000000100000001010110011110100011000001010101000111010101001110000100001100001011001111011010000100010101010100001101010100101000010100000111011101001100000001011000100001011001011010010111000000001001010100100000001010010000100010000010001111010100100101001010101101001010100011010101101110000110101110010100001000011000000101001010000010001110000100000100011000011010110100000010010100100100001110110100101000101000000001110110010110101101010100001001010000100001101010100001000100010010001000101011010000100011001000100001010100101010101111101001000000100101000000110010100101001000001000000000010110100000010011101110010010000111010010110111010000000011010001000100010000000100001110100000011001110101000101000100010001111100010101001010000001000100000101001010010101100000001001010100010111010000011110000100001000000011011100000000100000000101110000001100111010111010001000110111010101101111000
186DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR*/复制代码
点击并拖拽以移动
试题 E: RSA 解密
点击并拖拽以移动
编辑
思路：
比赛的时候没看，暂时不会
试题 F: 完全二叉树的权值
点击并拖拽以移动
编辑思路：
模拟找节点找深度就行，比较简单
#include<bits/stdc++.h>
using namespace std;
#define int long longsigned main(){ int N,i,j; vector<int>ans[555]; cin>>N; int cnt=0,sum1=1; for(i=1;i<=N;i++) { cin>>j; if(i<=sum1) { ans[cnt].push_back(j); } else { ++cnt; sum1+=(1<<cnt); ans[cnt].push_back(j); } } int max1=0,anss; for(i=0;i<=cnt;i++) { int ss1=0; for(j=0;j<ans[i].size();j++) { ss1+=ans[i][j]; } if(ss1>max1) { max1=ss1; anss=i+1; } } cout<<anss<<endl; return 0;}复制代码
点击并拖拽以移动
试题 G: 外卖店优先级
点击并拖拽以移动
编辑
思路：
一个模拟贪心题，观察到时间不是很长，所以模拟时间跑就行，不过这里细节挺多的，要注意出队入队的条件，读题要读清楚。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+1000;struct node { int pret,levl; bool f1;}mo[maxn];struct node1 { int stt,idd;}qury[maxn];bool cmp1(node1 a,node1 b ){ if(a.stt!=b.stt) return a.stt<b.stt; else return a.idd<b.idd;}int main(){ int n,m,i,j,ts,id,t; cin>>n>>m>>t; for(i=0;i<m;i++) { cin>>qury[i].stt>>qury[i].idd; } sort(qury,qury+m,cmp1); for(i=0;i<m;i++) { ts=qury[i].stt,id=qury[i].idd; if(ts>mo[id-1].pret) mo[id-1].levl=max(mo[id-1].levl-(ts-mo[id-1].pret-1),0); if(mo[id-1].f1==1&&mo[id-1].levl<=3) mo[id-1].f1=0; mo[id-1].levl+=2; if(mo[id-1].f1==0&&mo[id-1].levl>5) mo[id-1].f1=1; mo[id-1].pret=ts; } int ans=0; for(i=0;i<maxn;i++) { mo[i].levl=max(0,mo[i].levl-(t-mo[i].pret)); if(mo[i].f1==0&&mo[i].levl>5) mo[i].f1=1; if(mo[i].f1==1&&mo[i].levl<=3) mo[i].f1=0; if(mo[i].f1==1) ans++; } cout<<ans<<endl; return 0;}复制代码
点击并拖拽以移动
试题 H: 修改数组
点击并拖拽以移动
编辑
思路：
真是没想到是并查集做法，待补
试题 I: 糖果
点击并拖拽以移动
编辑
思路：
不会，二分贪心跑了几分
试题 J: 组合数问题
点击并拖拽以移动
编辑 思路:
不会
划线
评论
复制
发布于: 刚刚阅读数: 4
KEY.L
关注
还未添加个人签名 2022.07.01 加入
还未添加个人简介
评论