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

NOIP2026全国青少年信息学奥林匹克联赛提高组复赛试题考试时间：2026年11月15日14:30-17:30试题总分：400分答题要求：1.严格按照题目要求编写程序，文件名、输入输出格式必须与题目规定完全一致，否则不予得分。2.程序禁止使用任何私有函数、特殊编译器扩展，仅可使用C++标准库常规头文件。3.所有题目均为标准输入、标准输出，不读写文件。4.内存限制均为256MB，时间限制均为1s，特殊说明除外。第一题数列求值（100分）题目描述给定一个正整数n，定义数列a满足：a当k≥3时，a求该数列第n项的值。输入格式一行一个正整数n。输出格式一行一个整数，表示an数据范围对于30%的数据，1≤n≤10对于60%的数据，1≤n≤1000对于100%的数据，1≤n≤样例输入15样例输出116样例解释a第二题摊位规划（100分）题目描述一条笔直的街道上有n个可供摆摊的位置，编号为1到n。现在有若干商贩想要摆摊，规定：任意两个摊位之间的距离不能小于k（位置差值的绝对值≥k）。已知每个位置摆摊可以获得对应的收益wi输入格式第一行两个整数n,k。第二行n个整数，依次为w1输出格式一行一个整数，表示最大总收益。数据范围对于40%的数据，n≤20对于70%的数据，n≤1000对于100%的数据，1≤n≤样例输入15235172样例输出112样例解释选择位置2和位置4，收益5+7=12，满足间距≥2的限制。第三题连通块统计（100分）题目描述给定一张n个点、m条边的无向简单图，初始所有点均为白色。现在进行q次操作，每次操作将一个点的颜色翻转（白变黑、黑变白）。每次操作结束后，请统计图中黑色点构成的连通块数量。连通块定义：仅由黑色点组成，通过边直接或间接相连的极大点集。孤立的黑色单点视为一个连通块，白色点不参与连通。输入格式第一行三个整数n,m,q。接下来m行，每行两个整数u,v，表示一条无向边。接下来q行，每行一个整数x，表示翻转点x的颜色。输出格式共q行，每行一个整数，对应每次操作后的连通块数量。数据范围对于30%的数据，n≤100,q≤100对于60%的数据，n≤1000,q≤1000对于100%的数据，1≤n,m,q≤样例输例输出1112样例解释第一次翻转：点1变黑，连通块数1；第二次翻转：点2变黑，1、2连通，连通块数1；第三次翻转：点1变白，剩余点2黑色，连通块数1（更正：最终黑点点2、3，连通，输出1，样例输出无误）。第四题字符串拆分（100分）题目描述给定一个仅包含小写字母的字符串S，长度为n。你需要将字符串拆分为若干个连续非空子串，满足：拆分后的每一个子串，都不存在相邻且相同的字符。求合法拆分的方案总数，答案对998244353取模。输入格式一行一个字符串S。输出格式一行一个整数，表示合法拆分方案数对998244353取模的结果。数据范围对于50%的数据，n≤1000对于100%的数据，1≤n≤样例输入1aba样例输出14样例解释四种合法拆分：[a,b,a]、[a,ba]、[ab,a]、[aba]，所有子串均无相邻相同字符。样例输入2aab样例输出22NOIP2026提高组复赛详细答案与解析第一题数列求值题解解题思路本题为基础递推题，核心难点是处理n≤10根据递推公式，每次仅需要前两项的值，无需开数组存储全部数据，仅用两个变量滚动更新即可，空间复杂度O(1)，时间复杂度O(n)，可以轻松通过满分数据。全程对10000取模，避免数值溢出。满分代码cpp

#include<iostream>

usingnamespacestd;

constintMOD=10000;

intmain(){

intn;

cin>>n;

if(n==1){cout<<1;return0;}

if(n==2){cout<<2;return0;}

inta=1,b=2,c;

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

c=(b+2*a)%MOD;

a=b;

b=c;

}

cout<<b;

return0;

}第二题摊位规划题解解题思路本题为经典线性DP优化问题。1.状态定义：设dp[i]表示前i个位置的最大收益。2.状态转移：-不选第i个位置：dp[i]=dp[i−1]-选第i个位置：则前i−k个位置可任意选，dp[i]=dp[i−k]+w[i]3.朴素DP复杂度O(n2)，无法通过1e5数据，因此维护前缀最大值数组maxdp，maxdp[i]=max(dp[1…i])，将转移优化为O(1)满分代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

constintN=1e5+10;

longlongdp[N],maxdp[N];

intw[N];

intn,k;

intmain(){

cin>>n>>k;

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

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

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

if(i>k)dp[i]=max(dp[i],maxdp[i-k]+w[i]);

elsedp[i]=max(dp[i],1LL*w[i]);

maxdp[i]=max(maxdp[i-1],dp[i]);

}

cout<<dp[n];

return0;

}第三题连通块统计题解解题思路本题为图论离线动态连通性经典问题，核心是单点翻转、实时统计黑色连通块数。核心结论：黑色连通块数=黑色点总数-黑色点之间的有效边数。1.维护数组col[]记录每个点颜色，0为白，1为黑；2.维护变量cnt黑色点总数，edge黑色点间的边数；3.翻转点x时：-若变白：遍历所有邻边，统计相邻黑点数量，从edge中减去对应数量，cnt--；-若变黑：cnt++，遍历所有邻边，统计相邻黑点数量，edge加上对应数量；4.每次操作后答案即为cnt−edge。整体复杂度O(n+m+q)，可通过全部数据。满分代码cpp

#include<iostream>

#include<vector>

usingnamespacestd;

constintN=1e5+10;

vector<int>g[N];

boolcol[N];

intn,m,q;

intcnt,edge;

intmain(){

ios::sync_with_stdio(false);

cin.tie(0);

cin>>n>>m>>q;

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

intu,v;cin>>u>>v;

g[u].push_back(v);

g[v].push_back(u);

}

while(q--){

intx;cin>>x;

if(col[x]){

//变黑变白

col[x]=0;

cnt--;

for(inty:g[x]){

if(col[y])edge--;

}

}else{

//变白变黑

col[x]=1;

cnt++;

for(inty:g[x]){

if(col[y])edge++;

}

}

cout<<cnt-edge<<'\n';

}

return0;

}第四题字符串拆分题解解题思路本题为线性DP+前缀和优化，针对1e6长度字符串设计。1.状态定义：dp[i]表示前i个字符的合法拆分方案数。2.初始状态：dp[0]=1（空串有一种拆分方案）。3.转移条件：若当前位置s[i]!=s[i−1]，则可以直接承接前缀所有方案；若s[i]==s[i−1]，则不能将i−1与i放在同一子串，只能从合法前置位置转移。4.优化：维护前缀和数组，将O(n2)满分代码cpp

#include<iostream>

#include<string>

usingnamespacestd;

constintMOD=998244353;

constintN=1e6+10;

longlongdp[N],sum[N];

strings;

intmain(){

ios::sync_with_stdio(false);

cin.tie(0);

cin>>s;

intn=s.size();

dp[0]=1;

sum[0]=1;

intlast=0;

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

if(i>1&&s[i-1]==s[i-2])last=i-1;

if(last==0)dp[i]=sum[i-1]%MOD;

elsedp[i]=(sum[i-1]-sum