后台-插件-广告管理-内容页广告位一(手机)

您现在的位置是:首页 > 编程语言 > 其他编程其他编程

蓝桥杯2019年软件类省赛:真题+解答

2021-04-18 18:45:36其他编程人已围观

简介




文章目录
试题A:立方和试题B:子串数字试题C:质数试题D: 最短路试题E: RSA

文章目录

    • 试题A:立方和
    • 试题B:子串数字
    • 试题C:质数
    • 试题D: 最短路
    • 试题E: RSA解密
    • 试题F: Fibonacci 数列与黄金分割
    • 试题G: 扫地机器人


相关文章:

  • 2020年10月蓝桥杯(软件类)省赛:题目+解答
  • 2020年3月蓝桥杯(软件类)第一次模拟赛:题目+解答
  • 2020年4月蓝桥杯(软件类)第二次模拟赛:题目+解答

试题A:立方和

在这里插入图片描述
解析:

#include<iostream>
#include<sstream>
#include<math.h>
using namespace std;

string int_str(int a)
{
	string out;
	stringstream Convert;
	Convert<<a;
	Convert>>out;
	return out;
}

int main()
{
	int a=0;
	cin>>a;
	long long sum=0;
	for(int i=1; i<=a; ++i)
	{
		string str = int_str(i);
		if(str.find('2',0)!=string::npos||str.find('0',0)!=string::npos||str.find('1',0)!=string::npos||str.find('9',0)!=string::npos)
		sum += pow(i,3);	
	}
	cout<<sum<<endl;
	return 0;
} 

答案: 4097482414389


试题B:子串数字

在这里插入图片描述
解析:

#include<iostream>
#include<math.h>
using namespace std;

int main()
{
	long long sum=0;
	int num=0;
	string s;
	cin>>s;
	for(int i=0; i<s.size(); ++i)
	{
		num = s[s.size()-1-i]-'A'+1;
		sum += num*pow(26, i);
	}
	cout<<sum<<endl;
	return 0;
}

答案: 3725573269


试题C:质数

在这里插入图片描述
解析:

#include<iostream>
#include<math.h>
using namespace std;

//判断n是否是质数,n>=1
bool isZS(int n)
{
	if(n==1||n==2||n==3)
		return true;
	else
	{
		for(int i=2; i<=sqrt(n); ++i)
		{
			if(n%i==0)
				return false;
		}
		return true;
	}
}

int main()
{
	int j=2,count=0;
	while(count<2019)
	{
		if(isZS(j))
			count++; //计数 
		j++;
	}
	cout<<j-1<<endl; //因为在while中最后是加1的,所以输出j-1 
	return 0;
}

答案: 17569

试题D: 最短路

在这里插入图片描述
解析: 本题是填空题,可直接看出答案为6,最佳路径:S-J-B-A或者S-M-L-H-D-A。


试题E: RSA解密

在这里插入图片描述
解析:
本题是填空题中最难的一道。本题涉及到很多数论的知识:质因子分解,扩展欧几里得算法,快速幂算法,利用快速乘算法求解快速幂(mod太大导致不能直接乘,而是需要使用加法来替代乘法)。另外还需要注意扩展欧几里得算法求解出来的乘法逆可能是负数,所以需要使用公式进行转换。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<fstream>

