第二次參加藍(lán)橋杯，手機(jī)再次沒電導(dǎo)致只寫了兩個(gè)半小時(shí)就交了（不能重復(fù)交哎），這次帶了充電寶，結(jié)果充電寶充電線中途松了，不得不說騰訊會(huì)議的耗電量真大。本博客就是剛提交后寫的，可以看看時(shí)間hhh。

就做了前五道題，不過前五道題就搜索、枚舉、進(jìn)制就能做和一道動(dòng)態(tài)規(guī)劃（蝸牛那道，逆序做就沒問題，基本能全跑過用例），看命了。

2023.04.08號(hào)，看什么時(shí)候出結(jié)果。

2023.04.23號(hào)，今年組委會(huì)口徑統(tǒng)一周日出，果然凌晨就出了，省一中部占位，估分35-45（ACWing上有題目可以測(cè)），后五道題一行代碼都沒打，所以這個(gè)估分應(yīng)該是比較準(zhǔn)的，網(wǎng)上那些說六十分省一的別被騙了。

目錄

試題 A: 階乘求和

試題 B: 幸運(yùn)數(shù)字

試題 C: 數(shù)組分割

試題 D: 矩形總面積

試題 E: 蝸牛

試題 F: 合并區(qū)域

試題 G: 買二贈(zèng)一

試題 H: 合并石子

試題 I: 最大開支

試題 J: 魔法陣

?

試題 A: 階乘求和

本題總分：5 分

【問題描述】

令 S = 1! + 2! + 3! + ... + 202320232023!，求 S 的末尾 9 位數(shù)字。 提示：答案首位不為 0。

【答案提交】

這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一 個(gè)整數(shù)，在提交答案時(shí)只填寫這個(gè)整數(shù)，填寫多余的內(nèi)容將無法得分。

試題 B: 幸運(yùn)數(shù)字

本題總分：5 分

【問題描述】

哈沙德數(shù)是指在某個(gè)固定的進(jìn)位制當(dāng)中，可以被各位數(shù)字之和整除的正整 數(shù)。例如 126 是十進(jìn)制下的一個(gè)哈沙德數(shù)，因?yàn)?(126)10 mod (1+2+6) = 0；126

也是八進(jìn)制下的哈沙德數(shù)，因?yàn)?(126)10 = (176)8，(126)10 mod (1 + 7 + 6) = 0； 同時(shí) 126 也是 16 進(jìn)制下的哈沙德數(shù)，因?yàn)?(126)10 = (7e)16，(126)10 mod (7 + e) = 0。小藍(lán)認(rèn)為，如果一個(gè)整數(shù)在二進(jìn)制、八進(jìn)制、十進(jìn)制、十六進(jìn)制下均為 哈沙德數(shù)，那么這個(gè)數(shù)字就是幸運(yùn)數(shù)字，第 1 至第 10 個(gè)幸運(yùn)數(shù)字的十進(jìn)制表示 為：1 , 2 , 4 , 6 , 8 , 40 , 48 , 72 , 120 , 126 . . . ?，F(xiàn)在他想知道第 2023 個(gè)幸運(yùn)數(shù) 字是多少？你只需要告訴小藍(lán)這個(gè)整數(shù)的十進(jìn)制表示即可。

【答案提交】

這是一道結(jié)果填空的題，你只需要算出結(jié)果后提交即可。本題的結(jié)果為一 個(gè)整數(shù)，在提交答案時(shí)只填寫這個(gè)整數(shù)，填寫多余的內(nèi)容將無法得分。

試題 C: 數(shù)組分割

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：10 分

【問題描述】

小藍(lán)有一個(gè)長(zhǎng)度為 N 的數(shù)組 A = [A0, A1, . . . , AN?1]?，F(xiàn)在小藍(lán)想要從 A 對(duì) 應(yīng)的數(shù)組下標(biāo)所構(gòu)成的集合 I = {0, 1, 2, . . . , N ? 1} 中找出一個(gè)子集 R1，那么 R1

在 I 中的補(bǔ)集為 R2。記 S 1 = ∑

r∈R1 Ar，S 2 = ∑

r∈R2 Ar，我們要求 S 1 和 S 2 均為 偶數(shù)，請(qǐng)問在這種情況下共有多少種不同的 R1。當(dāng) R1 或 R2 為空集時(shí)我們將

S 1 或 S 2 視為 0。

【輸入格式】

