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

2026年全国青少年信息学奥林匹克联赛（NOIP）提高组试题及详细答案考试时间：2026年11月14日14:30-17:30满分：400分答题说明1.本次考试共四道题目，每题100分，总分400分；2.程序必须使用C++语言编写，禁止使用Python、Java等其他语言；3.输入输出严格按照题目要求，不得添加多余提示、空格、换行；4.所有题目无部分分特殊说明时，仅完全正确通过所有测试点可得满分。第一题数列统计（seq）题目描述给定一个长度为\(n\)的整数数列，所有元素均为正整数。定义合法数对\((i,j)\)满足：\(1\lei<j\len\)，且数列中第\(i\)项与第\(j\)项的最大公约数严格大于最小公倍数的一半。请你统计出数列中合法数对的总个数。输入格式第一行一个正整数\(n\)，表示数列长度。第二行\(n\)个正整数，为给定的数列。输出格式一行一个整数，表示合法数对的数量。数据范围对于30%的数据：\(n\le100\)，数列元素\(\le100\)对于60%的数据：\(n\le1000\)，数列元素\(\le1000\)对于100%的数据：\(2\len\le10^5\)，数列元素\(\le10^5\)样例输入1524639样例输出17题目解析首先化简核心条件：设两个数为\(a,b\)，记\(g=\gcd(a,b),l=\text{lcm}(a,b)\)。根据数论基础公式：\(a\timesb=g\timesl\)。题目条件为\(g>\frac{l}{2}\)，代入公式推导：\(2g>\frac{ab}{g}\implies2g^2>ab\)令\(a=gx,b=gy\)，此时\(\gcd(x,y)=1\)，代入得：\(2g^2>g^2xy\impliesxy<2\)。因为\(x,y\)为互质正整数，\(xy<2\)仅能满足\(xy=1\)，即\(x=y=1\)。由此可得核心结论：两个数合法的充要条件为两数相等。问题转化为：统计数列中每个数值出现的次数\(cnt[x]\)，对每个\(x\)计算组合数\(C(cnt[x],2)=\frac{cnt[x]\times(cnt[x]-1)}{2}\)，所有结果求和即为答案。满分代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

constintMAXN=1e5+5;

intcnt[MAXN],n,x;

longlongans;

intmain(){

cin>>n;

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

cin>>x;

cnt[x]++;

}

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

ans+=1LL*cnt[i]*(cnt[i]-1)/2;

}

cout<<ans<<endl;

return0;

}得分点说明1.30分：暴力枚举所有数对，验证原始条件，适合小数据；2.60分：优化暴力，预处理gcd、lcm，可通过千级数据；3.100分：数论推导结论，桶计数+组合求和，线性复杂度。第二题区间修改（modify）题目描述给定一个长度为\(n\)的初始全0序列，现有\(m\)次操作，操作分为两种：1.区间加法：给定\(l,r,k\)，将区间\([l,r]\)内所有数加上\(k\)；2.区间查询：给定\(l,r\)，查询区间\([l,r]\)内严格大于区间平均值的元素个数。请依次输出每次查询操作的结果。输入格式第一行两个整数\(n,m\)，分别表示序列长度和操作次数。接下来\(m\)行，每行首先一个整数\(op\)表示操作类型。若\(op=1\)，后跟三个整数\(l,r,k\)；若\(op=2\)，后跟两个整数\(l,r\)。输出格式对于每个查询操作，输出一行一个整数表示答案。数据范围对于40%的数据：\(n,m\le1000\)对于70%的数据：\(n,m\le10^4\)对于100%的数据：\(1\len,m\le10^5,1\lel\ler\len,1\lek\le100\)样例输入15311321254215样例输出13样例解释操作后序列为：\([2,6,6,4,4]\)，区间总和为22，平均值为4.4。严格大于4.4的元素为6、6，统计个数为3。题目解析核心公式推导：设查询区间长度为\(len=r-l+1\)，区间总和为\(sum\)，平均值为\(sum/len\)。元素\(a[x]>sum/len\)等价于\(a[x]\timeslen>sum\)，规避浮点数精度误差。题目需要维护区间加法、区间求和、区间内满足\(a[x]\timeslen>sum\)的元素个数，使用线段树+懒标记维护。线段树每个节点维护：区间和、区间最大值、区间最小值、加法懒标记。查询时二分统计合法元素：若区间最大值\(\timeslen\lesum\)，无合法元素；若区间最小值\(\timeslen>sum\)，全部合法；否则递归左右子树统计。满分代码cpp

