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

NOIP2026全国青少年信息学奥林匹克联赛提高组复赛试题与详细题解考试说明1.试题共四道，满分400分，考试时间：3小时。2.程序文件名、输入输出文件名严格按照题目要求，大小写敏感。3.所有题目均为标准输入、标准输出，不读、写文件。4.允许使用C++、Pascal语言，禁止使用Python及其他高级语言。5.答案必须严格对应题目要求，输出格式错误不予得分。第一题区间求和（sum）题目描述给定一个长度为n的整数序列a1,a每次询问给出两个整数l,r，求区间[l,r]内所有正数的和。输入格式第一行两个正整数n,m。第二行n个整数，表示序列a。接下来m行，每行两个整数l,r。输出格式对于每个询问，输出一行一个整数，表示对应区间正数和。数据范围1≤n,m≤−1≤l≤r≤n样例输入PlainText

53

1-2305

15

24

35样例输出PlainText

9

3

8题解思路本题为经典前缀和模板题。因为数据范围达到105预处理数组：新建数组s，令s[i]表示前i个数中所有正数的和，负数和0直接不计入。预处理公式：s[i]=s[i−1]+(a[i]>0?a[i]:0)。查询公式：区间[l,r]答案为s[r]−s[l−1]。满分C++代码PlainText

#include<iostream>

usingnamespacestd;

typedeflonglongll;

constintN=1e5+10;

lls[N];

inta[N];

intn,m;

intmain(){

ios::sync_with_stdio(false);

cin.tie(0);

cin>>n>>m;

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

cin>>a[i];

s[i]=s[i-1];

if(a[i]>0)s[i]+=a[i];

}

while(m--){

intl,r;

cin>>l>>r;

cout<<s[r]-s[l-1]<<'\n';

}

return0;

}第二题合法序列（seq）题目描述如果一个整数序列满足：序列中任意两个相邻数字的差值绝对值不超过1，则称该序列为合法序列。给定两个整数n,k，求长度为n、每个元素取值在[1,k]之间的合法序列总数量。答案对998244353取模。输入格式一行两个整数n,k。输出格式输出一个整数，表示合法序列数量。数据范围1≤n≤10001≤k≤1000样例输入1PlainText

22样例输出1PlainText

4解释：合法序列为[1,1],[1,2],[2,1],[2,2]，共4种。样例输入2PlainText

33样例输出2PlainText

21题解思路本题为动态规划基础题。状态定义：设dp[i][j]表示长度为i，最后一位数字为j的合法序列数量。初始状态：长度为1时，所有数字都合法，dp[1][j]=1(1≤j≤k)。转移方程：对于第i位取j，前一位可以取j−1、j、dp[i][j]=dp[i−1][j−1]+dp[i−1][j]+dp[i−1][j+1]（边界特判）最终答案：j=1k满分C++代码PlainText

#include<iostream>

usingnamespacestd;

constintMOD=998244353;

constintN=1010;

longlongdp[N][N];

intn,k;

intmain(){

cin>>n>>k;

for(inti=1;i<=k;i++)dp[1][i]=1;

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

for(intj=1;j<=k;j++){

dp[i][j]=dp[i-1][j];

if(j>1)dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD;

if(j<k)dp[i][j]=(dp[i][j]+dp[i-1][j+1])%MOD;

}

}

longlongans=0;

for(inti=1;i<=k;i++)ans=(ans+dp[n][i])%MOD;

cout<<ans<<endl;

return0;

}第三题最短路径（path）题目描述给定一张n个点、m条边的无向连通带权图，边权为正整数。定义特殊路径：从1号点出发，到达n号点，且路径中最多经过2条边权为偶数的边。求满足条件的特殊路径的最短长度。保证至少存在一条合法路径。输入格式第一行两个整数n,m。接下来m行，每行三个整数u,v,w，表示u,v之间有一条权值为w的无向边。输出格式输出一个整数，表示最短特殊路径长度。数据范围1≤n≤10001≤m≤50001≤w≤1000样例输入PlainText

45

122

244

133

345

231样例输出PlainText

