藍橋杯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;
}

后續正在更新中，，，