using namespace std;
typedef long long LL;
/*
首先生成两个质数p, q,令n = p * q,设d 与(p -1)*(q -1) 互质,则可
找到e 使得d * e 除(p-1)*(q -1) 的余数为1。
现在你知道公钥中n = 1001733993063167141, d = 212353,同时你截获了别人发送的密文C = 20190324,请问,原文是多少?
当收到密文C 时,可使用私钥解开,计算公式为X = C^e mod n。答案:579706994112328949 
*/
/*
p=891234941 q=1123984201
*/
//扩展欧几里得算法 
void exgcd(LL a,LL b,LL&d,LL& x,LL& y){//d=gcd(a,b)
	if(!b){
		d=a;
		x=1;
		y=0;
	}else{
		exgcd(b,a%b,d,y,x);
		y-=x*(a/b);
	}
}
//快速乘
LL quickMul(LL a,LL b,LL mod){
	LL ans=0;//这里初值为0 
	while(b){
		if(b&1)
			ans=(ans+a)%mod;
		a=(a+a)%mod;
		b>>=1;
	}
	return ans%mod;
} 
LL quickPower(LL a,LL b,LL mod){
	LL ans=1;//注意这里初值是1 
	while(b){
		if(b&1)
			ans=quickMul(ans,a,mod)%mod;
		a=quickMul(a,a,mod)%mod;
		b>>=1;
	}
	return ans%mod;
}
int main(){
	LL n=1001733993063167141;
	//分解质因数 
	for(LL i=2;i*i<=n;i++){
		while(n%i==0){
			//cout<<i<<" "<<n/i<<endl;//两个质数 
			n/=i;
		}
	}
	LL p=891234941,q=1123984201;
	LL mod=(p-1)*(q-1);
	LL d=212353;
	LL e,y,gcd;
	//d*e==1(%mod)
	//扩展欧几里得算法 
	exgcd(d,mod,gcd,e,y);
	e=(e%mod+mod)%mod;//这里是因为e可能为负数 
	//cout<<e<<endl;
	LL c=20190324;
	n=1001733993063167141;
	//X = C^e mod n
	LL x;
	//快速幂和快速乘相结合 
	cout<<quickPower(c,e,n)<<endl;
	return 0;
}

试题F: Fibonacci 数列与黄金分割

在这里插入图片描述
解析:

#include<iostream>
#include<iomanip>
using namespace std;

//Fibonacci 数列 
double f(double n)
{
	if(n==1)
		return 1;
	else if(n==2)
		return 1;
	else
		return f(n-1)+f(n-2);
}

int main()
{
	int a=0;
	cin>>a;
	double output = f(a)/f(a+1);
	//小数点后保留8位数字 
	cout<<setprecision(8)<<fixed<<output<<endl;
	return 0;
}

试题G: 扫地机器人

在这里插入图片描述
解析:

#include<iostream>
#include<algorithm>
using namespace std;
int N,K;
int a[100]; //K个机器人位置
int b[100]; //标记N个方格中是否有机器人 
int check1(int first_L,int L){ //第一个区间长度为first_L,之后区间长度都为L 
	int i,j;
	if(first_L+(K-1)*L<N){
		return 0;
	}
	i=1; //第i个区间 
	j=1; //当前查看的方格位置 
	while(j<=N){
		if(b[j]==1){ //第i个区间内有机器人 
			j=first_L+(i-1)*L+1; //j指向下一个区间起点 
			i++; //下一个区间 
		}else{
			j++;
			if(j==first_L+(i-1)*L+1||j==N+1){ //第i个区间内没有机器人
				return 0; 
			}
		}		
	} 
	return 1;
} 
int check(int L){
	int first_L; //首区间的长度(取值范围:1~L) 
	for(first_L=L;first_L>0;first_L--){
		if(check1(first_L,L)){
			return 1;
		}
	}
	return 0;
}
int fun(){
	int i,j,L;
	for(L=N/K;L<=N;L++){ 
		if(check(L)){
			return L;
		}
	}
} 
int main(){
	int i,L;
	cin>>N>>K;
	for(i=1;i<=K;i++){
		cin>>a[i];
		b[a[i]]=1; //标记a[i]位置有机器人 
	}
	sort(a+1,a+K+1);
	L=fun();
	cout<<2*(L-1);
	return 0;
}

后续正在更新中。。。

文章来源:查看

Tags:算法   数据结构   蓝桥杯  

很赞哦! ()

后台-插件-广告管理-内容页广告位二(手机)
后台-插件-广告管理-内容页广告位三(手机)

随机图文

后台-插件-广告管理-内容页广告位四(手机)

文章评论

留言与评论(共有 0 条评论)
   
验证码:

本栏推荐

站点信息

  • 文章统计13614篇文章
  • 浏览统计468次浏览
  • 评论统计1个评论
  • 标签管理标签云
  • 统计数据:统计代码
  • 微信公众号:扫描二维码,关注我们