2026年noip竞赛知识点学习指南

2026年noip竞赛知识点学习指南一、算法设计（共3题，每题15分）1.（15分）字符串最小表示法问题给定一个字符串`S`，求它的最小表示。最小表示定义为：在所有`S`的循环移位中，字典序最小的那个。例如，`S="abcabc"`的最小表示为`"abcabc"`。输入格式：第一行一个字符串`S`（长度不超过1e5）。输出格式：输出`S`的最小表示。示例输入：abcabc示例输出：abcabc解析：直接输出字符串本身，因为它是字典序最小的循环移位。2.（15分）快速幂模运算给定三个正整数`a`、`b`、`c`，计算`(a^b)%c`的值。要求在时间复杂度`O(logb)`内完成计算。输入格式：第一行三个整数`a`、`b`、`c`。输出格式：输出`(a^b)%c`的值。示例输入：3101000示例输出：9解析：使用快速幂算法，将`b`拆分为二进制表示，逐位计算幂次方并取模。例如，`3^10=3^(8+2)=(3^8%1000)(3^2%1000)%1000=99%1000=81`。3.（15分）树的最大独立集问题给定一棵树（点数为`n`，边数为`n-1`），求其最大独立集的大小。最大独立集定义为：树中任意两个点不相连的点的最大集合。输入格式：第一行一个整数`n`（`2<=n<=1e5`），表示点数。接下来`n-1`行，每行两个整数`u`、`v`，表示一条无向边。输出格式：输出最大独立集的大小。示例输入：512133435示例输出：3解析：可以使用动态规划或贪心策略解决。对于每个节点，选择其子树中不相连的点，可以递归计算每个节点的最大独立集大小。二、数据结构（共2题，每题20分）1.（20分）线段树区间加与区间和查询给定一个长度为`n`的数组`nums`，支持两种操作：-`1lrx`：将`nums[l]`到`nums[r]`的元素都加`x`。-`2lr`：查询`nums[l]`到`nums[r]`的元素和。输入格式：第一行两个整数`n`、`m`，分别表示数组长度和操作次数。第二行`n`个整数，表示初始数组。接下来`m`行，每行一个操作，格式如上。输出格式：对于每个`2lr`操作，输出对应的区间和。示例输入：5512345113221412512141153示例输出：810解析：使用线段树维护区间加和区间和。第一个操作将`nums[1]`到`nums[3]`加`2`，数组变为`34545`；第二个查询`nums[1]`到`nums[4]`的和为`16`；第三个操作将`nums[2]`到`nums[5]`加`1`，数组变为`35646`；第四个查询`nums[1]`到`nums[4]`的和为`18`；第五个操作将`nums[1]`到`nums[5]`加`3`，数组变为`68979`；最后一个查询`nums[1]`到`nums[4]`的和为`30`。2.（20分）平衡树（Treap）的插入与查询给定一个Treap（合并为左倾红黑树或左倾Treap），支持两种操作：-`1x`：将`x`插入Treap。-`2x`：查询`x`在Treap中的前驱和后继。输入格式：第一行一个整数`n`，表示操作次数。接下来`n`行，每行一个操作，格式如上。输出格式：对于每个`2x`操作，输出`x`的前驱和后继的值（如果存在）。示例输入：6110120130225215235示例输出：203010202530解析：Treap的插入和查询操作基于优先级（随机生成）和BST性质。前驱是比`x`小的最大值，后继是比`x`大的最小值。例如，插入`10`、`20`、`30`后，前驱和后继分别为`20`和`30`；插入`25`后，前驱为`20`，后继为`30`；插入`15`后，前驱为`10`，后继为`20`；插入`35`后，前驱为`30`，后继不存在。三、图论（共3题，每题20分）1.（20分）最小生成树（Kruskal算法）给定一个无向连通图，边权可能为负数，但无负权环，求其最小生成树的总权值。输入格式：第一行两个整数`n`、`m`，表示点数和边数。接下来`m`行，每行三个整数`u`、`v`、`w`，表示一条边。输出格式：输出最小生成树的总权值。示例输入：45121233342132424示例输出：6解析：使用Kruskal算法，按边权排序并按顺序选择不形成环的边。选择`1-2`（权1）、`1-3`（权2）、`3-4`（权2），总权值为`6`。2.（20分）二分图最大匹配给定一个二分图（点集分为左部`U`和右部`V`，边集为`E`），求其最大匹配的大小。输入格式：第一行两个整数`m`、`n`，分别表示左部点和右部点的数量。接下来`e`行，每行两个整数`u`、`v`，表示一条从左部点`u`到右部点`v`的边。输出格式：输出最大匹配的大小。示例输入：4411122223333444示例输出：4解析：使用匈牙利算法或网络流算法求解。通过匹配所有点对，可以得到最大匹配大小为`4`。3.（20分）最短路径（Dijkstra算法）给定一个带权图，起点为`1`，终点为`n`，求最短路径长度。图可能包含负权边，但无负权环。输入格式：第一行两个整数`n`、`m`，表示点数和边数。接下来`m`行，每行三个整数`u`、`v`、`w`，表示一条从`u`到`v`权值为`w`的边。输出格式：输出从`1`到`n`的最短路径长度。示例输入：5612223-134345-21410351示例输出：3解析：使用Dijkstra算法，优先队列维护当前最短路径。路径`1-2-3-5`的总权值为`3`，是最短路径。四、综合应用（共2题，每题25分）1.（25分）动态规划：区间操作问题给定一个长度为`n`的数组`nums`，支持两种操作：-`1lrx`：将`nums[l]`到`nums[r]`的元素都加`x`。-`2q`：查询`nums[1]`到`nums[q]`的元素和。要求在`O(n+mlogn)`时间内完成所有操作。输入格式：第一行两个整数`n`、`m`，表示数组长度和操作次数。第二行`n`个整数，表示初始数组。接下来`m`行，每行一个操作，格式如上。输出格式：对于每个`2q`操作，输出对应的区间和。示例输入：5512345113223125124115325示例输出：81030解析：结合线段树和树状数组。线段树维护区间加，树状数组维护前缀和。第一个操作将`nums[1]`到`nums[3]`加`2`，数组变为`34545`；第二个查询`nums[1]`到`nums[3]`的和为`12`；第三个操作将`nums[2]`到`nums[5]`加`1`，数组变为`35656`；第四个查询`nums[1]`到`nums[4]`的和为`19`；第五个操作将`nums[1]`到`nums[5]`加`3`，数组变为`68989`；最后一个查询`nums[1]`到`nums[5]`的和为`30`。2.（25分）贪心算法：区间调度问题给定`n`个区间，每个区间为`[start_i,end_i]`，求最多能安排多少个不重叠的区间。输入格式：第一行一个整数`n`，表示区间数量。接下来`n`行，每行两个整数`start_i`、`end_i`。输出格式：输出最多能安排的不重叠区间数量。示例输入：6142536135768示例输出：3解析：按区间结束时间排序，贪心选择不与当前区间重叠的区间。排序后区间为`[1,3]`、`[1,4]`、`[2,5]`、`[3,6]`、`[5,7]`、`[6,8]`，选择`[1,3]`、`[5,7]`、`[6,8]`共`3`个不重叠区间。答案与解析算法设计1.示例输入输出已给出，最小表示法直接输出原串。2.示例输入输出已给出，快速幂模运算按位拆解计算。3.示例输入输出已给出，树的最大独立集通过动态规划求解。数据结构1.示例输入输出已给出，线段树支持区间加和区间和查询。2.示例输入输出已给出，Treap支持插入和前驱后继查询。图论1.示例输入输出