#include<iostream>

#include<cstdio>

#include<algorithm>

usingnamespacestd;

typedeflonglongll;

constintMAXN=1e5+5;

structTree{

llsum,maxn,minn,lazy;

}tr[MAXN*4];

intn,m;

voidpushup(intp){

tr[p].sum=tr[p*2].sum+tr[p*2+1].sum;

tr[p].maxn=max(tr[p*2].maxn,tr[p*2+1].maxn);

tr[p].minn=min(tr[p*2].minn,tr[p*2+1].minn);

}

voidpushdown(intp,intl,intr){

if(tr[p].lazy==0)return;

intmid=(l+r)/2;

llk=tr[p].lazy;

//更新左子树

tr[p*2].sum+=k*(mid-l+1);

tr[p*2].maxn+=k;

tr[p*2].minn+=k;

tr[p*2].lazy+=k;

//更新右子树

tr[p*2+1].sum+=k*(r-mid);

tr[p*2+1].maxn+=k;

tr[p*2+1].minn+=k;

tr[p*2+1].lazy+=k;

tr[p].lazy=0;

}

voidupdate(intp,intl,intr,intul,intur,llk){

if(ur<l||ul>r)return;

if(ul<=l&&r<=ur){

tr[p].sum+=k*(r-l+1);

tr[p].maxn+=k;

tr[p].minn+=k;

tr[p].lazy+=k;

return;

}

pushdown(p,l,r);

intmid=(l+r)/2;

update(p*2,l,mid,ul,ur,k);

update(p*2+1,mid+1,r,ul,ur,k);

pushup(p);

}

llquery_sum(intp,intl,intr,intql,intqr){

if(qr<l||ql>r)return0;

if(ql<=l&&r<=qr)returntr[p].sum;

pushdown(p,l,r);

intmid=(l+r)/2;

returnquery_sum(p*2,l,mid,ql,qr)+query_sum(p*2+1,mid+1,r,ql,qr);

}

intquery_cnt(intp,intl,intr,intql,intqr,lllen,llsum){

if(qr<l||ql>r)return0;

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

if(tr[p].maxn*len<=sum)return0;

if(tr[p].minn*len>sum)returnr-l+1;

}

pushdown(p,l,r);

intmid=(l+r)/2;

returnquery_cnt(p*2,l,mid,ql,qr,len,sum)+query_cnt(p*2+1,mid+1,r,ql,qr,len,sum);

}

intmain(){

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

while(m--){

intop;

scanf("%d",&op);

if(op==1){

intl,r;llk;

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

update(1,1,n,l,r,k);

}else{

intl,r;

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

lllen=r-l+1;

llsum=query_sum(1,1,n,l,r);

intans=query_cnt(1,1,n,l,r,len,sum);

printf("%d\n",ans);

}

}

return0;

}得分点说明1.40分：暴力模拟，每次修改直接更新数组，查询遍历统计；2.70分：差分优化区间修改，查询暴力遍历，可通过万级数据；3.100分：线段树维护区间信息，二分统计合法个数，时间复杂度\(O(m\logn)\)。第三题最短路径（path）题目描述给定一张\(n\)个点、\(m\)条边的无向连通带权图，边权为正整数。定义特殊路径：从起点\(1\)到终点\(n\)的路径中，路径上最大边权与最小边权的差值最小的路径。请你求出该最小差值。输入格式第一行两个整数\(n,m\)，分别表示点数和边数。接下来\(m\)行，每行三个整数\(u,v,w\)，表示\(u,v\)之间有一条权值为\(w\)的无向边。输出格式一行一个整数，表示最短特殊路径的最小差值。数据范围对于50%的数据：\(n\le100,m\le500\)对于80%的数据：\(n\le500,m\le2000\)对于100%的数据：\(2\len\le1000,1\lem\le5000,1\lew\le10^5\)样例输入145121245133344232样例输出11样例解释最优路径为\(1\to2\to3\to4\)，路径边权为1、2、4，最大4，最小1，差值3；最优解为\(1\to3\to4\)，边权3、4，差值1。题目解析本题核心思路为边排序+并查集经典解法：1.将所有边按照边权从小到大排序；2.枚举每条边作为路径的最小边，不断向图中加入更大的边，用并查集维护连通性；3.当起点1与终点\(n\)连通时，当前加入的最大边与枚举的最小边的差值即为候选答案；4.遍历所有情况，取最小差值即为最终答案。该思路规避了暴力枚举路径的复杂开销，时间复杂度可完全覆盖题目数据范围。满分代码cpp

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