6解释：路径1-2-4，经过2条偶边，长度2+4=6，为合法最短路径。题解思路本题为分层最短路经典模型。普通最短路无法记录偶边使用次数，需要增加一维状态记录已使用的偶边数量。状态设计：dis[x][t]表示到达点x，已经使用t条偶边的最短距离，其中t∈{0,1,2}。跑Dijkstra算法，遍历每条边时判断边权奇偶：1.边权为奇数：不改变t，直接松弛；2.边权为偶数：仅当t<2时可以走，t+1状态松弛。最终答案取dis[n][0],dis[n][1],dis[n][2]中的最小值。满分C++代码PlainText

#include<iostream>

#include<vector>

#include<queue>

#include<cstring>

usingnamespacestd;

typedeflonglongll;

constintINF=0x3f3f3f3f;

constintN=1010;

structEdge{

intto,w;

};

vector<Edge>g[N];

intdis[N][3];

intn,m;

structNode{

intpos,t,val;

booloperator<(constNode&x)const{

returnval>x.val;

}

};

intmain(){

cin>>n>>m;

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

intu,v,w;

cin>>u>>v>>w;

g[u].push_back({v,w});

g[v].push_back({u,w});

}

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

priority_queue<Node>q;

dis[1][0]=0;

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

while(!q.empty()){

Nodenow=q.top();

q.pop();

intu=now.pos;

intt=now.t;

intd=now.val;

if(d>dis[u][t])continue;

for(autoe:g[u]){

intv=e.to;

intw=e.w;

if(w%2==1){

if(dis[v][t]>d+w){

dis[v][t]=d+w;

q.push({v,t,dis[v][t]});

}

}else{

if(t<2&&dis[v][t+1]>d+w){

dis[v][t+1]=d+w;

q.push({v,t+1,dis[v][t+1]});

}

}

}

}

intans=min(min(dis[n][0],dis[n][1]),dis[n][2]);

cout<<ans<<endl;

return0;

}第四题子树统计（tree）题目描述给定一棵以1为根的n个节点的有根树，每个节点拥有一个权值val[i]。对于每个节点u，定义其合法子树为：以u为根的子树中，k所有节点权值的最大值与最小值的差值不超过。求整棵树中，满足上述条件的极大合法子树的数量。极大合法子树定义：该子树合法，且不存在其祖先节点对应的合法子树包含它。输入格式第一行两个整数n,k。第二行n个整数val[1..n]。接下来n−1行，每行两个整数u,v，表示树边。输出格式输出一个整数，表示极大合法子树的数量。数据范围1≤n≤20000≤k≤0≤val[i]≤样例输入PlainText

52

12321

12

13

24

25样例输出PlainText

2解释：节点2的子树合法、节点3的子树合法，且二者均无法被更大的合法子树包含，共计2个。题解思路本题为树上枚举+贪心统计，适配n=2000的O(n核心思路：1.先DFS预处理每个节点u的子树内的最大值、最小值，判断子树是否合法；2.极大性判定：若节点u的子树合法，且其父亲节点的子树不合法，则u对应的子树是极大合法子树；3.根节点特殊判定：若根子树合法，直接计入答案。算法流程：两次DFS，第一次统计每个子树的最值与合法性，第二次遍历所有节点统计极大合法子树数量。满分C++代码PlainText

#include<iostream>

#include<vector>

#include<algorithm>

usingnamespacestd;

constintN=2010;

constintINF=0x3f3f3f3f;

vector<int>g[N];

intval[N];

intmaxn[N],minn[N];

boolok[N];

intn,k,ans;

voiddfs(intu,intfa){

maxn[u]=val[u];

minn[u]=val[u];

for(intv:g[u]){

if(v==fa)continue;

dfs(v,u);

maxn[u]=max(maxn[u],maxn[v]);

minn[u]=min(minn[u],minn[v]);

}

if(maxn[u]-minn[u]<=k)ok[u]=true;

elseok[u]=false;

}

voidcalc(intu,intfa){

if(ok[u]){

if(fa==0||!ok[fa])ans++;

}

for(intv:g[u]){

if(v==fa)continue;

calc(v,u);

}

}

intmain(){

cin>>n>>k;

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

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

intu,v;

cin>>u>>v;

g[u].push_back(v);