相关文章：
试题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;
}
答案： 3725573267
试题C：质数
解析：
#include<iostream>
#include<math.h>
using namespace std;
//判断n是否是质数
bool isZS(int n)
{
for(int i=2; i<=sqrt(n); ++i)
{
if(n%i==0)
return true;
}
return false;
}
int main()
{
int j=0,count=0;
while(count<=2019)
{
if(isZS(j))
count++;
j++;
}
cout<<j<<endl;
return 0;
}
答案： 2373
试题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;
}
后续正在更新中。。。
转载：https://blog.csdn.net/wjinjie/article/details/115747848
查看评论