usingnamespacestd;

constintMAXN=1005,MAXM=5005,INF=0x3f3f3f3f;

structEdge{

intu,v,w;

booloperator<(constEdge&b)const{

returnw<b.w;

}

}e[MAXM];

intfa[MAXN];

intn,m,ans=INF;

intfind(intx){

if(fa[x]!=x)fa[x]=find(fa[x]);

returnfa[x];

}

intmain(){

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

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

scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

}

sort(e+1,e+m+1);

//枚举最小边

for(intl=1;l<=m;l++){

for(inti=1;i<=n;i++)fa[i]=i;

for(intr=l;r<=m;r++){

intu=e[r].u,v=e[r].v;

if(find(u)!=find(v)){

fa[find(u)]=find(v);

}

if(find(1)==find(n)){

ans=min(ans,e[r].w-e[l].w);

break;

}

}

}

printf("%d\n",ans);

return0;

}得分点说明1.50分：暴力搜索所有路径，统计每条路径的极值差值，取最小值；2.80分：优化搜索，记忆化部分状态，减少重复遍历；3.100分：排序+并查集双指针，高效求解最优差值。第四题树上选择（tree）题目描述给定一棵包含\(n\)个节点的无根树，每个节点有一个权值\(a[i]\)。现在需要选出若干节点，满足以下两个条件：1.选出的节点中，任意两个节点不相邻；2.选出的节点数量恰好为\(k\)。求满足条件的节点权值和的最大值，若无合法方案，输出-1。输入格式第一行两个整数\(n,k\)。第二行\(n\)个整数，第\(i\)个数表示节点\(i\)的权值\(a[i]\)。接下来\(n-1\)行，每行两个整数\(u,v\)，表示树上的一条边。输出格式一行一个整数，表示最大权值和，无方案输出-1。数据范围对于30%的数据：\(n\le20\)对于60%的数据：\(n\le100,k\le50\)对于100%的数据：\(1\len\le300,1\lek\len,-10^4\lea[i]\le10^4\)样例输入1521234512233445样例输出18样例解释最优选择为节点2和5，权值和为2+5=8，两节点不相邻，数量恰好为2。题目解析本题为树上背包DP经典题型，定义状态：\(dp[u][j][0]\)：以\(u\)为根的子树，选\(j\)个节点，不选\(u\)的最大权值和；\(dp[u][j][1]\)：以\(u\)为根的子树，选\(j\)个节点，选\(u\)的最大权值和。状态转移方程：1.选\(u\)时，子节点全部不能选：\(dp[u][j][1]=\max(dp[u][j][1],dp[u][j-1][0]+a[u])\)，子节点仅能取0状态；2.不选\(u\)时，子节点可选可不选：合并子树背包，取子节点两种状态的最大值。初始化所有DP值为负无穷，代表不合法状态，最终答案为\(\max(dp[1][k][0],dp[1][k][1])\)，若结果仍为负无穷则输出-1。满分代码cpp

#include<iostream>

#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

usingnamespacestd;

constintMAXN=305,INF=0x3f3f3f3f;

vector<int>g[MAXN];

intn,k,a[MAXN];

intdp[MAXN][MAXN][2];

intsiz[MAXN];

voiddfs(intu,intfa){

siz[u]=1;

dp[u][0][0]=0;

dp[u][1][1]=a[u];

for(intv:g[u]){

if(v==fa)continue;

dfs(v,u);

//反向背包更新，防止覆盖

for(intj=siz[u];j>=0;j--){

for(intt=siz[v];t>=0;t--){

//不选u，v可选可不选

dp[u][j+t][0]=max(