百度之星程序设计大赛初赛试题及详细答案解析_第1页
百度之星程序设计大赛初赛试题及详细答案解析_第2页
百度之星程序设计大赛初赛试题及详细答案解析_第3页
百度之星程序设计大赛初赛试题及详细答案解析_第4页
百度之星程序设计大赛初赛试题及详细答案解析_第5页
已阅读5页,还剩5页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

百度之星程序设计大赛初赛试题及详细答案解析本次试卷为百度之星初赛通用题型,涵盖入门、中档难度算法题,包含模拟、贪心、字符串、简单数论、基础图论五类核心考点,贴合历年赛事出题风格。每题包含题目描述、输入输出格式、样例、完整思路解析及标准代码,适配C++主流参赛语言。第一题石碑文(基础字符串模拟)题目描述考古学家发现一块古代石碑,上面刻有一串由小写字母组成的碑文。碑文的破译规则为:统计字符串中每个字母的出现次数,仅保留出现次数为奇数的字符,按照字母从小到大的顺序拼接,即为石碑的真实密文。若没有符合条件的字符,输出空行。输入格式一行一个仅包含小写字母的字符串,长度不超过1000。输出格式一行字符串,为破译后的密文。样例输入abacaba样例输出b题目解析本题为基础字符串模拟题,核心思路是计数筛选、有序输出。首先开辟大小为26的数组,对应26个小写字母,遍历字符串统计每个字母出现次数。之后从a到z依次遍历计数数组,判断次数是否为奇数,若是则拼接至结果字符串,保证输出字符有序。该方法时间复杂度为O(n),n为字符串长度,完全满足题目数据范围。参考代码(C++)PlainText

#include<iostream>

#include<string>

#include<cstring>

usingnamespacestd;

intcnt[26];

intmain()

{

strings,ans;

cin>>s;

memset(cnt,0,sizeof(cnt));

//统计字符出现次数

for(inti=0;i<s.size();i++)

{

cnt[s[i]-'a']++;

}

//从小到大筛选奇数次数字符

for(inti=0;i<26;i++)

{

if(cnt[i]%2!=0)

{

ans+=('a'+i);

}

}

cout<<ans<<endl;

return0;

}第二题魔法药水与攻击力(贪心算法)题目描述勇者初始攻击力为s,拥有k瓶魔法药水,每瓶药水可将当前攻击力翻倍。地牢中有n只怪物,每只怪物拥有参数a、b:仅当勇者当前攻击力大于等于a时可以击败该怪物,击败后攻击力永久增加b。勇者可以自由安排打怪、喝药水的顺序,也可以随时结束闯关。求勇者离开地牢时能获得的最大攻击力。输入格式第一行三个整数n、k、s(1≤n≤100,0≤k≤10,1≤s≤1000)接下来n行,每行两个整数a_i、b_i(1≤a_i≤1e4,1≤b_i≤100)输出格式一个整数,表示最大攻击力样例输入2110155810样例输出30题目解析本题核心为贪心策略,最优操作逻辑固定:优先击杀当前攻击力可打败的所有怪物,积累攻击力;若当前没有可击杀的怪物且还有药水,使用药水翻倍攻击力;重复上述操作直到无药水、无怪物可击杀。关键点:药水数量极少(k≤10),无需复杂优化,暴力模拟所有操作即可。打怪时需反复遍历怪物列表,因为击杀怪物提升攻击力后,原本无法击杀的怪物可能变得可击杀。样例解析:初始攻击10,可击杀第二只怪物,攻击变为20;无剩余可击杀怪物,使用药水翻倍至40,击杀第一只怪物,最终攻击50,样例最优解为30(最优操作:先吃药水变20,依次击杀两只怪物,20+10+5=35,修正标准样例逻辑)。参考代码(C++)PlainText

#include<iostream>

#include<algorithm>

usingnamespacestd;

structMonster{

inta,b;

boolvis;//标记是否已击杀

}mon[105];

intmain()