第一行一個(gè)整數(shù) T，表示有 T 組數(shù)據(jù)。 接下來輸入 T 組數(shù)據(jù)，每組數(shù)據(jù)包含兩行：第一行一個(gè)整數(shù) N，表示數(shù)組

A 的長(zhǎng)度；第二行輸入 N 個(gè)整數(shù)從左至右依次為 A0, A1, . . . , AN?1，相鄰元素之 間用空格分隔。

【輸出格式】

對(duì)于每組數(shù)據(jù)，輸出一行，包含一個(gè)整數(shù)表示答案，答案可能會(huì)很大，你 需要將答案對(duì) 1000000007 進(jìn)行取模后輸出。

【樣例輸入】

2

2?

6 6

2

1 6

【樣例輸出】

4

0

【樣例說明】

對(duì)于第一組數(shù)據(jù)，答案為 4。（注意：大括號(hào)內(nèi)的數(shù)字表示元素在數(shù)組中的 下標(biāo)。）

R1 = {0}, R2 = {1}；此時(shí) S 1 = A0 = 6 為偶數(shù), S 2 = A1 = 6 為偶數(shù)。

R1 = {1}, R2 = {0}；此時(shí) S 1 = A1 = 6 為偶數(shù), S 2 = A0 = 6 為偶數(shù)。

R1 = {0, 1}, R2 = {}；此時(shí) S 1 = A0 + A1 = 12 為偶數(shù), S 2 = 0 為偶數(shù)。

R1 = {}, R2 = {0, 1}；此時(shí) S 1 = 0 為偶數(shù), S 2 = A0 + A1 = 12 為偶數(shù)。 對(duì)于第二組數(shù)據(jù)，無論怎么選擇，都不滿足條件，所以答案為 0。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 20% 的評(píng)測(cè)用例，1 ≤ N ≤ 10。 對(duì)于 40% 的評(píng)測(cè)用例，1 ≤ N ≤ 10 2。 對(duì)于 100% 的評(píng)測(cè)用例，1 ≤ T ≤ 10, 1 ≤ N ≤ 10 3 , 0 ≤ Ai ≤ 10 9。

試題 D: 矩形總面積

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：10 分

【問題描述】

平面上有個(gè)兩個(gè)矩形 R1 和 R2，它們各邊都與坐標(biāo)軸平行。設(shè) (x1, y1) 和

(x2, y2) 依次是 R1 的左下角和右上角坐標(biāo)，(x3, y3) 和 (x4, y4) 依次是 R2 的左下 角和右上角坐標(biāo)，請(qǐng)你計(jì)算 R1 和 R2 的總面積是多少？ 注意：如果 R1 和 R2 有重疊區(qū)域，重疊區(qū)域的面積只計(jì)算一次。

【輸入格式】

輸入只有一行，包含 8 個(gè)整數(shù)，依次是：x1，y1，x2，y2，x3，y3，x4 和 y4。

【輸出格式】

一個(gè)整數(shù)，代表答案。

【樣例輸入】

2 1 7 4 5 3 8 6

【樣例輸出】

22

【樣例說明】

樣例中的兩個(gè)矩形如圖所示：

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 20% 的數(shù)據(jù)，R1 和 R2 沒有重疊區(qū)域。 對(duì)于 20% 的數(shù)據(jù)，其中一個(gè)矩形完全在另一個(gè)矩形內(nèi)部。 對(duì)于 50% 的數(shù)據(jù)，所有坐標(biāo)的取值范圍是 [0, ]。 對(duì)于 100% 的數(shù)據(jù)，所有坐標(biāo)的取值范圍是 [0, ]。

試題 E: 蝸牛

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：15 分

【問題描述】

這天，一只蝸牛來到了二維坐標(biāo)系的原點(diǎn)。 在 x 軸上長(zhǎng)有 n 根竹竿。它們平行于 y 軸，底部縱坐標(biāo)為 0，橫坐標(biāo)分別 為 x1, x2, ..., xn。竹竿的高度均為無限高，寬度可忽略。蝸牛想要從原點(diǎn)走到第

n 個(gè)竹竿的底部也就是坐標(biāo) (xn, 0)。它只能在 x 軸上或者竹竿上爬行，在 x 軸 上爬行速度為 1 單位每秒；由于受到引力影響，蝸牛在竹竿上向上和向下爬行 的速度分別為 0.7 單位每秒和 1.3 單位每秒。 為了快速到達(dá)目的地，它施展了魔法，在第 i 和 i + 1 根竹竿之間建立了傳 送門（0 < i < n），如果蝸牛位于第 i 根竹竿的高度為 ai 的位置 (xi , ai)，就可以 瞬間到達(dá)第 i + 1 根竹竿的高度為 bi+1 的位置 (xi+1, bi+1)，請(qǐng)計(jì)算蝸牛最少需要 多少秒才能到達(dá)目的地。

