2026年noip中的经典问题集及其详细解析

2026年noip中的经典问题集及其详细解析一、算法设计题（共3题，每题25分）1.1.最短路径问题——城市交通优化（25分）题目描述：某城市有N个交通枢纽（编号1到N），枢纽之间通过双向道路连接。每条道路有一个权重，表示通过该道路所需的时间（单位：分钟）。现需要设计一个算法，找出从枢纽1到枢纽N的最短路径，并输出该路径的长度。如果存在多条最短路径，选择其中一条即可。输入格式：第一行输入一个整数N（2≤N≤1000），表示交通枢纽的数量。接下来N行，每行输入N个整数，表示每两个枢纽之间的道路权重。如果i和j之间没有道路，则输入0（i≠j），如果i=j，则输入0。输出格式：输出一个整数，表示从枢纽1到枢纽N的最短路径长度。如果无法到达，输出-1。示例输入：40206203803076870示例输出：12解析：最优路径为1→2→3→4，总长度为2+3+7=12。1.2.最小生成树问题——网络布线方案（25分）题目描述：某公司需要在N个办公室之间铺设网络线路，办公室编号为1到N。铺设每条线路的成本不同，需要选择一个最小生成树，使得所有办公室连通且总成本最低。输入格式：第一行输入一个整数N（3≤N≤200）。接下来N行，每行输入N个整数，表示在i和j之间铺设线路的成本。如果i和j之间不能铺设线路，输入0（i≠j），如果i=j，输入0。输出格式：输出一个整数，表示最小生成树的总成本。如果无法连通所有办公室，输出-1。示例输入：50200320300030400040530050示例输出：14解析：最优方案为1-2-3-4-5，总成本为2+3+4+5=14。1.3.动态规划问题——任务调度优化（25分）题目描述：某公司有N个任务需要完成，每个任务有一个开始时间和结束时间。如果两个任务的时间有重叠，则无法同时进行。需要选择一个任务集合，使得完成所有任务所需的最长时间尽可能短。输入格式：第一行输入一个整数N（2≤N≤200）。接下来N行，每行输入两个整数Si和Fi（1≤Si<Fi≤1000），分别表示任务的开始时间和结束时间。输出格式：输出一个整数，表示完成所有任务所需的最长时间。示例输入：6143506573859示例输出：9解析：最优方案为任务1（1-4）、任务3（0-6）、任务6（5-9），最长时间为9。二、数据结构题（共3题，每题25分）2.1.栈的应用——表达式求值（25分）题目描述：给定一个中缀表达式，包含数字和运算符（+、-、、/），使用栈实现表达式求值。输入格式：第一行输入一个字符串，表示中缀表达式。字符串长度不超过1000。输出格式：输出一个浮点数，表示表达式的值。示例输入：3+58-2示例输出：37.0解析：计算顺序为3+(58)-2=3+40-2=41。2.2.队列的应用——打印任务调度（25分）题目描述：有N个打印任务，每个任务有一个优先级（1到N，数字越小优先级越高）。使用队列实现打印任务调度，按优先级从高到低依次打印。输入格式：第一行输入一个整数N（1≤N≤100）。接下来N行，每行输入一个整数Pi（1≤Pi≤N），表示任务的优先级。输出格式：按顺序输出打印任务的编号。示例输入：43142示例输出：1234解析：按优先级排序后，任务1先打印，然后任务2、任务3、任务4。2.3.树的应用——二叉搜索树（25分）题目描述：给定一个整数序列，构建一个二叉搜索树，并输出按中序遍历的序列。输入格式：第一行输入一个整数N（1≤N≤100）。接下来N行，每行输入一个整数，表示序列中的元素。输出格式：按中序遍历输出二叉搜索树的序列，每个数字后空一格。示例输入：531425示例输出：12345解析：构建的二叉搜索树为：3/\14\2\5中序遍历为12345。三、字符串处理题（共3题，每题25分）3.1.字符串匹配——最长公共子串（25分）题目描述：给定两个字符串，找出它们的最长公共子串。输入格式：第一行输入一个字符串S1，第二行输入一个字符串S2。输出格式：输出最长公共子串。如果不存在，输出空字符串。示例输入：abcdefgabcxyz示例输出：abc解析：最长公共子串为"abc"。3.2.字符串处理——字符串反转（25分）题目描述：给定一个字符串，将其反转后输出。输入格式：第一行输入一个字符串，长度不超过1000。输出格式：输出反转后的字符串。示例输入：hello示例输出：olleh解析：字符串"hello"反转后为"olleh"。3.3.字符串处理——字符串匹配（KMP算法）（25分）题目描述：给定一个文本串T和一个模式串P，使用KMP算法找出模式串在文本串中的所有出现位置。输入格式：第一行输入文本串T，第二行输入模式串P。输出格式：按顺序输出模式串在文本串中的所有起始位置（从0开始），用空格分隔。如果未找到，输出-1。示例输入：ababababababab示例输出：0246解析：模式串"abab"在文本串中出现在位置0、2、4、6。答案与解析1.1.最短路径问题——城市交通优化（25分）-答案：使用Dijkstra算法，从枢纽1出发，更新所有可达节点的最短路径，最终得到最短路径长度为12。-解析：最优路径为1→2→3→4，总长度为2+3+7=12。1.2.最小生成树问题——网络布线方案（25分）-答案：使用Kruskal算法，按边权从小到大选择边，构建最小生成树，总成本为14。-解析：最优方案为1-2-3-4-5，总成本为2+3+4+5=14。1.3.动态规划问题——任务调度优化（25分）-答案：使用动态规划，定义f[i]为完成前i个任务所需的最长时间，最终f[N]为答案。-解析：最优方案为任务1（1-4）、任务3（0-6）、任务6（5-9），最长时间为9。2.1.栈的应用——表达式求值（25分）-答案：使用两个栈，一个存储数字，一个存储运算符，按顺序计算表达式。-解析：计算顺序为3+(58)-2=3+40-2=41。2.2.队列的应用——打印任务调度（25分）-答案：使用队列按优先级顺序存储任务，依次取出打印。-解析：按优先级排序后，任务1先打印，然后任务2、任务3、任务4。2.3.树的应用——二叉搜索树（25分）-答案：构建二叉搜索树，然后进行中序遍历。-解析：构建的二叉搜索树为：3/\14\2\5中序遍历为12345。3.1.字符串匹配——最长公共子串（25分）-答案：使用动态规划找出最长公共子串。-解析：最长公共子串为"abc"。3.2.字符串处理——字符串反转（25分）-答案：使用栈或递归反转