NOI竞赛高频试题和详细答案

NOI竞赛高频试题和详细答案考试时间：______分钟总分：______分姓名：______选择题（每题2分，共10分）1.在动态规划中，状态设计的核心原则是？A.最优子结构B.无后效性C.状态转移方程D.以上都是2.Dijkstra算法用于求解？A.单源最短路径B.多源最短路径C.最小生成树D.最大流3.线段树的主要应用是？A.字符串匹配B.区间查询与修改C.图遍历D.排序4.KMP算法中的next数组用于？A.字符串反转B.字符串匹配C.最长公共子串D.字典序排序5.在搜索算法中，剪枝的主要目的是？A.减少搜索空间B.增加搜索深度C.提高正确率D.简化代码多选题（每题3分，共9分）1.以下哪些属于动态规划的高频考点？A.线性DPB.区间DPC.树形DPD.贪心算法2.以下哪些数据结构支持区间查询？A.线段树B.树状数组C.链表D.哈希表3.NOI竞赛中，试题的特点包括？A.核心考点高度聚焦B.问题设计强调建模能力C.算法复杂度要求严格D.细节考察全面深入填空题（每空1分，共10分）1.在动态规划中，状态转移方程需要满足______和______两个核心性质。2.Kruskal算法用于求解______，使用______数据结构实现。3.线段树的懒标记用于______，以避免重复计算。4.KMP算法中，next[i]表示模式串中前i个字符的______。5.在搜索中，迭代加深结合______策略，用于深度受限的搜索。编程题（共71分）1.任务调度问题（25分）：给定n个任务，每个任务有开始时间sᵢ、结束时间eᵢ、收益wᵢ。选择不重叠的任务，使总收益最大。写出动态规划的代码框架（伪代码或C++）。2.最小生成树变形（23分）：给定无向图，选择边使所有点度数为偶数且边权和最小。写出算法步骤。3.区间查询与修改（23分）：给定数组，支持区间加x和查询区间最大值。写出线段树的伪代码。试卷答案选择题1.D.以上都是解析思路：动态规划的状态设计必须满足最优子结构（子问题的解能组合成原问题的最优解）、无后效性（当前状态只依赖于之前的状态，不依赖于未来状态）和状态转移方程（定义状态之间的转移关系），因此所有选项都是核心原则。2.A.单源最短路径解析思路：Dijkstra算法专门用于计算从一个起点到所有其他顶点的最短路径，适用于非负权图；多源最短路径用Floyd算法，最小生成树用Prim或Kruskal，最大流用Ford-Fulkerson或Dinic算法。3.B.区间查询与修改解析思路：线段树是一种高效处理区间查询（如最大值、最小值、和）和区间修改（如加法、赋值）的数据结构，时间复杂度为O(logn)；字符串匹配用KMP或AC自动机，图遍历用BFS或DFS，排序用快速排序等算法。4.B.字符串匹配解析思路：KMP算法利用next数组（部分匹配表）来避免不必要的字符比较，提高字符串匹配的效率，时间复杂度O(n)；字符串反转用简单操作，最长公共子串用动态规划或后缀数组，字典序排序用排序算法。5.A.减少搜索空间解析思路：剪枝通过排除不可能的搜索路径，减少需要探索的状态数量，从而优化搜索效率，避免超时；增加搜索深度可能增加时间，提高正确率不是直接目的，简化代码不是主要目的。多选题1.A.线性DP,B.区间DP,C.树形DP解析思路：动态规划的高频考点包括线性DP（如背包问题）、区间DP（如矩阵连乘）、树形DP（如树的直径）；贪心算法是独立方法，不属于动态规划范畴。2.A.线段树,B.树状数组解析思路：线段树支持区间查询（如最大值、和）和区间修改；树状数组支持前缀和查询和单点修改，可转化为区间查询；链表不支持高效区间查询（需O(n)），哈希表不支持区间查询操作。3.A.核心考点高度聚焦,B.问题设计强调建模能力,C.算法复杂度要求严格,D.细节考察全面深入解析思路：NOI试题聚焦核心算法（如DP、图论），要求将实际问题抽象为算法模型，严格限制算法复杂度（避免超时），并考察代码实现的细节（如边界条件、数据溢出）。填空题1.最优子结构,无后效性解析思路：动态规划的状态转移方程必须满足最优子结构（问题的最优解由子问题的最优解构成）和无后效性（当前状态只依赖于之前的状态，不依赖于未来状态）。2.最小生成树,并查集解析思路：Kruskal算法通过贪心策略选择最小边构建最小生成树，使用并查集来管理连通分量，高效检测环。3.延迟更新解析思路：懒标记用于延迟区间更新操作，只在需要时下传更新，避免重复计算，提高效率。4.最长公共前后缀长度解析思路：next[i]表示模式串中前i个字符的最长相等前后缀的长度（不包括整个字符串），用于在匹配失败时跳过不必要的比较。5.剪枝解析思路：迭代加深通过限制搜索深度，结合剪枝策略（如A*算法）来优化搜索效率，避免无限深度搜索。编程题1.任务调度问题（25分）：```cpp#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;structTask{ints,e,w;};boolcmp(constTask&a,constTask&b){returna.e<b.e;}intmain(){intn;cin>>n;vector<Task>tasks(n);for(inti=0;i<n;i++){cin>>tasks[i].s>>tasks[i].e>>tasks[i].w;}sort(tasks.begin(),tasks.end(),cmp);vector<int>dp(n+1,0);for(inti=1;i<=n;i++){ints_i=tasks[i-1].s,w_i=tasks[i-1].w;intj=lower_bound(tasks.begin(),tasks.begin()+i-1,Task{0,s_i,0},cmp)-tasks.begin();dp[i]=max(dp[i-1],dp[j]+w_i);}cout<<dp[n]<<endl;return0;}```解析思路：将任务按结束时间排序；定义dp[i]为前i个任务的最大收益；对于每个任务i，找到最后一个不重叠的任务j（使用二分查找），dp[i]=max(dp[i-1],dp[j]+w_i)；最终dp[n]为答案。2.最小生成树变形（23分）：1.检查原图连通性，若不连通则无解；2.求原图的最小生成树（MST）；3.在MST中标记所有奇数度点；4.若奇数度点数量为奇数，则无解；5.对奇数度点进行最小权匹配（如贪心或最小费用流），将匹配路径上的边加入MST；6.输出最终MST的边权和。解析思路：问题转化为使所有点度数为偶数（欧拉回路），通过最小生成树和最小权匹配实现；步骤确保连通性、奇数度点配对，并最小化边权和。3.区间查询与修改（23分）：```cppstructNode{intl,r,max_val,lazy;};voidbuild(intnode,intl,intr,vector<int>&arr){tree[node].l=l;tree[node].r=r;if(l==r){tree[node].max_val=arr[l];return;}intmid=(l+r)/2;build(node*2,l,mid,arr);build(node*2+1,mid+1,r,arr);tree[node].max_val=max(tree[node*2].max_val,tree[node*2+1].max_val);}voidpush_down(intnode){if(tree[node].lazy!=0){tree[node*2].max_val+=tree[node].lazy;tree[node*2].lazy+=tree[node].lazy;tree[node*2+1].max_val+=tree[node].lazy;tree[node*2+1].lazy+=tree[node].lazy;tree[node].lazy=0;}}voidupdate(intnode,intl,intr,intx){if(tree[node].l>=l&&tree[node].r<=r){tree[node].max_val+=x;tree[node].lazy+=x;return;}push_down(node);intmid=(tree[node].l+tree[node].r)/2;if(l<=mid)update(node*2,l,r,x);if(r>mid)update(node*2+1,l,r,x);tree[node].max_val=max(tree[node*2].max_val,tree[node*2+1].max_val);}intquery(intnode,intl,intr){if(tree[node].l>=l&&tree[node].r<=r){returntree[node].max_val;}push_down(node);intmid=(tree[node].l