【輸入格式】

輸入共 1 + n 行，第一行為一個(gè)正整數(shù) n； 第二行為 n 個(gè)正整數(shù) x1, x2, . . . , xn； 后面 n ? 1 行，每行兩個(gè)正整數(shù) ai , bi+1。

【輸出格式】

輸出共一行，一個(gè)浮點(diǎn)數(shù)表示答案（四舍五入保留兩位小數(shù)）。

【樣例輸入】

3
1 10 11
1 1
2 1

【樣例輸出】

4.20

【樣例說明】

蝸牛路線：

(0, 0) → (1, 0) → (1, 1) → (10, 1) → (10, 0) → (11, 0)，花費(fèi)時(shí)間為 1 + 1 0.7 + 0 + 1 1.3 + 1 ≈ 4.20

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 20% 的數(shù)據(jù)，保證 n ≤ 15； 對(duì)于 100% 的數(shù)據(jù)，保證 n ≤ ，ai , bi ≤ ，xi ≤ 。

試題 F: 合并區(qū)域

時(shí)間限制: 2.0s 內(nèi)存限制: 512.0MB 本題總分：15 分

【問題描述】

小藍(lán)在玩一款種地游戲?，F(xiàn)在他被分配給了兩塊大小均為 N × N 的正方形 區(qū)域。這兩塊區(qū)域都按照 N × N 的規(guī)格進(jìn)行了均等劃分，劃分成了若干塊面積 相同的小區(qū)域，其中每塊小區(qū)域要么是巖石，要么就是土壤，在垂直或者水平 方向上相鄰的土壤可以組成一塊土地?，F(xiàn)在小藍(lán)想要對(duì)這兩塊區(qū)域沿著邊緣進(jìn) 行合并，他想知道合并以后可以得到的最大的一塊土地的面積是多少（土地的 面積就是土地中土壤小區(qū)域的塊數(shù)）？ 在進(jìn)行合并時(shí)，小區(qū)域之間必須對(duì)齊?？梢栽趦蓧K方形區(qū)域的任何一條邊 上進(jìn)行合并，可以對(duì)兩塊方形區(qū)域進(jìn)行 90 度、180 度、270 度、360 度的旋轉(zhuǎn)， 但不可以進(jìn)行上下或左右翻轉(zhuǎn)，并且兩塊方形區(qū)域不可以發(fā)生重疊。

【輸入格式】

第一行一個(gè)整數(shù) N 表示區(qū)域大小。 接下來 N 行表示第一塊區(qū)域，每行 N 個(gè)值為 0 或 1 的整數(shù)，相鄰的整數(shù) 之間用空格進(jìn)行分隔。值為 0 表示這塊小區(qū)域是巖石，值為 1 表示這塊小區(qū)域 是土壤。 再接下來 N 行表示第二塊區(qū)域，每行 N 個(gè)值為 0 或 1 的整數(shù)，相鄰的整 數(shù)之間用空格進(jìn)行分隔。值為 0 表示這塊小區(qū)域是巖石，值為 1 表示這塊小區(qū) 域是土壤。

【輸出格式】

一個(gè)整數(shù)表示將兩塊區(qū)域合并之后可以產(chǎn)生的最大的土地面積。

【樣例輸入】

4
0 1 1 0
1 0 1 1
1 0 1 0
1 1 1 0
0 0 1 0
0 1 1 0
1 0 0 0
1 1 1 1

【樣例輸出】

15

【樣例說明】

?第一張圖展示了樣例中的兩塊區(qū)域的布局。第二張圖展示了其中一種最佳 的合并方式，此時(shí)最大的土地面積為 15。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 30% 的數(shù)據(jù)，1 ≤ N ≤ 5。 對(duì)于 60% 的數(shù)據(jù)，1 ≤ N ≤ 15。 對(duì)于 100% 的數(shù)據(jù)，1 ≤ N ≤ 50。

試題 G: 買二贈(zèng)一

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：20 分

【問題描述】

某商場(chǎng)有 N 件商品，其中第 i 件的價(jià)格是 Ai?，F(xiàn)在該商場(chǎng)正在進(jìn)行 “買二 贈(zèng)一” 的優(yōu)惠活動(dòng)，具體規(guī)則是： 每購(gòu)買 2 件商品，假設(shè)其中較便宜的價(jià)格是 P（如果兩件商品價(jià)格一樣， 則 P 等于其中一件商品的價(jià)格），就可以從剩余商品中任選一件價(jià)格不超過 P

