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

NOIP普及组模拟试题（含详细答案解析）考试时长：120分钟满分：400分答题说明1.严格按照题目要求编写程序，输入输出格式必须与题目规定完全一致，否则不予得分；2.程序允许使用C、C++语言，禁止使用特殊编译器扩展语法；3.所有题目均为标准输入、标准输出，无需读写本地文件；4.内存限制均为256MB，时间限制均为1000ms。第一题整数求和（100分）题目描述给定两个正整数a和b，计算从a到b之间（包含a、b）所有整数的和。输入格式一行两个正整数a、b，中间用空格隔开。输出格式一行一个整数，表示区间所有数的和。数据范围1≤a≤b≤100000样例输入110样例输出55题目解析本题是普及组基础入门题，考察循环遍历或数学公式求和，两种方法均可通过所有测试点。方法一（数学公式，效率最优）：连续整数求和公式为sum=(a+b)×(b−a+1)/方法二（循环遍历）：从a循环到b，逐个累加数值，逻辑简单直观，适合新手理解。满分代码（C++）cpp

#include<iostream>

usingnamespacestd;

intmain()

{

longlonga,b;

cin>>a>>b;

longlongans=(a+b)*(b-a+1)/2;

cout<<ans<<endl;

return0;

}答案说明样例中1~10求和：(1+10)×10/2=55，与输出一致。使用longlong类型可避免数值溢出，适配题目最大数据范围。第二题字符统计（100分）题目描述给定一串只包含小写英文字母的字符串，统计其中出现次数最多的字符，以及该字符出现的次数。若有多个字符出现次数相同且均为最多，输出字典序最小的字符。输入格式一行一个小写字母字符串，长度不超过1000。输出格式一行输出一个字符和一个整数，中间用空格隔开，分别表示答案字符和对应次数。样例输入abacaba样例输出a4题目解析本题考察字符串遍历与数组计数，是普及组高频基础题型。核心思路：开设大小为26的数组，对应26个小写字母，遍历字符串统计每个字母出现次数。遍历计数数组时，按照a~z的字典序遍历，遇到次数更大的字符则更新答案，次数相等时保留先遍历到的（字典序更小），即可满足题目要求。满分代码（C++）cpp

#include<iostream>

#include<string>

usingnamespacestd;

intcnt[26];

intmain()

{

strings;

cin>>s;

//统计字符出现次数

for(inti=0;i<s.size();i++)

{

cnt[s[i]-'a']++;

}

intmaxnum=0;

charres;

//按字典序遍历，保证相同次数取最小字典序

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

{

if(cnt[i]>maxnum)

{

maxnum=cnt[i];

res='a'+i;

}

}

cout<<res<<""<<maxnum<<endl;

return0;

}答案说明样例字符串abacaba中，a出现4次，b出现2次，c出现1次，a为出现次数最多的字符，故输出a4。第三题倍数问题（100分）题目描述给定一个正整数n，求出1到n之间（包含n）所有是3的倍数或者5的倍数的数字总和。输入格式一行一个整数n。输出格式一行一个整数，表示符合条件的数字和。数据范围1≤n≤1000000样例输入115样例输出160样例解释符合条件的数：3、5、6、9、10、12、15，求和结果为60。题目解析本题考察容斥原理，是普及组经典数学题型。直接循环遍历可过基础数据，大数据范围推荐容斥公式，效率更高。容斥原理：3的倍数和+5的倍数和-15的倍数和（15是3和5的最小公倍数，避免重复计算）。倍数求和公式：k的1~m倍和=k×m×(m+1)/满分代码（C++）cpp

#include<iostream>

usingnamespacestd;

typedeflonglongll;

//计算1~n中k的倍数和

llget_sum(lln,llk)

{

llm=n/k;

returnk*m*(m+1)/2;

}

intmain()

{

lln;

cin>>n;

llans=get_sum(n,3)+get_sum(n,5)-get_sum(n,15);

cout<<ans<<endl;

return0;

}答案说明n=15时，3的倍数和：3+6+9+12+15=45，5的倍数和：5+10+15=30，15的倍数和：15，最终45+30-15=60，与样例一致。第四题最大子段和（100分）题目描述给定一个长度为n的整数序列，求出该序列的最大子段和。子段指连续的一段序列，不能为空。序列包含正数、负数和0。输入格式第一行一个整数n，表示序列长度；第二行n个整数，为序列的各个元素。输出格式一行一个整数，表示最大子段和。数据范围1≤n≤100000，数值范围[-10000,10000]样例输入7-21-34-121样例输出6样例解释最优子段为4、-1、2、1，和为6。题目解析本题为普及组经典动态规划题目，核心为贪心DP思想（Kadane算法），时间复杂度O(n)，可适配最大数据范围。核心思路：维护当前子段和now，如果now<0，说明当前子段无贡献，直接舍弃，重置为当前数值；否则累加当前数值。全程更新最大子段和ans。满分代码（C++）cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

typedeflonglongll;

constintN=1e5+10;

inta[N];

intmain()

{

intn;

cin>>n;

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

{

cin>>a[i];

}

llans=-1e18;

llnow=0;

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

{

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

ans=max(ans,now);

}

cout<<ans<<endl;

return0;

}答案说明遍历样例序列时，前面负数子段被舍弃，从数值4开始累加，最终得到最大和6，符合样例结果。该算法可处理全负数序列，会自动选取最大的单个负数。全套试