NOIP2026 普及组复赛试题及详细题解

NOIP2026普及组复赛试题及详细题解NOIP2026全国青少年信息学奥林匹克联赛普及组复赛考试时间：10月18日14:30-18:00试题总分：400分题目数量：4道大题编译环境：C++GCC9.3.0第一题整数拆分（split）【题目描述】给定一个正整数n，你需要将其拆分为若干个互不相同的正整数之和，使得拆分出的所有数的乘积最大。请输出这个最大乘积。【输入格式】一行一个正整数n。【输出格式】一行一个整数，表示最大乘积。【输入样例1】8【输出样例1】15【样例解释1】8拆分为3+5，乘积3×5=15，为所有合法拆分中的最大值。【输入样例2】10【输出样例2】30【数据范围】对于30%的数据：1≤n≤10对于60%的数据：1≤n≤100对于100%的数据：1≤n≤1000【第一题详细题解】解题思路本题核心是找整数拆分的最优策略，通过数学规律可直接推导最优方案，无需暴力枚举：1.想要互不相同的数乘积最大，优先选择连续的自然数（从2开始）累加，相同和的情况下，数越接近，乘积越大；2.先累加2,3,4...直到总和接近n，记录剩余差值rest；3.若剩余值为0，直接累乘所有数即可；4.若剩余值不为0，从最大的数开始依次+1分配剩余值，保证所有数不重复；5.特殊情况：n=1时只能输出1。满分代码（C++）cpp

#include<iostream>

#include<vector>

usingnamespacestd;

intmain()

{

intn;

cin>>n;

if(n==1)

{

cout<<1<<endl;

return0;

}

vector<int>num;

intsum=0;

intcur=2;

//先取连续递增数

while(sum+cur<=n)

{

num.push_back(cur);

sum+=cur;

cur++;

}

intrest=n-sum;

//从后往前分配余数

for(inti=num.size()-1;rest>0;i--)

{

num[i]++;

rest--;

if(i==0)i=num.size();

}

//计算乘积

longlongans=1;

for(intx:num)ans*=x;

cout<<ans<<endl;

return0;

}得分点说明30分：暴力枚举所有拆分情况，处理小数据；60分：实现连续数累加策略，未优化余数分配；100分：正确分配余数，使用longlong防止溢出，处理特殊边界。第二题班级统计（count）【题目描述】某学校一个班级有n名学生，每名学生有一门期末分数，分数为0∼100的整数。现在给出m次查询，每次查询给出两个整数l,r，要求统计区间[l,r]内的学生中：1.最高分、最低分；2.平均分（保留两位小数）；3.及格人数（分数≥60）。【输入格式】第一行两个整数n,m，分别表示学生人数和查询次数。第二行n个整数，依次为1~n号学生的分数。接下来m行，每行两个整数l,r，表示查询区间。【输出格式】对于每次查询，输出一行四个数据：最高分、最低分、平均分、及格人数，数据之间用空格分隔，平均分保留两位小数。【输入样例】5285599266451325【输出样例】925978.672924565.502【数据范围】对于50%的数据：n,m≤1000对于100%的数据：1≤n,m≤105【第二题详细题解】解题思路本题数据量较大，直接暴力遍历每个查询会超时，需要预处理前缀数组实现O(1)查询：1.预处理前缀和数组，快速求区间总分、平均分；2.预处理前缀及格人数数组，快速统计区间及格人数；3.针对区间最值，使用ST表预处理，实现静态区间最大最小值O(1)查询；4.每次查询直接调取预处理结果，计算输出即可。满分代码（C++）cpp

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

usingnamespacestd;

constintMAXN=1e5+10;

constintLOG=20;

intn,m;

inta[MAXN];

longlongsum[MAXN];

intpass[MAXN];

intmaxst[LOG][MAXN];

intminst[LOG][MAXN];

intlog2n[MAXN];

voidinit()

{

//预处理log2

log2n[1]=0;

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

log2n[i]=log2n[i/2]+1;

//初始化ST表

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

{

maxst[0][i]=a[i];

minst[0][i]=a[i];

}

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

{

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

{

maxst[j][i]=max(maxst[j-1][i],maxst[j-1][i+(1<<(j-1))]);

minst[j][i]=min(minst[j-1][i],minst[j-1][i+(1<<(j-1))]);

}

}

}

intgetmax(intl,intr)