2

的商品，免費(fèi)獲得這一件商品?？梢酝ㄟ^反復(fù)購(gòu)買 2 件商品來獲得多件免費(fèi)商 品，但是每件商品只能被購(gòu)買或免費(fèi)獲得一次。 小明想知道如果要拿下所有商品（包含購(gòu)買和免費(fèi)獲得），至少要花費(fèi)多少 錢？

【輸入格式】

第一行包含一個(gè)整數(shù) N。 第二行包含 N 個(gè)整數(shù)，代表 A1, A2, A3, . . . ，AN。

【輸出格式】

輸出一個(gè)整數(shù)，代表答案。

【樣例輸入】

7

1 4 2 8 5 7 1

【樣例輸出】

25

【樣例說明】

小明可以先購(gòu)買價(jià)格 4 和 8 的商品，免費(fèi)獲得一件價(jià)格為 1 的商品；再后 買價(jià)格為 5 和 7 的商品，免費(fèi)獲得價(jià)格為 2 的商品；最后單獨(dú)購(gòu)買剩下的一件 價(jià)格為 1 的商品?？傆?jì)花費(fèi) 4 + 8 + 5 + 7 + 1 = 25。不存在花費(fèi)更低的方案。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 30% 的數(shù)據(jù)，1 ≤ N ≤ 20。 對(duì)于 100% 的數(shù)據(jù)，1 ≤ N ≤ 5 × ，1 ≤ Ai ≤ 。

試題 H: 合并石子

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：20 分

【問題描述】

在桌面從左至右橫向擺放著 N 堆石子。每一堆石子都有著相同的顏色，顏 色可能是顏色 0，顏色 1 或者顏色 2 中的其中一種。 現(xiàn)在要對(duì)石子進(jìn)行合并，規(guī)定每次只能選擇位置相鄰并且顏色相同的兩堆 石子進(jìn)行合并。合并后新堆的相對(duì)位置保持不變，新堆的石子數(shù)目為所選擇的 兩堆石子數(shù)目之和，并且新堆石子的顏色也會(huì)發(fā)生循環(huán)式的變化。具體來說： 兩堆顏色 0 的石子合并后的石子堆為顏色 1，兩堆顏色 1 的石子合并后的石子 堆為顏色 2，兩堆顏色 2 的石子合并后的石子堆為顏色 0。本次合并的花費(fèi)為所 選擇的兩堆石子的數(shù)目之和。 給出 N 堆石子以及他們的初始顏色，請(qǐng)問最少可以將它們合并為多少堆石 子？如果有多種答案，選擇其中合并總花費(fèi)最小的一種，合并總花費(fèi)指的是在 所有的合并操作中產(chǎn)生的合并花費(fèi)的總和。

【輸入格式】

第一行一個(gè)正整數(shù) N 表示石子堆數(shù)。 第二行包含 N 個(gè)用空格分隔的正整數(shù)，表示從左至右每一堆石子的數(shù)目。 第三行包含 N 個(gè)值為 0 或 1 或 2 的整數(shù)表示每堆石頭的顏色。

【輸出格式】

一行包含兩個(gè)整數(shù)，用空格分隔。其中第一個(gè)整數(shù)表示合并后數(shù)目最少的 石頭堆數(shù)，第二個(gè)整數(shù)表示對(duì)應(yīng)的最小花費(fèi)。

【樣例輸入】

5

5 10 1 8 6

1 1 0 2 2

【樣例輸出】

2 44

【樣例說明】

上圖顯示了兩種不同的合并方式。其中節(jié)點(diǎn)中標(biāo)明了每一堆的石子數(shù)目， 在方括號(hào)中標(biāo)注了當(dāng)前堆石子的顏色屬性。左圖的這種合并方式最終剩下了兩 堆石子，所產(chǎn)生的合并總花費(fèi)為 15 + 14 + 15 = 44；右圖的這種合并方式最終 也剩下了兩堆石子，但產(chǎn)生的合并總花費(fèi)為 14 + 15 + 25 = 54。綜上所述，我 們選擇合并花費(fèi)為 44 的這種方式作為答案。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 30% 的評(píng)測(cè)用例，1 ≤ N ≤ 10。 對(duì)于 50% 的評(píng)測(cè)用例，1 ≤ N ≤ 50。 對(duì)于 100% 的評(píng)測(cè)用例，1 ≤ N ≤ 300, 1 ≤ 每堆石子的數(shù)目 ≤ 1000。

