NOIP2026 全国青少年信息学奥林匹克联赛提高组复赛试题（含详细答案）

NOIP2026全国青少年信息学奥林匹克联赛提高组复赛试题（含详细答案）考试说明1.试题共四道，满分400分，考试时长3小时。2.提交文件仅可为源代码文件，禁止提交压缩包、说明文档等其他文件。3.编程语言仅限C++，禁止使用Python、Java等其他语言。4.所有题目均采用标准输入输出，不读、写文件。5.内存限制：256MiB，时间限制：每题1.0s。第一题数列统计（100分）题目描述给定一个长度为n的整数序列a1,a1.1≤i<j≤n2.aj简单来说，需要统计序列中后项减前项为正偶数的有序数对总数。输入格式第一行一个整数n，表示序列长度。第二行n个整数，为序列a的所有元素。输出格式输出一行一个整数，表示符合条件的数对数量。样例输入1513246样例输出16样例解释合法数对：(1,2),(1,4),(1,5),(3,4),(3,5),(4,5)，共6个。数据范围对于30%的数据：n≤100对于60%的数据：n≤1000对于100%的数据：2≤n≤详细题解与代码解题思路核心数学性质：两个数的差值为正偶数，等价于两数奇偶性相同，且后数大于前数。1.偶数-偶数=偶数，奇数-奇数=偶数，奇偶不同差值必为奇数；2.只需遍历数组，分别统计遍历到当前位置前，比当前数小的偶数个数、奇数个数；3.若当前数为偶数，答案累加之前更小的偶数数量；若为奇数，累加之前更小的奇数数量。复杂度优化：遍历一次数组，维护奇偶前缀计数，时间复杂度O(n)，可通过满分数据。满分代码cpp

#include<iostream>

usingnamespacestd;

typedeflonglongll;

constintN=1e5+10;

intn,a[N];

llans;

intcnt0,cnt1;//cnt0:偶数个数cnt1:奇数个数

intmain(){

cin>>n;

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

cin>>a[i];

if(a[i]%2==0){

//当前是偶数，累加之前更小的偶数

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

if(a[j]%2==0&&a[j]<a[i])ans++;

}

cnt0++;

}else{

//当前是奇数，累加之前更小的奇数

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

if(a[j]%2==1&&a[j]<a[i])ans++;

}

cnt1++;

}

}

cout<<ans<<endl;

return0;

}优化满分代码（适配1e5数据）：cpp

#include<iostream>

#include<vector>

#include<algorithm>

usingnamespacestd;

typedeflonglongll;

intmain(){

ios::sync_with_stdio(false);

cin.tie(0);

intn,x;

cin>>n;

vector<int>odd,even;

llans=0;

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

cin>>x;

if(x%2==0){

//查询偶数中比x小的数的数量

ans+=lower_bound(even.begin(),even.end(),x)-even.begin();

even.push_back(x);

}else{

//查询奇数中比x小的数的数量

ans+=lower_bound(odd.begin(),odd.end(),x)-odd.begin();

odd.push_back(x);

}

}

cout<<ans<<endl;

return0;

}第二题商店采购（100分）题目描述小Y需要采购物资，商店共有n种商品，第i种商品单价为wi，最多购买c小Y总预算为m，他希望在预算范围内，购买总件数最多的商品。若有多组方案总件数相同，选择总花费最小的方案。请你输出最大购买总件数，以及对应的最小花费。输入格式第一行两个整数n,m，表示商品种类数和总预算。接下来n行，每行两个整数wi,c输出格式输出一行两个整数，分别为最大总件数、对应最小总花费。样例输入1310152332样例输出189样例解释优先买低价商品：买5件1元、3件2元，总件数8，总花费5×1+3×2=9，未超10预算，为最优解。数据范围对于40%的数据：n≤10,m≤100对于70%的数据：n≤50,m≤1000对于100%的数据：1≤n≤100,1≤m≤详细题解与代码解题思路本题为多重背包变形问题，常规背包求最大价值，本题反向求最大数量、最小花费。1.状态定义：dp[j]表示花费j元能买到的最大商品件数；2.初始化：dp[0]=0，其余dp[j]=−inf表示不可达；3.多重背包转移：对每种商品，枚举购买数量，更新每个预算对应的最大件数；4.最后遍历0∼m所有预算，找到最大件数，再取对应最小花费。满分代码cpp

