第十三届蓝桥杯真题题解(A~D题)
试题A:九进制转十进制 试题B:顺子日期试题C:刷题统计试题D:修剪灌木。2022年蓝桥杯省赛真题
试题A:九进制转十进制
本题总分:5分
【问题描述】
九进制正整数(2022),转换成十进制等于多少?
知识点详解:
1.X进制转十进制规则:各个位数按权展开,若存在小数部分也同理。
例:2024.5三进制转为十进制--4*3^0+2*3^1+2*3^3+5*3^(-1)=64.33333...
2.十进制转X进制:整数部分用短除法(自底向上取余),小数部分采用"乘X取整,顺序排列"法(自顶向下)。
例:10.25十进制转为二进制-- 1010.01
(1).将整数部分10十进制转换为二进制:1010= 10102
(2).将小数部分0.25十进制转换为二进制:将0.25乘以2,得到0.5,整数部分为0将0.5乘以2,得到1.0,整数部分为1,小数部分是0在乘下去没有意义。因此,0.25十进制转换为二进制为O.01。3.X1转X2进制:以十进制作为媒介中转 X1->10->X2
十六进制对应4位二进制,八进制对应3位,十进制对应2位。
【小技巧】
- 像特殊的进制也可用计算器求解
#include <iostream>
using namespace std;
int main() {
cout << 2 + 2 * 9 + 2 * 9 * 9 * 9;
return 0;
}
试题B:顺子日期
本题总分:5分
【问题描述】
小明特别喜欢顺子。顺子指的就是连续的三个数字:123、456等。顺子日期指的就是在日期的 yyyymmdd表示法中,存在任意连续的三位数是一个顺子的日期。例如20220123就是一个顺子日期,因为它出现了一个顺子:123;而20221023则不是一个顺子日期,它一个顺子也没有。小明想知道在整个2022年份中,一共有多少个顺子日期。
题解:枚举日期拼成字符串,用查询顺子串
【小技巧】
- 可以使用excel表拉取数据再结合查找(CTRL+F)功能,查询012和123一共的个数。
- 在验证自己写的代码后,要学会使用缩小数据范围,选择自己知道的区间测试代码的正确性。
【注】:如果使用devC++编译器记得开允许c++11 ,否则会不识别to_string函数
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s1="012",s2="123";//顺子串
int cnt=0;
//枚举法:枚举每个月
for(int i=1;i<=12;i++)
{
//枚举每一天
for(int j=1;j<=31;j++)
{
string s="2022";
if(i<10)
s+="0"+to_string(i);//将数据类型转为字符串的函数
else
s+=to_string(i);
if(j<10)
s+="0"+to_string(j);
else
s+=to_string(j);
//查询子串
if(s.find(s1)!=-1||s.find(s2)!=-1)
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}
试题C:刷题统计
时间限制: 1.0s内存限制: 256.0MB本题总分:10
【问题描述】
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做α道题目,周六和周日每天做b道题目。请你帮小明计算,按照计划他将在第几天实现做题数大于等于n题?
(一)暴力法
模拟每一天取得部分分数(枚举每一天,做题目数量的累加和)--时间复杂度O(n)
#include<iostream>
#include<string>
using namespace std;
int main()
{
int a,b,n;
cin>>a>>b>>n;
int sum=0;
//枚举
for(int i=1;;i++)
{
if(i%7==0||i%7==6)//周末
sum+=b;
else
sum+=a;
if(sum>=n)
{
cout<<i<<endl;
return 0;
}
}
return 0;
}
(二)数学优化版
每周7天的固定刷题量t=5a+2b,所以只需要查看总题量n里面有多少个t,然后再对余数进行处理即可,因为剩下的余数一定是7天内完成的,时间复杂度O(1)
#include <iostream>
using namespace std;
#define int long long
signed main()
{
int a,b,n;
cin>>a>>b>>n;
int t=5*a+2*b;//每一周可以完成的题目数量
//如果整周就可以完成
if(n%t==0)
cout<<n/t*7;
else
{
int d=n/t;//可以整周完成的周数
int m=n%t;//整周完成不了一周内的天数
int sum=0;
for(int i=1;i<=7;i++)
{
if(i>5)
sum+=b;
else
sum+=a;
while(sum>=m)
{
cout<<d*7+i<<endl;
return 0;
}
}
}
return 0;
}
试题D:修剪灌木
时间限制: 1.0s内存限制: 256.0MB本题总分:10分
【问题描述】
爱丽丝要完成一项修剪灌木的工作。有N棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木,让灌木的高度变为0厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始,每天向右修剪一棵灌木。当修剪了最右侧的灌木后,她会调转方向,下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。
灌木每天从早上到傍晚会长高1厘米,而其余时间不会长高。在第一天的早晨,所有灌木的高度都是0厘米。爱丽丝想知道每棵灌木最高长到多高。
(一)模拟法(不考虑清晨傍晚关系)--时间复杂度O(n)
0 0 0 (竖着一列接着一列模拟)
0 1 1 3 2 0 0 2 3
1 0 2 4 0 1 1 0 4
2 1 0 0 1 2 ...
通过模拟3棵树和4棵树后发现规律,调转方向三次后就可以找到最大值。
为了记录每棵树高度的变化开个数组h,记录当前最大高度hmx
#include <iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int>h(n+1),hmx(n+1) ;
//模拟从左往右剪树
for(int i=1;i<=n;i++)
{
for(int j =1 ; j <= n ; j ++)
{
h[j]++;
h[i]=0;
hmx[j]=max(hmx[j],h[j]);
}
}
//调转方向模拟从右往左剪树
for(int i=n;i>=1;i--)
{
for(int j =1 ; j <= n ; j ++)
{
h[j]++;
h[i]=0;
hmx[j]=max(hmx[j],h[j]);
}
}
//再次调转方向模拟从左往右剪树
for(int i=1;i<=n;i++)
{
for(int j =1 ; j <= n ; j ++)
{
h[j]++;
h[i]=0;
hmx[j]=max(hmx[j],h[j]);
}
}
for(int i=1;i<=n;i++)
cout<<hmx[i]<<endl;
return 0;
}
(二)数学优化--时间复杂度O(n)
在模拟法的基础上观察一下规律对于点i(只要I不走i都在+1),结合调转方向,那么1~i-1之间的点和i+1~n之间的点都会遍历两次,所以当前点i的最大增长高度为max(2*(i-1),2*(n-i))
#include <iostream>
using namespace std;
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i++)
cout << max(i - 1, n - i)*2 << endl;
return 0;
}
如果你对探索机器学习的无限可能性、掌握Python编程的技巧、以及玩转各种框架的技能充满了好奇心,那么恭喜你,你来对地方了!赶紧扫描下方二维码,加入我们的微信公众号吧!这里有最新的技术趋势、独家教程、精彩案例等着你,让我们一起探索未知的领域,开启编程之旅吧!🚀🌟
更多推荐
所有评论(0)