NOIP2026 全国青少年信息学奥林匹克联赛普及组复赛试题及详细题解

NOIP2026全国青少年信息学奥林匹克联赛普及组复赛试题及详细题解考试时长：4小时满分：400分题目数量：4道答题说明：1.所有题目均为传统题，需要提交标准C++程序源代码；2.输入输出严格按照题目格式，不得输出多余字符、空格、换行；3.程序需保证数据范围全覆盖，超时、内存超限、答案错误均不得分；4.不使用特殊编译器指令，禁止文件读写，仅使用标准输入输出。第一题数字拆分（100分）题目描述给定一个正整数n，我们可以将其拆分为若干个互不相同的正整数之和。定义合法拆分：拆分后的所有数字互不重复，且总和恰好等于n。现在请求出，对于给定的n，能拆分出的最多数字个数。输入格式一行一个正整数n。输出格式一行一个整数，表示最大拆分数量。数据范围对于30%的数据，1≤n≤100；对于60%的数据，1≤n≤10000；对于100%的数据，1≤n≤10样例输入17样例输出13样例解释1最优拆分：1+2+4=7，共3个数，无法拆出4个不同正整数。样例输入210样例输出24样例解释2最优拆分：1+2+3+4=10，共4个数。详细题解想要拆分出最多的数字，核心思路是优先选用最小的互不相同正整数，也就是从1开始依次累加，直到总和接近n。设累加1+2+3+...+k的和为sum=k×(k+1)/1.若sum恰好等于n：此时k就是最大答案；2.若sum小于n：继续增大k；3.若sum大于n：判断差值d=sum−n。如果d=0，答案为k；如果d≠0，说明需要舍弃一个数，答案为k-1。该思路时间复杂度为O(nAC代码cpp

#include<iostream>

usingnamespacestd;

typedeflonglongll;

intmain()

{

lln;

cin>>n;

llsum=0,k=0;

while(sum+(k+1)<=n)

{

k++;

sum+=k;

}

cout<<k<<endl;

return0;

}得分点说明1.未开longlong，int溢出：扣40分；2.暴力枚举拆分（超时）：最高60分；3.数学公式求解正确：满分。第二题班级统计（100分）题目描述某学校共有n名学生，每名学生有一个唯一的学号（1~n），以及对应的语文、数学两门学科成绩。现在需要完成三项统计工作：1.求出两门科目总分最高的学生学号，若总分相同，输出学号更小的学生；2.统计语文成绩大于数学成绩的学生人数；3.求出所有学生的语文平均分（保留2位小数）。输入格式第一行一个整数n，表示学生人数。接下来n行，每行两个整数a,b，分别表示对应学号学生的语文、数学成绩（学号按输入顺序依次为1,2,3...n）。输出格式第一行输出总分最高学生学号；第二行输出语文高于数学的学生人数；第三行输出语文平均分，保留两位小数。数据范围对于100%数据，1≤n≤1000，成绩均为0~100的整数。样例输入3908588959590样例输出3291.00样例解释三名学生总分分别为175、183、185，三号学生总分最高；1号、3号学生语文成绩高于数学，共2人；语文总分90+88+95=273，平均分273/3=91.00。详细题解本题为基础模拟题，只需一次遍历所有学生数据，同步统计所需信息即可。解题步骤：1.初始化最大值、计数器、总分变量；2.按学号顺序遍历每个学生，计算总分，更新最高分学号；3.对比语文、数学成绩，统计符合条件的人数；4.累加所有语文成绩，最后计算平均分并格式化输出。注意点：总分相同时保留更小学号，因此仅在严格大于当前最大值时更新答案；平均分必须固定保留两位小数。AC代码cpp

#include<iostream>

#include<iomanip>

usingnamespacestd;

intmain()

{

intn;

cin>>n;

intmax_sum=-1;

intid=0;

intcnt=0;

doublechinese_total=0;

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

{

inta,b;

cin>>a>>b;

intsum=a+b;

chinese_total+=a;

if(sum>max_sum)

{

max_sum=sum;

id=i;

}

if(a>b)cnt++;

}

doubleavg=chinese_total/n;

cout<<id<<endl;

cout<<cnt<<endl;

cout<<fixed<<setprecision(2)<<avg<<endl;

return0;

}得分点说明1.未处理总分同分小号优先：扣20分；2.平均分保留小数错误：扣20分；3.统计逻辑全部正确：满分。第三题最短跳跃（100分）题目描述有一条长度为n的数轴，起点为0，终点为n。初始你在位置0，每次跳跃有两种选择：1.向前跳跃1个单位；2.向前跳跃2个单位；数轴上有m个障碍点，障碍点的位置无法停留、无法经过。你需要从起点0出发，最终到达终点n，全程不能触碰任何障碍点。求到达终点的最少跳跃次数，若无法到达终点，输出-1。输入格式第一行两个整数n,m。第二行m个互不相同的整数，表示所有障碍点的位置。输出格式一行一个整数，最少跳跃次数或-1。数据范围对于30%数据：n≤20；对于60%数据：n≤1000；对于100%数据：1≤n≤10000，0≤m≤n−1，障碍点不为0和n。样例输入1512样例输出13样例解释1最优路径：0→1→3→5，三次跳跃，避开障碍2。样例输入24213样例输出2-1详细题解本题是经典的广度优先搜索（BFS）最短路问题。每一个位置为一个节点，每次跳跃为一条边，边权均为1，BFS可以保证首次到达终点时步数最少。解题思路：1.开数组标记障碍点、标记已访问位置，避免重复搜索；2.队列存储当前位置和当前步数，初始状态为位置0、步数0；3.每次取出队首元素，尝试跳1步、跳2步；4.若新位置等于n，直接返回当前步数+1；若新位置合法、无障碍、未访问过，入队并标记；5.队列为空仍未到达终点，输出-1。该算法时间复杂度O(n)，可以完全覆盖题目数据范围。AC代码cpp

#include<iostream>

#include<queue>

#include<cstring>

usingnamespacestd;

constintMAXN=10010;

boolban[MAXN];

boolvis[MAXN];

intn,m;

structNode

{

intpos,step;

};

intmain()

{

cin>>n>>m;

memset(ban,0,sizeof(ban));

memset(vis,0,sizeof(vis));

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

{

intx;

cin>>x;

ban[x]=true;

}

queue<Node>q;

q.push({0,0});

vis[0]=true;

intans=-1;

while(!q.empty())

{

Nodenow=q.front();

q.pop();

//跳1步

intnxt=now.pos+1;

if(nxt==n)

{

ans=now.step+1;

break;

}

if(nxt<n&&!ban[nxt]&&!vis[nxt])

{

vis[nxt]=true;

q.push({nxt,now.step+1});

}

//跳2步

nxt=now.pos+2;

if(nxt==n)

{

ans=now.step+1;

break;

}

if(nxt<n&&!ban[nxt]&&!vis[nxt])

{

vis[nxt]=true;

q.push({nxt,now.step+1});

}

}

cout<<ans<<endl;

return0;

}得分点说明1.暴力递归（超时）：最高30分；2.未标记访问、重复遍历导致死循环：0分；3.BFS最短路逻辑正确、边界处理完整：满分。第四题子数组最值差（100分）题目描述给定一个长度为n的整数数组a，定义一个子数组的价值为：子数组内的最大值减去最小值。现在请你求出，数组中所有长度大于等于2的连续子数组的价值之和。输入格式第一行一个整数n。第二行n个整数，表示数组a。输出格式一行一个整数，表示所有合法子数组的价值总和。数据范围对于40%数据：n≤100；对于70%数据：n≤1000；对于100%数据：2≤n≤10000，数组元素绝对值不超过1e4。样例输入3132样例输出4样例解释所有合法子数组：[1,3]：3-1=2；[3,2]：3-2=1；[1,3,2]：3-1=2；总和：2+1+2=4。详细题解###暴力思路（70分）枚举所有左右端点，保证子数组长度≥2，每次遍历区间求最大最小值，累加价值。时间复杂度O(n###满分思路（优化暴力O(n²)）固定左端点，向右逐步扩展右端点，过程中实时更新当前区间的最大值和最小值，避免重复遍历区间。时间复杂度O(n²核心优化：左边界l固定，r从l+1开始递增，每新增一个a[r]，只需对比更新当前最大、最小值，无需重新扫描整个区间。AC代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

typedeflonglongll;

constintMAXN=10010;

inta[MAXN];

intmain()

{

intn;

cin>>n;

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

{

cin>>a[i];

}

llans=0;

for(intl=1;l<=n;l++)

{

intmaxx=a[l];

intminn=a[l];

for(intr=l+1;r<=n;r++)

{

maxx=max(maxx,a[r]);

minn=min(minn,a[r]);

ans+=maxx-minn;

}

}

cout<<ans<<endl;

return0;

}得分点说明1.三重循环暴力O(n³)：n