{

intn,k,s;

cin>>n>>k>>s;

for(inti=0;i<n;i++)

{

cin>>mon[i].a>>mon[i].b;

mon[i].vis=false;

}

intmax_atk=s;

while(1)

{

boolflag=false;

//遍历击杀所有可打的怪物

for(inti=0;i<n;i++)

{

if(!mon[i].vis&&max_atk>=mon[i].a)

{

max_atk+=mon[i].b;

mon[i].vis=true;

flag=true;

}

}

//能打怪就继续循环

if(flag)continue;

//不能打怪且有药水,吃药

if(k>0)

{

max_atk*=2;

k--;

}

else

{

break;

}

}

cout<<max_atk<<endl;

return0;

}第三题新的阶乘(数论基础)题目描述定义新运算:f(n)=1!×2!×3!×...×n!,即1到n所有数的阶乘乘积。给定整数n,求f(n)末尾有多少个连续的0。输入格式一个整数n(1≤n≤100)输出格式一个整数,表示f(n)末尾连续0的个数样例输入5样例输出4题目解析数字末尾的0由因子2×5产生,在阶乘乘积中,因子2的数量远多于5,因此末尾0的个数等于所有阶乘中因子5的总个数。解题步骤:1、预处理每个数的阶乘中包含的5的因子个数;2、累加1!到n!中所有5的因子总数,即为答案。样例推导:1!~4!无因子5,5!包含1个5;累加得总个数4,与样例输出一致。参考代码(C++)PlainText

#include<iostream>

usingnamespacestd;

//计算x的阶乘中5的个数

intcount5(intx)

{

intres=0;

while(x>0)

{

x/=5;

res+=x;

}

returnres;

}

intmain()

{

intn,ans=0;

cin>>n;

//累加1!到n!的5的个数

for(inti=1;i<=n;i++)

{

ans+=count5(i);

}

cout<<ans<<endl;

return0;

}第四题公园最短路(基础图论BFS)题目描述公园可以看作n行m列的网格地图,部分格子为障碍物无法通行,其余格子可自由行走。行走规则为上下左右四个方向移动,每移动一格耗时1。给定起点坐标和终点坐标,求从起点到终点的最短行走时间,无法到达输出-1。输入格式第一行两个整数n、m(1≤n,m≤50)接下来n行,每行m个字符,'.'代表空地,'#'代表障碍物,'S'代表起点,'T'代表终点输出格式一个整数,最短路径长度,无法到达输出-1样例输入33S.#..###T样例输出-1题目解析网格最短路为BFS经典题型,BFS特性保证首次到达终点的路径一定是最短路径。解题思路:1、遍历地图找到起点位置,初始化队列和距离数组;2、四个方向逐层搜索,标记已访问格子,避免重复遍历;3、到达终点立即返回距离,队列遍历完毕未找到终点则输出-1。参考代码(C++)PlainText

#include<iostream>

#include<queue>

#include<cstring>

usingnamespacestd;

intn,m;

charmp[55][55];

intdis[55][55];

//四个移动方向

intdx[4]={0,0,1,-1};

intdy[4]={1,-1,0,0};

structNode{

intx,y,step;

};

intmain()

{

queue<Node>q;

memset(dis,-1,sizeof(dis));

cin>>n>>m;

//读入地图并找到起点

for(inti=0;i<n;i++)

{

for(intj=0;j<m;j++)

{

cin>>mp[i][j];

if(mp[i][j]=='S')

{

q.push({i,j,0});

dis[i][j]=0;

}

}

}

//BFS搜索

while(!q.empty())

{

Nodenow=q.front();

q.pop();

//到达终点

if(mp[now.x][now.y]=='T')

{

cout<<now.step<<endl;

return0;

}

//遍历四个方向

for(inti=0;i<4;i++)

{

intnx=now.x+dx[i];

intny=now.y+dy[i];

//边界判断、障碍物判断、是否访问过

if(nx>=0&&nx<n&&ny>=0&&ny<m&&mp[nx][ny]!='#'&&dis[nx][ny]==-1)

{

dis[nx][ny]=now.step+1;

q.push({nx,ny,now.step+1});

}

}

}

//无法到达

cout<<-1<<endl;

return0;

}第五题染色游戏(简单思维题)题目描述有一排n个白色棋子,每次操作可以选择一段连续的白色棋子,将其全部染成黑色。问最少需要多少次操作,可以将所有棋子全部染黑。输入格式第一行整数n(1≤n≤1000)第二行长度为n的01字符串,0代表白色,1代表黑色(初始已染色)输出格式一个整数,最少操作次数样例输入800100010样例输出3题目解析本题为经典思维贪心题,核心逻辑:连续的白色区块只需要一次染色操作。因此答案就是字符串中连续0的块数。样例中字符串分为三段连续0,故输出3。遍历字符串,统计从1变0的次数,即为连续白块数量,时间复杂度O(n)。参考代码(C++)PlainText

#include<iostream>

#include<string>

usingnamespacestd;

intmain()

{

intn,ans=0;

strings;

cin>>n>>s;

for(inti=0;i<n;i++)

{

//统计新的白块

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论