2026年程序设计竞赛题库算法设计与实现编程题

2026年程序设计竞赛题库：算法设计与实现编程题1.动态规划类（共3题，每题15分）题目1（15分）：最长公共子序列问题背景：在软件开发中，经常需要比较两个版本字符串的差异。最长公共子序列（LCS）是衡量两个字符串相似度的常用方法。问题描述：给定两个字符串`str1`和`str2`，请计算它们的LCS长度，并输出任意一个LCS。输入：输入第一行包含一个整数`T`（1≤T≤10），表示测试用例数量。接下来`T`行，每行包含两个由空格分隔的字符串，长度均不超过1000个字符。输出：对于每个测试用例，第一行输出LCS的长度，第二行输出其中一个LCS（若存在多个，输出任意一个）。若不存在LCS，则输出`-1`。示例：输入：3ABCBDABBDABAGGTABGXTXAYBaaaabbb输出：4BDBA4GTAB0题目2（15分）：背包问题变种背景：在资源分配场景中，背包问题常用于最大化价值。本题要求在限制背包容量和物品数量时求解。问题描述：给定`n`件物品，每件物品的重量为`w[i]`（1≤w[i]≤100），价值为`v[i]`（1≤v[i]≤100）。背包最大容量为`W`（1≤W≤1000），最多可装`k`件物品（1≤k≤n）。请计算最大总价值。输入：输入第一行包含四个整数`n`、`W`、`k`和`T`（1≤T≤10），表示测试用例数量。接下来`T`组数据，每组数据第一行包含`n`个整数`w[1..n]`，第二行包含`n`个整数`v[1..n]`。输出：对于每个测试用例，输出最大总价值。示例：输入：250321020304050607020501030304050输出：9060题目3（15分）：区间调度问题背景：在任务调度中，区间调度问题常用于最大化不重叠区间的数量。问题描述：给定`n`个区间`[s[i],e[i]]`（1≤n≤1000，1≤s[i]<e[i]≤10^6），请计算最多可以安排多少个不重叠的区间。输入：输入第一行包含一个整数`n`和`T`（1≤T≤10）。接下来`T`组数据，每组数据包含`n`行，每行两个整数`s[i]`和`e[i]`。输出：对于每个测试用例，输出最多不重叠区间的数量。示例：输入：32132546123456输出：212.图论类（共4题，每题20分）题目4（20分）：最小生成树问题背景：在通信网络建设中，最小生成树（MST）用于连接所有节点且总权重最小。问题描述：给定一个无向连通图，包含`n`个节点和`m`条边（1≤n≤1000，1≤m≤10^4），每条边包含权重`w`（1≤w≤10^4）。请计算其MST的总权重。输入：输入第一行包含两个整数`n`和`m`。接下来`m`行，每行三个整数`u`、`v`和`w`，表示节点`u`和`v`之间的边权重。输出：输出MST的总权重。示例：输入：45121133146232344输出：8题目5（20分）：最短路径问题背景：在物流路径规划中，最短路径算法（如Dijkstra）常用于求解起点到所有节点的最短距离。问题描述：给定一个带权图，包含`n`个节点和`m`条边（1≤n≤1000，1≤m≤10^4），起点为`1`。请计算从起点到所有节点的最短距离。输入：输入第一行包含两个整数`n`和`m`。接下来`m`行，每行三个整数`u`、`v`和`w`，表示节点`u`和`v`之间的边权重（若`u`到`v`无直接边，则`w`为无穷大，可用`10^7`表示）。输出：输出起点到所有节点的最短距离，按节点编号顺序排列，无法到达的节点输出`-1`。示例：输入：451211332323441410输出：0126题目6（20分）：二分图最大匹配问题背景：在资源分配场景中，二分图最大匹配可用于最大化匹配数量。问题描述：给定一个二分图，左部节点数为`m`，右部节点数为`n`（1≤m,n≤200），包含`e`条边（1≤e≤4000）。请计算最大匹配数量。输入：输入第一行包含三个整数`m`、`n`和`e`。接下来`e`行，每行两个整数`u`和`v`，表示左部节点`u`和右部节点`v`之间存在边。输出：输出最大匹配数量。示例：输入：3351112132233输出：2题目7（20分）：拓扑排序问题背景：在依赖任务调度中，拓扑排序用于确保任务按依赖顺序执行。问题描述：给定一个有向无环图（DAG），包含`n`个节点和`m`条边（1≤n≤1000，1≤m≤10^4），请输出其拓扑排序序列。若存在环，则输出`-1`。输入：输入第一行包含两个整数`n`和`m`。接下来`m`行，每行两个整数`u`和`v`，表示从节点`u`到节点`v`的边。输出：输出拓扑排序序列，若存在环则输出`-1`。示例：输入：4412233414输出：12343.字符串处理类（共3题，每题15分）题目8（15分）：字符串匹配问题背景：在文本搜索中，字符串匹配算法（如KMP）常用于高效查找子串。问题描述：给定主串`S`和模式串`P`（1≤|S|,|P|≤1000），请计算`P`在`S`中出现的次数（不区分大小写）。输入：输入第一行包含一个整数`T`（1≤T≤10）。接下来`T`组数据，每组数据包含两个由空格分隔的字符串`S`和`P`。输出：对于每个测试用例，输出`P`在`S`中出现的次数。示例：输入：2ABCDABCDABDEABCABDHelloWorldhello输出：31题目9（15分）：字符串编辑距离问题背景：在文本纠错中，编辑距离（Levenshtein距离）用于衡量两个字符串的相似度。问题描述：给定两个字符串`str1`和`str2`，请计算它们的编辑距离（插入、删除、替换操作各计1次）。输入：输入第一行包含一个整数`T`（1≤T≤10）。接下来`T`组数据，每组数据包含两个由空格分隔的字符串`str1`和`str2`。输出：对于每个测试用例，输出编辑距离。示例：输入：2kittensittinggardengarden输出：30题目10（15分）：字符串压缩问题背景：在数据存储中，字符串压缩可减少存储空间。问题描述：给定一个字符串`S`，请使用Run-LengthEncoding（RLE）进行压缩。若压缩后长度不小于原字符串，则输出原字符串。输入：输入第一行包含一个整数`T`（1≤T≤10）。接下来`T`组数据，每组数据包含一个字符串`S`。输出：对于每个测试用例，输出压缩后的字符串或原字符串。示例：输入：2AAAABBBCCDAAABCD输出：4A3B2C1D2AABCD答案与解析动态规划类题目1：-输入：3ABCBDABBDABAGGTABGXTXAYBaaaabbb-输出：4BDBA4GTAB0-解析：-第一个测试用例：LCS为`BDBA`，长度为4。-第二个测试用例：LCS为`GTAB`，长度为4。-第三个测试用例：无公共子序列，输出`0`。题目2：-输入：250321020304050607020501030304050-输出：9060-解析：-第一个测试用例：选择物品1（价值20）、物品3（价值30）、物品4（价值40），总价值90。-第二个测试用例：选择物品1（价值50）、物品3（价值50），总价值60。题目3：-输入：32132546123456-输出：21-解析：-第一个测试用例：选择区间`[1,3]`和`[4,6]`，共2个。-第二个测试用例：选择区间`[1,2]`，共1个。图论类题目4：-输入：45121133146232344-输出：8-解析：-MST边集：`[1-2,1-3,2-3,3-4]`，总权重8。题目5：-输入：451211332323441410-输出：0126-解析：-最短路径：`0->1(1),1->3(2),3->4(4)`，输出`0126`。题目6：-输入：3351112132233-输出：2-解析：-最大匹配：左部节点1匹配节点1，左部节点2匹配节点2，共2个。题目7：-输入：4412233414-输出：1234-解析：-拓扑排序：`1->2->3->4`。字符串处理类题目8：-输入：2ABCDABCDABDEABCABDHelloWorldhello-输出：31-解析：-第一个测试用例：`ABCABD`出现3次。-第二个测试用例：`hello`出现1次。题目9：-输入：2kittensittinggardengarden-输出：30-解析：-