NOIP全国青少年信息学奥林匹克联赛复赛模拟试题及详细答案

NOIP全国青少年信息学奥林匹克联赛复赛模拟试题及详细答案考试时长：3小时满分：400分试题说明：本次试题贴合NOIP普及组复赛真题难度与题型结构，包含四道编程题，每题100分。题目无特殊陷阱，数据范围贴合联赛常规考察标准，解题思路以基础算法、模拟、贪心、动态规划、字符串处理为主，适配联赛核心考点。答题要求：所有题目仅需提交C++源代码，代码需包含标准输入输出，文件读写严格按照题目要求，禁止使用特殊头文件与非常规语法。第一题数字统计（100分）题目描述给定两个正整数L和R，统计区间[L,R]内所有整数中，数字2出现的总次数。例如：区间[2,22]中，数字2、12、20、21、22包含数字2，总次数为5次。输入格式一行两个正整数L,R。输出格式一行一个整数，表示数字2出现的总次数。数据范围1≤L≤R≤100000样例输入222样例输出5解题思路本题为基础模拟题，核心思路为遍历区间内每一个数字，逐位拆解每个数字的每一位，判断是否为2，累计统计数量即可。数据范围较小，暴力遍历不会超时，是联赛入门基础题型。具体步骤：1、循环遍历从L到R的所有整数；2、对每个数，不断取余10获取最后一位，判断是否为2，若为2则计数器加一；3、将数字除以10去掉最后一位，重复操作直至数字变为0；4、遍历结束后输出计数器结果。标准答案代码cpp

#include<iostream>

usingnamespacestd;

intmain()

{

intL,R;

cin>>L>>R;

intcnt=0;

for(inti=L;i<=R;i++)

{

intt=i;

while(t!=0)

{

if(t%10==2)

cnt++;

t/=10;

}

}

cout<<cnt<<endl;

return0;

}代码解析1、定义变量L、R存储输入区间，cnt作为统计计数器，初始值为0；2、外层for循环遍历区间所有数字；3、临时变量t保存当前数字，避免修改循环变量；4、while循环逐位拆解数字，取余10判断末位是否为2，成功则计数；5、整除10移除末位，完成单个数判断；6、全部遍历完成后输出最终计数。第二题购物报销（100分）题目描述学校为社团活动提供报销补贴，现有报销规则：单笔消费金额不超过100元的部分全额报销，超过100元的部分报销50%。现有n笔消费账单，请计算总报销金额。例如：一笔消费120元，100元全额报销，20元报销10元，单笔总报销110元。输入格式第一行一个整数n，表示账单数量。第二行n个整数，依次表示每笔账单的消费金额。输出格式一行一个实数，保留一位小数，表示总报销金额。数据范围1≤n≤1000，每笔消费金额为1~1000的整数样例输入380120200样例输出270.0解题思路本题为贪心模拟题，按照题目给定的报销规则逐笔计算报销金额，累加得到总和即可。核心是区分单笔消费的两段报销比例，精准计算每笔费用。最后按照格式保留一位小数输出结果。计算规则：单笔金额x，若x≤100，报销x元；若x>100，报销100+(x-100)*0.5元。逐笔累加所有报销金额，最终格式化输出。标准答案代码cpp

#include<iostream>

#include<iomanip>

usingnamespacestd;

intmain()

{

intn;

cin>>n;

doublesum=0.0;

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

{

intx;

cin>>x;

if(x<=100)

sum+=x;

else

sum+=100+(x-100)*0.5;

}

cout<<fixed<<setprecision(1)<<sum<<endl;

return0;

}代码解析1、引入iomanip头文件，用于控制输出小数位数；2、读取账单数量n，定义浮点型变量sum存储总报销金额；3、循环读取每笔消费金额，按规则分段计算报销额并累加；4、通过fixed和setprecision(1)固定保留一位小数，输出最终结果，适配题目格式要求。第三题最长连续递增子序列（100分）题目描述给定一个长度为n的整数序列，找出其中最长的连续递增子序列的长度。连续递增子序列定义为：序列中连续的若干元素，后一个元素严格大于前一个元素。例如：序列132451中，最长连续递增子序列为245，长度为3。输入格式第一行一个整数n，表示序列长度。第二行n个整数，为给定的序列。输出格式一行一个整数，表示最长连续递增子序列的长度。数据范围1≤n≤100000，序列元素绝对值不超过10000样例输入6132451样例输出3解题思路本题为线性动态规划/线性遍历基础题，无需双重循环，一次遍历即可完成，时间复杂度O(n)，可适配大数据范围。核心思路：维护当前递增区间长度和全局最大长度。具体逻辑：1、初始状态下，每个单独元素自身是长度为1的递增序列；2、从第二个元素开始遍历，若当前元素大于前一个元素，当前递增长度+1；3、否则重置当前递增长度为1；4、每次更新当前长度后，对比更新全局最大长度；5、遍历结束后输出最大值即可。标准答案代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

constintMAXN=100010;

inta[MAXN];

intmain()

{

intn;

cin>>n;

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

cin>>a[i];

intmax_len=1;

intnow=1;

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

{

if(a[i]>a[i-1])

now++;

else

now=1;

max_len=max(max_len,now);

}

cout<<max_len<<endl;

return0;

}代码解析1、定义数组存储序列数据，适配最大数据范围；2、初始化最大长度和当前长度为1，满足单元素边界情况；3、从第二个元素开始遍历，判断是否满足严格递增条件，更新当前区间长度；4、每次遍历更新全局最长长度，保证记录最优解；5、一次遍历完成计算，效率极高，不会超时。第四题背包问题（基础01背包）（100分）题目描述现有一个容量为V的背包，以及n件物品，每件物品有对应的体积和价值，每件物品只能选择放入或不放入背包（不可拆分）。在背包体积不超过容量的前提下，求能装入物品的最大总价值。输入格式第一行两个整数n,V，分别表示物品数量和背包容量。接下来n行，每行两个整数w,v，分别表示单件物品的体积和价值。输出格式一行一个整数，表示背包可装载的最大价值。数据范围1≤n≤100，1≤V≤1000，物品体积、价值均为正整数样例输入41023344556样例输出12解题思路本题为NOIP普及组核心考点——01动态规划背包问题。核心状态定义：dp[j]表示背包容量为j时，可获得的最大价值。状态转移方程：对于第i件物品（体积w，价值v），逆序遍历背包容量j（从V到w），dp[j]=max(dp[j],dp[j-w]+v)。逆序遍历可保证每件物品仅被选取一次，满足01背包不重复选取的规则。初始状态dp数组全部为0，表示无物品时价值为0。最终dp[V]即为背包容量为V时的最大价值。标准答案代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

intdp[1010];

intmain()

{

intn,V;

cin>>n>>V;

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

{

intw,v;

cin>>w>>v;

for(intj=V;j>=w;j--)

{

dp[j]=max(dp[j],dp[j-w]+v);

}

}

cout<<dp[V]<<endl;

return0;

}代码解析1、定义一维dp数组，节省空间，适配背包容量范围；2、依次读取每件物品的体积和价值；3、逆序遍历容量，更新dp数组状态，对比“不选当前物品”和“选当前物品”的价值，保留最大值；4、遍历完所有物品后