2025第十六届蓝桥杯大赛青少组省赛C++真题及答案解析

2025第十六届蓝桥杯大赛青少组省赛C++真题及答案解析第一部分填空题（共5题，每题8分，总计40分）1.将十进制数2025转换为八进制数后，其各位数字之和为______。【答案】16【解析】十进制转八进制采用“除8取余，逆序排列”的方法：2025÷8=253余1253÷8=31余531÷8=3余73÷8=0余3将余数逆序排列得到八进制数3751，各位数字之和为3+7+5+1=16。也可通过位权验证：3×8³+7×8²+5×8¹+1×8⁰=1536+448+40+1=2025，转换结果正确。2.已知斐波那契数列定义为：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)（n≥3）。则F(20)除以7的余数为______。【答案】3【解析】方法一：直接递推计算模7的结果，避免数值过大：F(1)%7=1，F(2)%7=1F(3)%7=(1+1)%7=2F(4)%7=(2+1)%7=3F(5)%7=(3+2)%7=5F(6)%7=(5+3)%7=1F(7)%7=(1+5)%7=6F(8)%7=(6+1)%7=0F(9)%7=(0+6)%7=6F(10)%7=(6+0)%7=6F(11)%7=(6+6)%7=5F(12)%7=(5+6)%7=4F(13)%7=(4+5)%7=2F(14)%7=(2+4)%7=6F(15)%7=(6+2)%7=1F(16)%7=(1+6)%7=0F(17)%7=(0+1)%7=1F(18)%7=(1+0)%7=1F(19)%7=(1+1)%7=2F(20)%7=(2+1)%7=3方法二：利用皮萨诺周期，斐波那契数列模m的结果具有周期性，模7的周期为16。20除以16余4，因此F(20)%7=F(4)%7=3。3.有5个不同的红球、3个不同的白球，全部放入编号为1、2、3的三个不同盒子中，要求每个盒子至少有1个球，且3个白球不能放在同一个盒子中，则共有______种不同的放法。【答案】5256【解析】采用分类计数结合容斥原理求解，分类依据为白球占据的盒子数量，分为“白球占据2个盒子”和“白球占据3个盒子”两类：（1）白球占据2个盒子：先选2个盒子放白球：组合数C(3,2)=3种选择3个不同的白球放入这2个盒子且每个盒子至少1个：2³-2=6种（总放法减去全放第一个、全放第二个的情况）此时剩余1个盒子没有白球，为满足“每个盒子至少1个球”，需保证该空盒子至少有1个红球。5个不同的红球总放法为3⁵=243种，减去空盒子不放红球的2⁵=32种，共243-32=211种此类总放法：3×6×211=3798种（2）白球占据3个盒子：3个不同的白球放入3个盒子且每个盒子至少1个：3!=6种（每个盒子恰好1个白球，全排列）此时每个盒子已有白球，红球可任意放置，5个红球的放法为3⁵=243种此类总放法：6×243=1458种总放法为两类之和：3798+1458=5256种。验证：用总满足“每个盒子至少1球”的放法减去“白球同盒且每个盒子至少1球”的放法，总放法为3⁸-3×2⁸+3×1⁸=6561-768+3=5796种；白球同盒时，选盒子3种，红球需放满剩余2个盒子，放法为3⁵-2×2⁵+1⁵=243-64+1=180种，共3×180=540种，5796-540=5256，结果一致。4.现有一个容量为20的背包，以及8件物品，物品的重量和价值如下表所示：物品编号12345678重量23456789价值345678910【答案】25【解析】本题为01背包问题，采用动态规划求解，定义dp[j]表示容量为j的背包能获得的最大价值，状态转移方程为dp[j]=max(dp[j],dp[j-w[i]]+v[i])，其中w[i]为第i件物品的重量，v[i]为价值，遍历物品时需逆序遍历背包容量避免重复选取物品。逐步计算后，容量为20的背包最大价值为25，对应选取物品1、2、3、4、5（重量2+3+4+5+6=20，价值3+4+5+6+7=25），该组合的价值密度最高，总价值最大。5.将正整数20拆分为若干个正整数之和，要求每个拆分的数不超过5，且不计较拆分的顺序（例如2+3和3+2视为同一种拆分），则共有______种不同的拆分方法。【答案】192【解析】本题为整数拆分计数问题，等价于“用面值为1、2、3、4、5的硬币凑20元，共有多少种凑法”，属于完全背包求组合数问题，采用动态规划求解：定义dp[i]表示凑出金额i的方案数，初始状态dp[0]=1（凑0元只有1种方法：不选任何硬币）。按硬币面值从小到大遍历（保证不计顺序），对于每种面值k，正序遍历金额从k到20，状态转移方程为dp[i]+=dp[i-k]（表示新增一种用k面值的方案）。逐步计算得dp[20]=192，即共有192种不同的拆分方法。可通过小数值验证：拆分5的方案共7种（全1、1+1+1+2、1+1+3、1+2+2、2+3、1+4、5），与计算结果一致。第二部分编程题（共5题，每题12分，总计60分）1.成绩评级题目描述：小蓝参加了蓝桥杯考试，成绩为整数n（0≤n≤100），请你根据成绩输出对应的评级：90分及以上：A80~89分：B70~79分：C60~69分：D60分以下：E输入格式：一行一个整数n，表示考试成绩。输出格式：一行一个大写字母，表示对应的评级。样例输入1：85样例输出1：B样例输入2：59样例输出2：E【参考代码】usingnamespacestd;intmain(){intn;cin>>n;if(n>=90){cout<<"A"<<endl;}elseif(n>=80){cout<<"B"<<endl;}elseif(n>=70){cout<<"C"<<endl;}elseif(n>=60){cout<<"D"<<endl;}else{cout<<"E"<<endl;}return0;}【解题思路】本题为基础分支结构应用题，只需按照分数区间依次判断即可。由于判断顺序从高到低，每个分支只需判断下界即可，无需同时判断上下界，简化代码逻辑。需注意输入范围为0到100，边界值如60、80、90需对应正确的评级，避免边界判断错误。【考点分析】标准输入输出、多分支if语句、逻辑判断。2.回文数计数题目描述：回文数是指从左往右读和从右往左读都完全相同的正整数，例如1、121、1331都是回文数，12、123不是回文数。给定两个正整数l和r（1≤l≤r≤10000），请统计闭区间[l,r]内共有多少个回文数。输入格式：一行两个整数l和r，用空格分隔。输出格式：一行一个整数，表示回文数的个数。样例输入：110样例输出：9样例解释：1到9都是一位数，均为回文数；10不是回文数，因此共9个。【参考代码】usingnamespacestd;//判断一个数是否为回文数boolisPalindrome(intx){intoriginal=x;intreversed=0;while(x>0){reversed=reversed*10+x%10;x/=10;}returnoriginal==reversed;}intmain(){intl,r;cin>>l>>r;intcount=0;for(inti=l;i<=r;i++){if(isPalindrome(i)){count++;}}cout<<count<<endl;return0;}【解题思路】1.封装回文数判断函数：通过逐位取余反转数字，将反转后的数字与原数字比较，若相等则为回文数。注意保存原数字的副本，避免反转过程中修改原数值导致比较失败。2.遍历区间[l,r]内的所有整数，逐个判断是否为回文数，统计符合条件的数量。由于r最大为10000，遍历次数不超过10000次，时间复杂度完全满足要求，无需额外优化。【考点分析】函数封装、数字反转操作、循环结构、计数统计。3.国王的金币题目描述：国王要给大臣发放金币，规则如下：第1天发1枚，第2天发2枚，第3天发3枚……第k天发k枚；每连续发放k天后，接下来的1天停发（不发放金币），之后再继续按顺序发放下一批金币。例如k=2时，发放规律为：第1天1枚，第2天2枚，第3天停发，第4天3枚，第5天4枚，第6天停发，以此类推。请问第m天结束后，大臣一共获得了多少枚金币？输入格式：一行两个整数k和m，用空格分隔（1≤k≤100，1≤m≤10000）。输出格式：一行一个整数，表示总金币数。样例输入：25样例输出：10样例解释：前5天中，第1天1枚、第2天2枚、第3天停发、第4天3枚、第5天4枚，总和为1+2+3+4=10。【参考代码】usingnamespacestd;intmain(){intk,m;cin>>k>>m;inttotal=0;//总金币数intcurrent=1;//当前要发放的金币数intday=1;//当前天数intsend_count=0;//当前周期已发放天数while(day<=m){if(send_count<k){total+=current;current++;send_count++;}else{send_count=0;//停发一天，重置周期计数}day++;}cout<<total<<endl;return0;}【解题思路】本题采用模拟法求解，按天模拟发放过程，逻辑清晰不易出错：1.维护四个核心变量：总金币数、当前待发放的金币数、当前天数、当前周期已发放的天数。2.循环处理每一天：若当前周期已发放天数小于k，则发放金币，总金币数累加当前金币数，当前金币数加1，已发放天数加1；否则当天停发，重置周期计数（当前天数仍要递增）。3.直到天数超过m时停止循环，输出总金币数。由于m最大为10000，模拟次数仅1万次，运行效率极高。也可通过数学公式计算完整周期数进一步优化，但模拟法更直观，适合本题数据范围。【考点分析】循环结构、模拟法、变量状态维护、边界条件处理。4.最长上升子序列题目描述：给定一个长度为n的整数序列，请求出该序列的最长严格上升子序列的长度。上升子序列是指从原序列中选取若干元素（可不连续），保持元素的相对顺序不变，且元素值严格递增。例如序列[1,3,2,5,4]的最长上升子序列长度为3（如1,3,5或1,2,4）。输入格式：第一行一个整数n，表示序列长度（1≤n≤1000）；第二行n个整数，为序列的元素，每个元素的绝对值不超过10000。输出格式：一行一个整数，表示最长上升子序列的长度。样例输入：513254样例输出：3【参考代码】usingnamespacestd;intmain(){intn;cin>>n;inta[1005];intdp[1005];//dp[i]表示以第i个元素结尾的最长上升子序列长度for(inti=0;i<n;i++){cin>>a[i];dp[i]=1;//初始长度为1（仅自身）}intmax_len=1;for(inti=0;i<n;i++){for(intj=0;j<i;j++){if(a[j]<a[i]){//严格上升，若为非严格则改为<=dp[i]=max(dp[i],dp[j]+1);}}max_len=max(max_len,dp[i]);}cout<<max_len<<endl;return0;}【解题思路】本题为经典动态规划入门题，采用O(n²)的动态规划解法，适合n≤1000的数据范围：1.状态定义：dp[i]表示以第i个元素结尾的最长严格上升子序列的长度。2.初始状态：每个元素自身构成一个长度为1的子序列，因此dp[i]初始值为1。3.状态转移：对于第i个元素，遍历其之前的所有元素j（j<i），若a[j]<a[i]，则可以将a[i]接在以a[j]结尾的子序列后面，形成更长的子序列，此时dp[i]=max(dp[i],dp[j]+1)。4.最终答案为所有dp[i]中的最大值，因为最长子序列不一定以最后一个元素结尾。本题n最大为1000，O(n²)的时间复杂度约为1e6次运算，完全满足时间要求。若数据范围更大（如n≤1e5），可采用贪心+二分的O(nlogn)解法，但本题无需复杂优化。【考点分析】动态规划思想、最长上升子序列模型、双重循环、最大值维护。5.迷宫最短路径题目描述：给定一个n行m列的迷宫，迷宫中包含三种字符：'S'表示起点，'T'表示终点，'#'表示障碍物，'.'表示空地。小蓝站在起点处，每次可以向上、下、左、右四个方向移动一格，不能移动到障碍物上，也不能走出迷宫边界。请求出小蓝从起点走到终点最少需要移动多少步？若无法到达终点，输出-1。输入格式：第一行两个整数n和m（1≤n,m≤100），表示迷宫的行数和列数；接下来n行，每行m个字符，表示迷宫的布局。输出格式：一行一个整数，表示从起点到终点的最少步数；若无法到达则输出-1。样例输入：33S...#...T样例输出：4样例解释：最短路径为S→(0,1)→(0,2)→(1,2)→(2,2)，共4步。【参考代码】usingnamespacestd;charmaze[105][105];//存储迷宫intdis[105][105];//存储每个位置到起点的最短距离，-1表示未访问//四个方向：上、下、左、右intdx[4]={-1,1,0,0};intdy[4]={0,0,-1,1};intmain(){intn,m;cin>>n>>m;intsx,sy,tx,ty;//起点和终点坐标memset(dis,-1,sizeof(dis));//初始化距离为-1（未访问）for(inti=0;i<n;i++){cin>>maze[i];for(intj=0;j<m;j++){if(maze[i][j]=='S'){sx=i;sy=j;dis[i][j]=0;//起点距离为0}if(maze[i][j]=='T'){tx=i;ty=j;}}}//BFS广度优先搜索queue<pair<int,int>>q;q.push({sx,sy});while(!q.empty()){pair<int,int>current=q.front();q.pop();intx=current.first;inty=current.second;//到达终点，直接输出距离if(x==tx&&y==ty){cout<<dis[x][y]<<endl;return0;}//遍