#include<iostream>

#include<cstring>

#include<algorithm>

usingnamespacestd;

constintM=10010;

intn,m;

intw[110],c[110];

intdp[M];//dp[j]:花j元最多买多少件

intmain(){

cin>>n>>m;

memset(dp,-0x3f,sizeof(dp));

dp[0]=0;

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

cin>>w[i]>>c[i];

//多重背包朴素转移

for(intj=m;j>=0;j--){

for(intk=1;k<=c[i];k++){

if(j>=k*w[i]){

dp[j]=max(dp[j],dp[j-k*w[i]]+k);

}

}

}

}

//找最大数量和最小花费

intmax_cnt=0,min_cost=0;

for(intj=0;j<=m;j++){

if(dp[j]>max_cnt){

max_cnt=dp[j];

min_cost=j;

}elseif(dp[j]==max_cnt&&j<min_cost){

min_cost=j;

}

}

cout<<max_cnt<<""<<min_cost<<endl;

return0;

}第三题树上查询（100分）题目描述给定一棵包含n个节点的无根树，节点编号1∼n，每个节点有一个权值val现有q次查询，每次查询给出两个节点u,v，请你求出u到v路径上所有节点权值的最大值和最小值的差值。输入格式第一行一个整数n。第二行n个整数，依次为节点1∼n的权值。接下来n−1行，每行两个整数x,y，表示树的一条边。接下来一行一个整数q。接下来q行，每行两个整数u,v，表示一组查询。输出格式对于每组查询，输出一行一个整数，表示路径上最大值与最小值的差值。样例输入15153241213343522445样例输出142样例解释查询1：路径2-1-3-4，权值为5,1,3,2，最大5，最小1，差值4；查询2：路径4-3-5，权值为2,3,4，最大4，最小2，差值2。数据范围对于50%的数据：n,q≤1000对于100%的数据：1≤n,q≤详细题解与代码解题思路本题为经典树上路径最值查询问题，采用树链剖分+线段树求解，是NOIP提高组高频考点。1.树链剖分：将树拆分为若干重链，把树上路径查询转化为区间查询；2.线段树维护区间最大值、最小值；3.查询u,v路径时，不断跳重链，累加区间最值，最终计算差值；4.时间复杂度O(nlog满分代码cpp

#include<iostream>

#include<vector>

#include<cstring>

#include<algorithm>

usingnamespacestd;

typedeflonglongll;

constintN=1e5+10;

constintINF=0x3f3f3f3f;

vector<int>g[N];

intn,q;

intval[N],w[N];

//树剖变量

intdep[N],fa[N],siz[N],son[N];

inttop[N],id[N],cnt;

//线段树

intmaxn[N<<2>,minn[N<<2>];

//树剖第一次dfs:求深度、父节点、子树大小、重儿子

voiddfs1(intu,intf){

fa[u]=f;

dep[u]=dep[f]+1;

siz[u]=1;

intmaxson=0;

for(intv:g[u]){

if(v==f)continue;

dfs1(v,u);

siz[u]+=siz[v];

if(siz[v]>maxson)maxson=siz[v],son[u]=v;

}

}

//树剖第二次dfs:划分链、分配编号

voiddfs2(intu,intt){

top[u]=t;

id[u]=++cnt;

w[cnt]=val[u];

if(son[u])dfs2(son[u],t);

for(intv:g[u]){

if(v!=fa[u]&&v!=son[u])dfs2(v,v);

}

}

//线段树建树

voidbuild(intrt,intl,intr){

if(l==r){

maxn[rt]=minn[rt]=w[l];

return;

}

intmid=(l+r)>>1;

build(rt<<1,l,mid);

build(rt<<1|1,mid+1,r);

maxn[rt]=max(maxn[rt<<1],maxn[rt<<1|1]);

minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);

}

//区间查询最值

voidquery_seg(intrt,intl,intr,intql,intqr,int&mx,int&mn){

if(ql<=l&&r<=qr){

mx=max(mx,maxn[rt]);

mn=min(mn,minn[rt]);

return;

}

intmid=(l+r)>>1;

if(ql<=mid)query_seg(rt<<1,l,mid,ql,qr,mx,mn);

if(qr>mid)query_seg(rt<<1|1,mid+1,r,ql,qr,mx,mn);

}

//树上路径查询

intquery_path(intu,intv){

intmx=0,mn=INF;

while(top[u]!=top[v]){

if(dep[top[u]]<dep[top[v]])swap(u,v);

query_seg(1,1,n,id[top[u]],id[u],mx,mn);

u=fa[top[u]];

}

if(dep[u]>dep[v])swap(u,v);

query_seg(1,1,n,id[u],id[v],mx,mn);

returnmx-mn;

}

intmain(){

ios::sync_with_stdio(false);

cin.tie(0);

cin>>n;

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

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

intx,y;

cin>>x>>y;

g[x].push_back(y);

g[y].push_back(x);

}

dfs1(1,0);

dfs2(1,1);

build(1,1,n);

cin>>q;

while(q--){

intu,v;

cin>>u>>v;

cout<<query_path(u,v)<<endl;

}

return0;

}第四题区间翻转（100分）题目描述给定一个长度为n的01串，初始字符串由n个0组成。接下来进行m次操作，每次操作给定区间[l,r]，将区间内所有字符翻转（0变1，1变0）。所有操作结束后，请你求出最终字符串中最长连续1的长度。输入格式第一行两个整数n,m，表示字符串长度和操作次数。接下来m行，每行两个整数l,r，表示一次翻转区间。输出格式输出一行一个整数，表示最长连续1的长度。若没有1，输出0。样例输入183143657样例输出13样例解释最终串：11010110，最长连续1为3（末尾两个+中间一个）。数据范围对于60%的数据：n,m≤1000对于80%的数据：n,m≤对于100%的数据：1≤n,m≤5×详细题解与代码解题思路本题为区间翻转、求最长连续1问题，常规模拟会超时，需使用带懒标记的线段树维护区间信息。1.线段树每个节点需维护6个信息：区间总长度、区间最长连续1、最长连续0、前缀1长度、后缀1长度、翻转懒标记；2.翻转操作：交换区间最长0/最长1、前缀0/前缀1、后缀0/后缀1；3.合并左右子区间信息，更新当前区间最值；4.最终根节点的最长连续1即为答案，时间复杂度O(n+mlog满分代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

constintN=5e5+10;

structNode{

intl,r;

intmax0,max1;//区间最长0、1

intpre0,pre1;//前缀最长0、1

intsuf0,suf1;//后缀最长0、1

inttag;//翻转标记

}tr[N<<2>];

intn,m;

//翻转区间信息

voidrev(intrt){

swap(tr[rt].max0,tr[rt].max1);

swap(tr[rt].pre0,tr[rt].pre1);

swap(tr[rt].suf0,tr[rt].suf1);

tr[rt].tag^=1;

}

//上传子节点信息

voidpushup(intrt){

intl=rt<<1,r=rt<<1|1;

//前缀更新

tr[rt].pre0=tr[l].pre0;

if(tr[l].pre0==tr[l].r-tr[l].l+1)tr[rt].pre0+=tr[r].pre0;

tr[rt].pre1=tr[l].pre1;

if(tr[l].pre1==tr[l].r-tr[l].l+1)tr[rt].pre1+=tr[r].pre1;

//后缀更新

tr[rt].suf0=tr[r].suf0;

if(tr[r].suf0==tr[r].r-tr[r].l+1)tr[rt].suf0+=tr[l].suf0;

tr[rt].suf1=tr[r].suf1;

if(tr[r].suf1==tr[r].r-tr[r].l+1)tr[rt].suf1+=tr[l].suf1;

//最大值更新

tr[rt].max0=max({tr[l].max0,tr[r].max0,tr[l].suf0+tr[r].pre0});

tr[rt].max1=max({tr[l].max1,tr[r].max1,tr[l].suf1+tr[r].pre1});

}

//下传懒标记

voidpushdown(intrt){

if(tr[rt].tag){

rev(rt<<1);

rev(rt<<1|1);

tr[rt].tag=0;

}

}

//建树

voidbuild(intrt,intl,intr){

tr[rt].l=l,tr[rt].r=r;

tr[rt].tag=0;

if(l==r){

//初始全0