2023年全国青少年信息素养大赛C++算法创意实践挑战赛(小学组-复赛)真题2(含答案)

2023年全国青少年信息素养大赛C++算法创意实践挑战赛(小学组_复赛)真题2(含答案)一、编程题。1.修复机器人的对话词库错误。题目描述：基于人工智能技术的智能陪伴机器人的语言词库被黑客的病毒感染了，感染方式是在单词中的某个字母被增加了两次，例如“hello”变成了“heeello”。空格字符被替换为长度不固定的数字乱码，请修复它。输入格式：输入一行字符串(字符串中无空格)。这一行是被感染的字符串。输出格式：输出一行对应的正确字符串。样例输入：Good24565morrrning样例输出：Goodmorning参考程序：#include<iostream>#include<string>#include<cctype>usingnamespacestd;stringrepair_string(conststring&s){stringresult;intn=s.length();inti=0;while(i<n){//如果是数字，全部跳过，只加一个空格。if(isdigit(s[i])){while(i<n&&isdigit(s[i])){i++;}result+='';}else{//如果是字母，处理连续三个相同字母。if(i+2<n&&s[i]==s[i+1]&&s[i]==s[i+2]){result+=s[i];i+=3;}else{result+=s[i];i+=1;}}}returnresult;}intmain(){stringinfected;cin>>infected;stringrepaired=repair_string(infected);cout<<repaired<<endl;return0;}2.定制架子问题。题目描述：李莳花要做一个架子，把她喜欢的摆件叠放起来，她的每个摆件的位置顺序是固定的。这个架子的宽度是W，每层排放的摆件不能超过这个宽度，每层架子的高度不能低于最高的摆件的高度。假设，给出排列好的每个摆件的宽度Wi，和高度Hi，请计算需要最少多高的架子。输入格式：输入的第一行有2个数字，一个是摆件的个数n，和架子的宽度W。以下摆件个数n行，每行的第一个数是摆件的宽度Wi和高度Hi。输出格式：输出放置摆件架子的最低高度。样例输入：552112132322样例输出：5参考程序：#include<iostream>#include<vector>#include<climits>#include<algorithm>//必须加，用于max和min。usingnamespacestd;intmain(){intn,W;cin>>n>>W;//items[i]存储：第i个摆件的宽度、高度。vector<pair<int,int>>items(n);for(inti=0;i<n;++i){cin>>items[i].first>>items[i].second;}//dp[i]=放好前i个摆件需要的最小总高度。vector<int>dp(n+1,INT_MAX);dp[0]=0;//0个摆件高度为0。for(inti=1;i<=n;++i){inttotal_width=0;intmax_height=0;//从第i个摆件往前看，尝试把[j…i]放在同一层。for(intj=i;j>0;--j){total_width+=items[j-1].first;//宽度超过架子宽度，不能再放。if(total_width>W)break;//记录这一层最高摆件高度。max_height=max(max_height,items[j-1].second);//动态规划转移：前j-1个的最小高度+当前层高度。dp[i]=min(dp[i],dp[j-1]+max_height);}}//答案就是放完所有n个摆件的最小高度。cout<<dp[n]<<endl;return0;}3.输出多进制数。题目描述：输入一个小于20的正整数n，要求按从小到大的顺序输出所有的n位m进制数，每个数占一行。输入格式：输入一个小于20的正整数n，和一个小于10的正整数m。输出格式：按从小到大的顺序输出所有的n位m进制数，每个数占一行。样例输入：32样例输出：000001010011100101110111参考程序：#include<iostream>#include<vector>#include<string>usingnamespacestd;//递归函数：生成n位m进制数。voidgenerateNumbers(intn,intm,stringcurrent,vector<string>&result){//递归出口：已经生成了n位数字。if(current.length()==n){result.push_back(current);return;}//每一位都可以填0~m-1。for(inti=0;i<m;++i){generateNumbers(n,m,current+to_string(i),result);}}intmain(){intn,m;cin>>n>>m;vector<string>numbers;//从空字符串开始生成。generateNumbers(n,m,"",numbers);//输出所有结果。for(conststring&num:numbers){cout<<num<<endl;}return0;}4.在AI下棋程序中，计算猫抓老鼠游戏的概率。题目描述：有这样一个游戏：在一个n*n的格子棋盘里，n是奇数；有两种棋子，一个是只能横向移动的棋子猫，一个是可以上下左右移动的棋子老鼠。假设老鼠在棋盘的正中央，第一步老鼠将进行上下左右的随机移动。棋子猫在从棋盘的中间行的最左边向棋盘的最右边移动，棋子猫每次移动只能是从左到右移动一步，第一步是猫位于棋盘的中间行的最左边格子。请问：在猫移动到棋盘外面前，会有多大概率抓到老鼠？输入格式：输入一个大于1的奇数n，表示棋盘的大小。输出格式：棋子猫抓到棋子老鼠的概率。(小数四舍五入保留4位有效数字)。样例输入：3样例输出：0.6667参考程序：#include<iostream>#include<vector>#include<map>#include<iomanip>//用于设置输出精度。#include<cmath>usingnamespacestd;//计算猫抓到老鼠的总概率。doublecalculateProbability(intn){intcenter=(n-1)/2;//棋盘中心点坐标。map<pair<int,int>,double>prob;//记录老鼠在每个位置的概率。prob[{center,center}]=1.0;//初始时老鼠一定在中心点。doubletotalProb=0.0;//总被抓概率。//猫从中间行最左→一直向右走，直到走出棋盘（共走n步）。for(intcatCol=0;catCol<n;++catCol){map<pair<int,int>,double>newProb;//遍历老鼠当前所有可能的位置，计算下一步移动概率。for(auto&entry:prob){intx=entry.first.first;inty=entry.first.second;doublep=entry.second;//老鼠四个方向移动。vector<pair<int,int>>moves={{x-1,y},{x+1,y},{x,y-1},{x,y+1}};intvalidMoves=0;//先统计有多少个合法移动方向。for(auto&move:moves){if(move.first>=0&&move.first<n&&move.second>=0&&move.second<n){validMoves++;}}//按概率分配到下一个位置。for(auto&move:moves){if(move.first>=0&&move.first<n&&move.second>=0&&move.second<n){newProb[move]+=p/validMoves;}}}prob=newProb;//更新老鼠位置概率分布。//判断：猫当前位置是否能抓到老鼠。pair<int,int>catchPos={center,catCol};if(prob.find(catchPos)!=prob.end()){totalProb+=prob[catchPos];//累加被抓概率。prob.