NOIP普及组决赛模拟试题（含详细答案解析）

NOIP普及组决赛模拟试题（含详细答案解析）考试时长：4小时满分：400分编译环境：C++做题须知1.所有题目均使用标准输入、标准输出，不允许读写文件2.程序禁止使用万能头以外的非标准库，禁止使用离线调试函数3.输出答案必须严格匹配格式，多余空格、换行均视为错误4.数据范围严格遵从题目描述，超时、超内存均不得分第一题数字统计（100分）题目描述给定两个正整数L、R，统计区间[L,R]内所有整数中，数字2出现的总次数。例如：区间[2,22]中，数字2出现在2、12、20、21、22中，总次数为5次。输入格式一行两个正整数L、R。输出格式一行一个整数，表示数字2出现的总次数。数据范围对于50%数据：1≤L≤R≤1000对于100%数据：1≤L≤R≤1000000样例输入222样例输出5详细题解本题为基础模拟题，核心思路为遍历区间内每一个数字，逐位拆解判断是否为2，累计计数即可。数据范围最大为1e6，暴力遍历完全不会超时，适合入门选手练习基础循环与数位拆解。解题步骤：1.定义计数器变量，初始值为0；2.循环遍历L到R的所有整数；3.对每个数，逐位取余10判断当前数位是否为2，若是则计数器加1；4.将数字除以10，去掉已判断的最后一位，重复操作直至数字为0；5.遍历结束后输出计数器结果。AC代码cpp

#include<iostream>

usingnamespacestd;

intmain()

{

intL,R;

cin>>L>>R;

intcnt=0;

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

{

intx=i;

while(x>0)

{

if(x%10==2)cnt++;

x/=10;

}

}

cout<<cnt<<endl;

return0;

}第二题购物报销（100分）题目描述某公司报销规则如下：单次消费金额不超过100元的部分全额报销，超过100元但不超过500元的部分报销80%，超过500元的部分报销50%。给定一笔消费总金额，计算可以报销的最大金额（结果保留整数，直接向下取整）。输入格式一行一个整数n，表示消费总金额。输出格式一行一个整数，表示报销金额。数据范围1≤n≤10000样例输入180样例输出180样例输入2300样例输出2260样例解释2100元全额报销，剩余200元按80%报销，100+200*0.8=260。详细题解本题为分段计算题，核心是按照报销规则分层计算，避免区间重叠出错。根据规则分为三个区间，逐段核算报销金额即可。分段规则拆解：1.金额≤100：全额报销；2.100＜金额≤500：100元全额，超出100的部分80%；3.金额＞500：100元全额，400元（100-500区间）80%，超出500的部分50%。所有计算结果向下取整，C++整数除法可自动实现该效果。AC代码cpp

#include<iostream>

usingnamespacestd;

intmain()

{

intn;

cin>>n;

intres=0;

if(n<=100)

{

res=n;

}

elseif(n<=500)

{

res=100+(n-100)*4/5;

}

else

{

res=100+400*4/5+(n-500)/2;

}

cout<<res<<endl;

return0;

}第三题最大子段和（100分）题目描述给定一个长度为n的整数序列，找出其中一段连续的子序列，使得该子序列的和最大，输出这个最大和。子序列不能为空，至少包含一个元素。输入格式第一行一个整数n，表示序列长度。第二行n个整数，为序列的各个元素。输出格式一行一个整数，表示最大子段和。数据范围对于60%数据：1≤n≤100对于100%数据：1≤n≤100000，序列元素绝对值不超过1000样例输入51-234-5样例输出7样例解释选取子段[3,4]，和为7，为全局最大值。详细题解本题为经典贪心算法题型（最大子段和），朴素双重循环暴力解法会在大数据下超时，需使用线性贪心算法（Kadane算法），时间复杂度O(n)，可适配1e5数据范围。算法思路：1.维护两个变量：当前子段和、全局最大和；2.遍历每个元素，若当前子段和为负数，直接舍弃前面的子段，从当前元素重新开始累加；3.每次累加后，更新全局最大和；4.遍历结束后，全局最大和即为答案。AC代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

constintN=1e5+10;

inta[N];

intmain()

{

intn;

cin>>n;

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

cin>>a[i];

intnow=a[1],maxn=a[1];

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

{

now=max(a[i],now+a[i]);

maxn=max(maxn,now);

}

cout<<maxn<<endl;

return0;

}第四题最短路径（100分）题目描述给定一张无向连通图，包含n个节点、m条边，每条边的权值均为正整数。求从节点1到节点n的最短路径长度。输入格式第一行两个整数n、m，分别表示节点数和边数。接下来m行，每行三个整数u、v、w，表示u和v之间有一条权值为w的无向边。输出格式一行一个整数，表示1号节点到n号节点的最短路径长度。数据范围1≤n≤1000，1≤m≤50001≤w≤100样例输入44121245132341样例输出3样例解释最短路径为1→3→4，总长度2+1=3。详细题解本题为经典单源最短路径问题，节点数n≤1000，使用朴素Dijkstra算法即可完美通过，无需堆优化，代码简洁且不易出错。算法思路：1.初始化距离数组，所有节点距离设为无穷大，起点1的距离设为0；2.每次选取未访问过的距离最小的节点，标记为已访问；3.用该节点更新其所有相邻节点的最短距离；4.重复操作直至所有节点遍历完成，最终dist[n]即为答案。AC代码cpp

#include<iostream>

#include<cstring>

#include<algorithm>

usingnamespacestd;

constintN=1010;

constintINF=0x3f3f3f3f;

intmp[N][N];

intdist[N];

boolvis[N];

intn,m;

intmain()

{

memset(mp,0x3f,sizeof(mp));

cin>>n>>m;

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

{

intu,v,w;

cin>>u>>v>>w;

mp[u][v]=w;

mp[v][u]=w;

}

memset(dist,0x3f,sizeof(dist));

dist[1]=0;

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

{

intt=-1;

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

{

if(!vis[j]&&(t==-1||dist[j]<dist[t]))

t=j;

}

vis[t]=true;

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

{

dist[j]=min(dist[j],dist[t]+mp[t][j]);

}