蓝桥杯考试题库及答案

蓝桥杯考试题库及答案一、填空题（每题10分，共50分）1.小明从1开始依次写整数1,答案1612解析按数位统计：个位出现202次，十位出现210次，百位出现200次，千位出现1000次，总计1612次。2.已知2023年1月1日是星期日，请问2023年12月31日是星期几？答案星期日解析2023年共有365天，365 3.求1!答案3解析1!+24.小蓝要爬上10级台阶，每次可以走1级或2级台阶。问他共有多少种不同的走法？答案89解析设f(n)(1)=1,\f(2)=2,\f(n)=f(n-1)+f(n-2)$。递推得$f(10)=89$。5.求1+答案1024144解析共有(2023+1二、程序设计题（每题20分，共100分）6.给定一个正整数n，求它的二进制表示中数字1的个数。输入格式：一个正整数n（1≤n≤109）。输出格式：一个整数，表示n#include<iostream>

usingnamespacestd;

intmain(){

intn;

cin>>n;

intcnt=0;

while(n){

cnt+=n&1;

n>>=1;

}

cout<<cnt<<endl;

return0;

}解析：用位运算逐位检查最低位，统计1的个数。也可以使用__builtin_popcount(n)。7.输入一个字符串（可能包含空格），判断它是否为回文串（忽略大小写和非字母数字字符）。如果是，输出YES，否则输出NO。输入格式：一行字符串，长度不超过1000。输出格式：YES或NO。样例输入：Aman,aplan,acanal:Panama样例输出：YES#include<iostream>

#include<string>

#include<cctype>

usingnamespacestd;

intmain(){

strings;

getline(cin,s);

stringt;

for(charc:s){

if(isalnum(c))t+=tolower(c);

}

intleft=0,right=t.size()-1;

boolok=true;

while(left<right){

if(t[left]!=t[right]){

ok=false;

break;

}

left++;

right--;

}

cout<<(ok?"YES":"NO")<<endl;

return0;

}解析：先过滤出字母和数字并转为小写，再用双指针判断回文。8.给定一个长度为n的整数序列，求其连续子序列和的最大值（子序列至少包含一个数）。输入格式：第一行一个整数n（1≤n≤105）；第二行n样例输入：9

-21-34-121-54样例输出：6答案：#include<iostream>

#include<vector>

usingnamespacestd;

intmain(){

intn;

cin>>n;

vector<int>a(n);

for(inti=0;i<n;i++)cin>>a[i];

longlongcur=0,best=a[0];

for(intx:a){

cur=max((longlong)x,cur+x);

best=max(best,cur);

}

cout<<best<<endl;

return0;

}解析：使用Kadane算法，动态维护以当前位置结尾的最大子段和。时间复杂度O(9.给定两个字符串s和t，判断t是否为s的子序列（不要求连续）。如果是，输出YES，否则输出NO。输入格式：第一行字符串s，第二行字符串t。字符串只包含小写字母，长度均不超过105。输出格式：YES或NO样例输入：abcde

ace样例输出：YES答案：#include<iostream>

#include<string>

usingnamespacestd;

intmain(){

strings,t;

cin>>s>>t;

inti=0,j=0;

while(i<s.size()&&j<t.size()){

if(s[i]==t[j])j++;

i++;

}

cout<<(j==t.size()?"YES":"NO")<<endl;

return0;

}解析：双指针贪心匹配，s中每个字符按顺序尝试匹配t中的当前字符，若t全部匹配则成功。10.给定一个m×n的网格，从左上角(1,1)走到右下角(m,n)，每次只能向右或向下移动一格。求不同路径的总数，结果对1000000007取模。样例输入：32样例输出：3答案：#include<iostream>

#include<vector>

usingnamespacestd;

constintMOD=1000000007;

intmain(){

intm,n;

cin>>m>>n;

vector<vector<longlong>>dp(m,vector<longlong>(n,0));

for(inti=0;i<m;i++)dp[i][0]=1;

for(intj=0;j<n;j++)dp[0][j]=1;

for(inti=1;i<m;i++){

for(intj=1;j<n;j++)