{

intlen=r-l+1;

intk=log2n[len];

returnmax(maxst[k][l],maxst[k][r-(1<<k)+1]);

}

intgetmin(intl,intr)

{

intlen=r-l+1;

intk=log2n[len];

returnmin(minst[k][l],minst[k][r-(1<<k)+1]);

}

intmain()

{

scanf("%d%d",&n,&m);

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

{

scanf("%d",&a[i]);

sum[i]=sum[i-1]+a[i];

pass[i]=pass[i-1]+(a[i]>=60?1:0);

}

init();

while(m--)

{

intl,r;

scanf("%d%d",&l,&r);

intmx=getmax(l,r);

intmn=getmin(l,r);

doubleavg=1.0*(sum[r]-sum[l-1])/(r-l+1);

intcnt=pass[r]-pass[l-1];

printf("%d%d%.2f%d\n",mx,mn,avg,cnt);

}

return0;

}得分点说明50分：暴力遍历每个查询区间，可过小规模数据；80分：使用前缀和、前缀及格数组，暴力求最值，卡大数据时限；100分：ST表预处理区间最值，全程快读快输，无超时、无精度错误。第三题跳跃游戏（jump）【题目描述】给定一个长度为n的数组a，初始位置为下标1。在位置i时，你可以向后跳跃1∼a[i]步，即跳到i+1∼i+a[i]的任意位置。求从位置1跳到位置n的最少跳跃次数。保证一定可以到达终点。【输入格式】第一行一个整数n。第二行n个正整数，为数组a。【输出格式】一行一个整数，表示最少跳跃次数。【输入样例】72311421【输出样例】2【样例解释】1→2→7，两次跳跃即可到达终点。【数据范围】对于60%的数据：n≤1000对于100%的数据：1≤n≤106【第三题详细题解】解题思路本题是经典贪心跳跃问题，动态规划会超时，最优解法为线性贪心：1.维护三个变量：当前跳跃边界now、最远可达位置maxr、跳跃次数ans；2.遍历每个位置，实时更新最远可达位置；3.当遍历到当前边界now时，说明需要进行一次跳跃，更新边界为最远可达位置，次数+1；4.到达终点时终止遍历，输出答案。该算法时间复杂度O(n)，可通过百万级大数据。满分代码（C++）cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

constintMAXN=1e6+10;

inta[MAXN];

intmain()

{

ios::sync_with_stdio(false);

cin.tie(0);

intn;

cin>>n;

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

cin>>a[i];

intmaxr=0,now=1,ans=0;

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

{

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

if(i==now)

{

ans++;

now=maxr;

if(now>=n)break;

}

}

cout<<ans<<endl;

return0;

}得分点说明60分：动态规划DP解法，O(n100分：线性贪心算法，优化输入输出，适配大数据范围。第四题树上染色（tree）【题目描述】给定一棵有n个节点的无根树，所有节点初始为白色。现在进行k次操作，每次操作选择一个节点，将该节点以及其所有相邻节点染为黑色。求所有操作完成后，树上剩余的白色节点数量。【输入格式】第一行两个整数n,k。接下来n−1行，每行两个整数u,v，表示树的一条边。最后一行k个整数，表示每次操作选择的节点。【输出格式】一行一个整数，表示最终白色节点数量。【输入样例】51122324452【输出样例】1【样例解释】选中节点2，染色节点为1、2、3、4，仅剩节点5为白色，答案为1。【数据范围】对于40%的数据：n≤1000对于70%的数据：n≤对于100%的数据：1≤n≤2×105【第四题详细题解】解题思路本题为基础树上模拟题，核心是标记染色节点，去重统计：1.建立邻接表存储整棵树；2.开设布尔数组记录节点是否被染色；3.遍历所有操作节点，若节点已染色则跳过（避免重复操作）；4.对未染色的操作节点，将自身和所有邻接节点标记为黑色；5.最后统计未被标记的白色节点总数即可。关键点：重复操作同一节点不会产生额外效果，需要去重优化，避免无效遍历超时。满分代码（C++）cpp

#include<iostream>

#include<vector>

usingnamespacestd;

constintMAXN=2e5+10;

vector<int>edge[MAXN];

boolvis[MAXN];

boolop[MAXN];

intmain()

{

ios::sync_with_stdio(false);

cin.tie(0);

intn,k;

cin>>n>>k;

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

{

intu,v;

cin>>u>>v;

edge[u].push_back(v);

edge[v].push_back(u);

}

//读取操作节点并去重

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