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

太过爱你忘了你带给我的痛 2023-01-13 05:41 163阅读 0赞

### 文章目录 ###

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

--------------------

**相关文章：**

*  [2020年10月蓝桥杯（软件类）省赛：题目+解答][2020_10]
 *  [2020年3月蓝桥杯（软件类）第一次模拟赛：题目+解答][2020_3]
 *  [2020年4月蓝桥杯（软件类）第二次模拟赛：题目+解答][2020_4]

--------------------

## 试题A：立方和 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]  
**解析：**

#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：子串数字 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]  
**解析：**

#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：质数 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 2]  
**解析：**

#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: 最短路 ##

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

--------------------

## 试题E: RSA解密 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 4]  
**解析：**  
本题是填空题中最难的一道。本题涉及到很多数论的知识：质因子分解，扩展欧几里得算法，快速幂算法，利用快速乘算法求解快速幂（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 数列与黄金分割 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 5]  
**解析：**

#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: 扫地机器人 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 6]  
**解析：**

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

--------------------

***后续正在更新中*。。。**

[2020_10]: https://ai-wx.blog.csdn.net/article/details/109214863
[2020_3]: https://ai-wx.blog.csdn.net/article/details/109108840
[2020_4]: https://ai-wx.blog.csdn.net/article/details/109067927
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]: /images/20221022/7444f5a6340549d7b176871dcec615ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 1]: /images/20221022/ccda040f680346bc8de01055d2de60b1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 2]: /images/20221022/8da26f19c74a43619299393a339b2853.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 3]: /images/20221022/3a82c0dbb8bb435f934d817cc0e0f8a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 4]: /images/20221022/508494b994f54c3d9d09d6fc20061b65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 5]: /images/20221022/a2d302ebed7d4d8f8d9d1127624aaa2d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70 6]: /images/20221022/aeea916dd3e64847a3858af748a09b91.png