2026年程序設(shè)計(jì)競(jìng)賽題庫：算法設(shè)計(jì)與實(shí)現(xiàn)編程題1.動(dòng)態(tài)規(guī)劃類（共3題，每題15分）題目1（15分）：最長(zhǎng)公共子序列問題背景：在軟件開發(fā)中，經(jīng)常需要比較兩個(gè)版本字符串的差異。最長(zhǎng)公共子序列（LCS）是衡量?jī)蓚€(gè)字符串相似度的常用方法。問題描述：給定兩個(gè)字符串`str1`和`str2`，請(qǐng)計(jì)算它們的LCS長(zhǎng)度，并輸出任意一個(gè)LCS。輸入：輸入第一行包含一個(gè)整數(shù)`T`（1≤T≤10），表示測(cè)試用例數(shù)量。接下來`T`行，每行包含兩個(gè)由空格分隔的字符串，長(zhǎng)度均不超過1000個(gè)字符。輸出：對(duì)于每個(gè)測(cè)試用例，第一行輸出LCS的長(zhǎng)度，第二行輸出其中一個(gè)LCS（若存在多個(gè)，輸出任意一個(gè)）。若不存在LCS，則輸出`-1`。示例：輸入：3ABCBDABBDABAGGTABGXTXAYBaaaabbb輸出：4BDBA4GTAB0題目2（15分）：背包問題變種背景：在資源分配場(chǎng)景中，背包問題常用于最大化價(jià)值。本題要求在限制背包容量和物品數(shù)量時(shí)求解。問題描述：給定`n`件物品，每件物品的重量為`w[i]`（1≤w[i]≤100），價(jià)值為`v[i]`（1≤v[i]≤100）。背包最大容量為`W`（1≤W≤1000），最多可裝`k`件物品（1≤k≤n）。請(qǐng)計(jì)算最大總價(jià)值。輸入：輸入第一行包含四個(gè)整數(shù)`n`、`W`、`k`和`T`（1≤T≤10），表示測(cè)試用例數(shù)量。接下來`T`組數(shù)據(jù)，每組數(shù)據(jù)第一行包含`n`個(gè)整數(shù)`w[1..n]`，第二行包含`n`個(gè)整數(shù)`v[1..n]`。輸出：對(duì)于每個(gè)測(cè)試用例，輸出最大總價(jià)值。示例：輸入：250321020304050607020501030304050輸出：9060題目3（15分）：區(qū)間調(diào)度問題背景：在任務(wù)調(diào)度中，區(qū)間調(diào)度問題常用于最大化不重疊區(qū)間的數(shù)量。問題描述：給定`n`個(gè)區(qū)間`[s[i],e[i]]`（1≤n≤1000，1≤s[i]<e[i]≤10^6），請(qǐng)計(jì)算最多可以安排多少個(gè)不重疊的區(qū)間。輸入：輸入第一行包含一個(gè)整數(shù)`n`和`T`（1≤T≤10）。接下來`T`組數(shù)據(jù)，每組數(shù)據(jù)包含`n`行，每行兩個(gè)整數(shù)`s[i]`和`e[i]`。輸出：對(duì)于每個(gè)測(cè)試用例，輸出最多不重疊區(qū)間的數(shù)量。示例：輸入：32132546123456輸出：212.圖論類（共4題，每題20分）題目4（20分）：最小生成樹問題背景：在通信網(wǎng)絡(luò)建設(shè)中，最小生成樹（MST）用于連接所有節(jié)點(diǎn)且總權(quán)重最小。問題描述：給定一個(gè)無向連通圖，包含`n`個(gè)節(jié)點(diǎn)和`m`條邊（1≤n≤1000，1≤m≤10^4），每條邊包含權(quán)重`w`（1≤w≤10^4）。請(qǐng)計(jì)算其MST的總權(quán)重。輸入：輸入第一行包含兩個(gè)整數(shù)`n`和`m`。接下來`m`行，每行三個(gè)整數(shù)`u`、`v`和`w`，表示節(jié)點(diǎn)`u`和`v`之間的邊權(quán)重。輸出：輸出MST的總權(quán)重。示例：輸入：45121133146232344輸出：8題目5（20分）：最短路徑問題背景：在物流路徑規(guī)劃中，最短路徑算法（如Dijkstra）常用于求解起點(diǎn)到所有節(jié)點(diǎn)的最短距離。問題描述：給定一個(gè)帶權(quán)圖，包含`n`個(gè)節(jié)點(diǎn)和`m`條邊（1≤n≤1000，1≤m≤10^4），起點(diǎn)為`1`。請(qǐng)計(jì)算從起點(diǎn)到所有節(jié)點(diǎn)的最短距離。輸入：輸入第一行包含兩個(gè)整數(shù)`n`和`m`。接下來`m`行，每行三個(gè)整數(shù)`u`、`v`和`w`，表示節(jié)點(diǎn)`u`和`v`之間的邊權(quán)重（若`u`到`v`無直接邊，則`w`為無窮大，可用`10^7`表示）。輸出：輸出起點(diǎn)到所有節(jié)點(diǎn)的最短距離，按節(jié)點(diǎn)編號(hào)順序排列，無法到達(dá)的節(jié)點(diǎn)輸出`-1`。示例：輸入：451211332323441410輸出：0126題目6（20分）：二分圖最大匹配問題背景：在資源分配場(chǎng)景中，二分圖最大匹配可用于最大化匹配數(shù)量。問題描述：給定一個(gè)二分圖，左部節(jié)點(diǎn)數(shù)為`m`，右部節(jié)點(diǎn)數(shù)為`n`（1≤m,n≤200），包含`e`條邊（1≤e≤4000）。請(qǐng)計(jì)算最大匹配數(shù)量。輸入：輸入第一行包含三個(gè)整數(shù)`m`、`n`和`e`。接下來`e`行，每行兩個(gè)整數(shù)`u`和`v`，表示左部節(jié)點(diǎn)`u`和右部節(jié)點(diǎn)`v`之間存在邊。輸出：輸出最大匹配數(shù)量。示例：輸入：3351112132233輸出：2題目7（20分）：拓?fù)渑判騿栴}背景：在依賴任務(wù)調(diào)度中，拓?fù)渑判蛴糜诖_保任務(wù)按依賴順序執(zhí)行。問題描述：給定一個(gè)有向無環(huán)圖（DAG），包含`n`個(gè)節(jié)點(diǎn)和`m`條邊（1≤n≤1000，1≤m≤10^4），請(qǐng)輸出其拓?fù)渑判蛐蛄小Ｈ舸嬖诃h(huán)，則輸出`-1`。輸入：輸入第一行包含兩個(gè)整數(shù)`n`和`m`。接下來`m`行，每行兩個(gè)整數(shù)`u`和`v`，表示從節(jié)點(diǎn)`u`到節(jié)點(diǎn)`v`的邊。輸出：輸出拓?fù)渑判蛐蛄?，若存在環(huán)則輸出`-1`。示例：輸入：4412233414輸出：12343.字符串處理類（共3題，每題15分）題目8（15分）：字符串匹配問題背景：在文本搜索中，字符串匹配算法（如KMP）常用于高效查找子串。問題描述：給定主串`S`和模式串`P`（1≤|S|,|P|≤1000），請(qǐng)計(jì)算`P`在`S`中出現(xiàn)的次數(shù)（不區(qū)分大小寫）。輸入：輸入第一行包含一個(gè)整數(shù)`T`（1≤T≤10）。接下來`T`組數(shù)據(jù)，每組數(shù)據(jù)包含兩個(gè)由空格分隔的字符串`S`和`P`。輸出：對(duì)于每個(gè)測(cè)試用例，輸出`P`在`S`中出現(xiàn)的次數(shù)。示例：輸入：2ABCDABCDABDEABCABDHelloWorldhello輸出：31題目9（15分）：字符串編輯距離問題背景：在文本糾錯(cuò)中，編輯距離（Levenshtein距離）用于衡量?jī)蓚€(gè)字符串的相似度。問題描述：給定兩個(gè)字符串`str1`和`str2`，請(qǐng)計(jì)算它們的編輯距離（插入、刪除、替換操作各計(jì)1次）。輸入：輸入第一行包含一個(gè)整數(shù)`T`（1≤T≤10）。接下來`T`組數(shù)據(jù)，每組數(shù)據(jù)包含兩個(gè)由空格分隔的字符串`str1`和`str2`。輸出：對(duì)于每個(gè)測(cè)試用例，輸出編輯距離。示例：輸入：2kittensittinggardengarden輸出：30題目10（15分）：字符串壓縮問題背景：在數(shù)據(jù)存儲(chǔ)中，字符串壓縮可減少存儲(chǔ)空間。問題描述：給定一個(gè)字符串`S`，請(qǐng)使用Run-LengthEncoding（RLE）進(jìn)行壓縮。若壓縮后長(zhǎng)度不小于原字符串，則輸出原字符串。輸入：輸入第一行包含一個(gè)整數(shù)`T`（1≤T≤10）。接下來`T`組數(shù)據(jù)，每組數(shù)據(jù)包含一個(gè)字符串`S`。輸出：對(duì)于每個(gè)測(cè)試用例，輸出壓縮后的字符串或原字符串。示例：輸入：2AAAABBBCCDAAABCD輸出：4A3B2C1D2AABCD答案與解析動(dòng)態(tài)規(guī)劃類題目1：-輸入：3ABCBDABBDABAGGTABGXTXAYBaaaabbb-輸出：4BDBA4GTAB0-解析：-第一個(gè)測(cè)試用例：LCS為`BDBA`，長(zhǎng)度為4。-第二個(gè)測(cè)試用例：LCS為`GTAB`，長(zhǎng)度為4。-第三個(gè)測(cè)試用例：無公共子序列，輸出`0`。題目2：-輸入：250321020304050607020501030304050-輸出：9060-解析：-第一個(gè)測(cè)試用例：選擇物品1（價(jià)值20）、物品3（價(jià)值30）、物品4（價(jià)值40），總價(jià)值90。-第二個(gè)測(cè)試用例：選擇物品1（價(jià)值50）、物品3（價(jià)值50），總價(jià)值60。題目3：-輸入：32132546123456-輸出：21-解析：-第一個(gè)測(cè)試用例：選擇區(qū)間`[1,3]`和`[4,6]`，共2個(gè)。-第二個(gè)測(cè)試用例：選擇區(qū)間`[1,2]`，共1個(gè)。圖論類題目4：-輸入：45121133146232344-輸出：8-解析：-MST邊集：`[1-2,1-3,2-3,3-4]`，總權(quán)重8。題目5：-輸入：451211332323441410-輸出：0126-解析：-最短路徑：`0->1(1),1->3(2),3->4(4)`，輸出`0126`。題目6：-輸入：3351112132233-輸出：2-解析：-最大匹配：左部節(jié)點(diǎn)1匹配節(jié)點(diǎn)1，左部節(jié)點(diǎn)2匹配節(jié)點(diǎn)2，共2個(gè)。題目7：-輸入：4412233414-輸出：1234-解析：-拓?fù)渑判颍篳1->2->3->4`。字符串處理類題目8：-輸入：2ABCDABCDABDEABCABDHelloWorldhello-輸出：31-解析：-第一個(gè)測(cè)試用例：`ABCABD`出現(xiàn)3次。-第二個(gè)測(cè)試用例：`hello`出現(xiàn)1次。題目9：-輸入：2kittensittinggardengarden-輸出：30-解析：-