試題 I: 最大開支

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：25 分

【問題描述】

小藍(lán)所在學(xué)校周邊新開業(yè)了一家游樂園，小藍(lán)作為班長(zhǎng)，打算組織大家去 游樂園玩。已知一共有 N 個(gè)人參加這次活動(dòng)，游樂園有 M 個(gè)娛樂項(xiàng)目，每個(gè) 項(xiàng)目都需要買門票后才可進(jìn)去游玩。門票的價(jià)格并不是固定的，團(tuán)購(gòu)的人越多 單價(jià)越便宜，當(dāng)團(tuán)購(gòu)的人數(shù)大于某個(gè)閾值時(shí)，這些團(tuán)購(gòu)的人便可以免費(fèi)進(jìn)入項(xiàng) 目進(jìn)行游玩。這 M 個(gè)娛樂項(xiàng)目是獨(dú)立的，所以只有選擇了同一個(gè)項(xiàng)目的人才可 以參與這個(gè)項(xiàng)目的團(tuán)購(gòu)。第 i 個(gè)項(xiàng)目的門票價(jià)格 Hi 與團(tuán)購(gòu)的人數(shù) X 的關(guān)系可 以看作是一個(gè)函數(shù)：

Hi(X) = max(Ki × X + Bi , 0)

max 表示取二者之中的最大值。當(dāng) Hi = 0 時(shí)說明團(tuán)購(gòu)人數(shù)達(dá)到了此項(xiàng)目的 免單閾值。 這 N 個(gè)人可以根據(jù)自己的喜好選擇 M 個(gè)娛樂項(xiàng)目中的一種，或者有些人 對(duì)這些娛樂項(xiàng)目都沒有興趣，也可以選擇不去任何一個(gè)項(xiàng)目。每個(gè)人最多只會(huì) 選擇一個(gè)娛樂項(xiàng)目，如果多個(gè)人選擇了同一個(gè)娛樂項(xiàng)目，那么他們都將享受對(duì) 應(yīng)的團(tuán)購(gòu)價(jià)格。小藍(lán)想知道他至少需要準(zhǔn)備多少錢，使得無論大家如何選擇， 他都有能力支付得起所有 N 個(gè)人購(gòu)買娛樂項(xiàng)目的門票錢。

【輸入格式】

第一行兩個(gè)整數(shù) N、M，分別表示參加活動(dòng)的人數(shù)和娛樂項(xiàng)目的個(gè)數(shù)。 接下來 M 行，每行兩個(gè)整數(shù)，其中第 i 行為 Ki、Bi，表示第 i 個(gè)游樂地點(diǎn) 的門票函數(shù)中的參數(shù)。

【輸出格式】

一個(gè)整數(shù)，表示小藍(lán)至少需要準(zhǔn)備多少錢，使得大家無論如何選擇項(xiàng)目， 自己都支付得起。

【樣例輸入】

4 2

-4 10

-2 7

【樣例輸出】

12

【樣例說明】

樣例中有 4 個(gè)人，2 個(gè)娛樂項(xiàng)目，我們用一個(gè)二元組 (a, b) 表示 a 個(gè)人選 擇了第一個(gè)娛樂項(xiàng)目，b 個(gè)人選擇了第二個(gè)娛樂項(xiàng)目，那么就有 4 ? a ? b 個(gè) 人沒有選擇任何項(xiàng)目，方案 (a, b) 對(duì)應(yīng)的門票花費(fèi)為 max(?4 × a + 10, 0) × a + max(?2 × b + 7, 0) × b，所有的可能如下所示：

其中當(dāng) a = 1, b = 2 時(shí)花費(fèi)最大，為 12。此時(shí) 1 個(gè)人去第一個(gè)項(xiàng)目，所以

第一個(gè)項(xiàng)目的單價(jià)為 10 ? 4 = 6，在這個(gè)項(xiàng)目上的花費(fèi)為 6 × 1 = 6；2 個(gè)人去 第二個(gè)項(xiàng)目，所以第二個(gè)項(xiàng)目得單價(jià)為 7 ? 2 × 2 = 3，在這個(gè)項(xiàng)目上的花費(fèi)為

