NOI 普及组风格模拟试题（含详细答案）

NOI普及组风格模拟试题（含详细答案）本次试题对标NOI普及组正式赛难度，共4道大题，满分400分，考试时长4小时。试题无套路模板，贴合真实竞赛出题思路，侧重考察代码功底、算法思维和细节调试能力。考试说明1.程序文件名严格按照题目要求，不得自定义文件名；2.输入输出均使用标准读写，禁止文件读写（除题目特殊说明）；3.数据范围严格遵循题目限制，注意边界情况、超时、爆int问题；4.编程语言仅限C++。第一题数字统计（100分）题目描述给定两个正整数L、R，统计区间[L,R]内，所有整数中数字2出现的总次数。例如：12、20、21三个数中，数字2一共出现了3次。输入格式一行两个正整数L,R。输出格式一行一个整数，表示数字2出现的总次数。数据范围1≤L≤R≤100000题解与代码解题思路：暴力枚举区间内每一个数，逐位拆解数字，判断是否为2并计数即可。数据范围较小，无需数位DP，基础模拟即可通过所有测试点。cpp

#include<iostream>

usingnamespacestd;

intmain()

{

intl,r;

cin>>l>>r;

intans=0;

for(inti=l;i<=r;i++)

{

intx=i;

while(x)

{

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

x/=10;

}

}

cout<<ans;

return0;

}样例输入11221样例输出13第二题最短跳跃（100分）题目描述小明在一条数轴上，初始位置为0。数轴上有n个落脚点，位置分别为a₁,a₂…aₙ（全部为正整数，且从小到大排序，无重复）。小明每次跳跃只能跳到下一个落脚点，不能后退、不能跳过。定义一次跳跃的代价为跳跃的距离。现在你可以删除最多一个落脚点（可以不删），求走完所有剩余落脚点的最大单次跳跃代价的最小值。输入格式第一行一个整数n；第二行n个整数，为递增的落脚点坐标。输出格式一个整数，表示最优策略下的最小最大跳跃距离。数据范围3≤n≤1000，1≤a[i]≤10000题解与代码解题思路：贪心模拟。删除一个点的本质是将相邻三段的两个间隔合并为一个间隔。遍历每一个可以删除的中间点，计算删除后的最大跳跃距离，取所有情况的最小值即可。cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

inta[1010];

intmain()

{

intn;

cin>>n;

for(inti=1;i<=n;i++)cin>>a[i];

intres=1e9;

//枚举删除每个中间点

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

{

intmaxd=0;

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

{

if(j==i)

{

maxd=max(maxd,a[j+1]-a[j-1]);

j+=2;

}

else

{

maxd=max(maxd,a[j+1]-a[j]);

j++;

}

}

res=min(res,maxd);

}

cout<<res;

return0;

}样例输入5

1361015样例输出4样例解释：删除6，跳跃间隔为2、7、5，最大值7；删除10，间隔为2、3、4、5，最大值4，为最优解。第三题单词统计（100分）题目描述给定一篇由小写字母和空格组成的短文，短文由若干单词组成，单词之间用单个空格分隔。现在需要完成两个统计任务：1.输出总单词数量；2.输出出现次数最多的单词，若有多个，输出字典序最小的那个。输入格式一行字符串（无首尾空格，单词单空格分隔）。输出格式第一行：单词总数；第二行：出现次数最多的单词。数据范围字符串长度≤10000，单个单词长度≤100。题解与代码解题思路：利用string字符串读入分割，map哈希统计单词出现次数。map自带字典序排序，完美解决多解取最小字典序的问题。cpp

#include<iostream>

#include<string>

#include<map>

usingnamespacestd;

map<string,int>cnt;

intmain()

{

strings,word;

inttot=0;

while(cin>>word)

{

cnt[word]++;

tot++;

}

cout<<tot<<endl;

stringans;

intmaxc=0;

//map自动字典序从小到大遍历

for(autop:cnt)

{

if(p.second>maxc)

{

maxc=p.second;

ans=p.first;

}

}

cout<<ans;

return0;

}样例输入iloveoioilovecode样例输出6

oi第四题迷宫搜索（100分）题目描述给定一个n×m的迷宫，迷宫中：0代表空地，可以行走；1代表墙壁，无法通行；起点为(1,1)，终点为(n,m)。每次只能向上下左右四个方向移动一格，求从起点到终点的最短路径步数，若无法到达，输出-1。注意：起点终点步数记为0，每移动一格步数+1。输入格式第一行两个整数n,m；接下来n行，每行m个数字（0或1）。输出格式一个整数，最短路径步数或-1。数据范围1≤n,m≤50题解与代码解题思路：经典BFS广度优先搜索，BFS天然求解无权图最短路径。标记走过的点防止重复遍历，搜到终点直接返回步数。cpp

#include<iostream>

#include<queue>

#include<cstring>

usingnamespacestd;

structnode{

intx,y,step;

};

intn,m;

intmp[55][55];

boolvis[55][55];

//上下左右

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

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

intmain()

{

cin>>n>>m;

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

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

cin>>mp[i][j];

queue<node>q;

q.push({1,1,0});

vis[1][1]=true;

intans=-1;

while(!q.empty())

{

nodenow=q.front();

q.pop();

if(now.x==n&&now.y==m)

{

ans=now.step;

break;

}

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

{

intnx=now.x+dx[i];

intny=now.y+dy[i];

if(nx>=1&&nx<=n&&ny>=1&&ny<=m)

{

if(!vis[nx][ny]&&mp[nx][ny]==0)

{

vis[nx][ny]=true;

q.push({nx,ny,now.ste