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

相关文章：

• 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;
}

后续正在更新中。。。