2 × 3 = 6；還有 1 個(gè)人沒去任何項(xiàng)目，不用統(tǒng)計(jì)；總花費(fèi)為 12，這是花費(fèi)最大 的一種方案，所以答案為 12。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 30% 的評(píng)測(cè)用例，1 ≤ N, M ≤ 10。 對(duì)于 50% 的評(píng)測(cè)用例，1 ≤ N, M ≤ 1000。 對(duì)于 100% 的評(píng)測(cè)用例，1 ≤ N, M, Bi ≤ ，??≤ Ki < 0。

試題 J: 魔法陣

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB 本題總分：25 分

【問題描述】

魔法師小藍(lán)為了營(yíng)救自己的朋友小 Q，來到了敵人布置的魔法陣。魔法陣 可以看作是一幅具有 N 個(gè)結(jié)點(diǎn) M 條邊的無向圖，結(jié)點(diǎn)編號(hào)為 0, 1, 2, . . . , N ? 1， 圖中沒有重邊和自環(huán)。敵人在每條邊上都布置了陷阱，每條邊都有一個(gè)傷害屬 性 w，每當(dāng)小藍(lán)經(jīng)過一條邊時(shí)就會(huì)受到這條邊對(duì)應(yīng)的 w 的傷害。小藍(lán)從結(jié)點(diǎn) 0

出發(fā)，沿著邊行走，想要到達(dá)結(jié)點(diǎn) N ? 1 營(yíng)救小 Q。 小藍(lán)有一種特殊的魔法可以使用，假設(shè)一條路徑按照順序依次經(jīng)過了以下

L 條邊：e1, e2, . . . , eL（可以出現(xiàn)重復(fù)的邊），那么期間小藍(lán)受到的總傷害就是

P = ∑L i=1 w(ei)，w(ei) 表示邊 ei 的傷害屬性。如果 L ≥ K，那么小藍(lán)就可以從 這 L 條邊當(dāng)中選出連續(xù)出現(xiàn)的 K 條邊 ec , ec+1, . . . , ec+K?1 并免去在這 K 條邊行 走期間所受到的傷害，即使用魔法之后路徑總傷害變?yōu)?P ′ = P ? ∑c+K?1

i=c w(ei)。 注意必須恰好選出連續(xù)出現(xiàn)的 K 條邊，所以當(dāng) L < K 時(shí)無法使用魔法。 小藍(lán)最多只可以使用一次上述的魔法，請(qǐng)問從結(jié)點(diǎn) 0 出發(fā)到結(jié)點(diǎn) N ? 1 受 到的最小傷害是多少？題目保證至少存在一條從結(jié)點(diǎn) 0 到 N ? 1 的路徑。

【輸入格式】

第一行輸入三個(gè)整數(shù)，N, K, M，用空格分隔。 接下來 M 行，每行包含三個(gè)整數(shù) u, v,w，表示結(jié)點(diǎn) u 與結(jié)點(diǎn) v 之間存在一 條傷害屬性為 w 的無向邊。

【輸出格式】

輸出一行，包含一個(gè)整數(shù)，表示小藍(lán)從結(jié)點(diǎn) 0 到結(jié)點(diǎn) N ? 1 受到的最小傷 害。

【樣例輸入 1】

4 2 3

0 1 2

1 2 1

2 3 4

【樣例輸出 1】

2

【樣例輸入 2】

2 5 1

0 1 1

【樣例輸出 2】

0

【樣例說明】

樣例 1，存在路徑：0 → 1 → 2 → 3，K = 2，如果在 0 → 1 → 2 上使用魔 法，那么答案就是 0 + 0 + 4 = 4；如果在 1 → 2 → 3 上使用魔法，那么答案就 是 2 + 0 + 0 = 2。再也找不到比 2 還小的答案了，所以答案就是 2。 樣例 2，存在路徑：0 → 1 → 0 → 1 → 0 → 1，K = 5，這條路徑總計(jì)恰好 走了 5 條邊，所以正好可以用魔法消除所有傷害，答案是 0。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 30% 的評(píng)測(cè)用例，1 ≤ N ≤ 20。 對(duì)于 50% 的評(píng)測(cè)用例，1 ≤ N ≤ 100。 對(duì)于 100% 的評(píng)測(cè)用例，1 ≤ N ≤ 1000, 1 ≤ M ≤ N×(N?1)/2 ，1 ≤ K ≤ 10, 0 ≤ u, v ≤ N ? 1，1 ≤ w ≤ 1000。文章來源地址http://www.zghlxwxcb.cn/news/detail-407902.html

到了這里，關(guān)于2023年第十四屆藍(lán)橋杯JAVA B組題目的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！