散文網(wǎng) » 科技 »數(shù)碼 » 2022 CSP-S2復(fù)賽真題

2022 CSP-S2復(fù)賽真題

2022-10-30 08:28 作者:逗比的吳銘世 0人讀過 | 我要投稿

T1:假期計劃

題目描述

小熊的地圖上有? $n$ ?個點，其中編號為? $1$ ?的是它的家、編號為 $2, 3, \dots, n$ ?的都是景點。部分點對之間有雙向直達(dá)的公交線路。如果點? $x$ ?與? $z^{1}$ 、 $z^{1}$ ?與? $z^{2}$ 、……、 $z(^{k ? 1)}$ ?與? $z(^{k)}$ 、 $z(^{k)}$ ?與? $y$ ?之間均有直達(dá)的線路，那么我們稱? $x$ ?與? $y$ ?之間的行程可轉(zhuǎn)車? $k$ ?次通達(dá)；特別地，如果點? $x$ ?與? $y$ ?之間有直達(dá)的線路，則稱可轉(zhuǎn)車? $0$ ?次通達(dá)。

很快就要放假了，小熊計劃從家出發(fā)去? $4$ ?個不同的景點游玩，完成? $5$ ?段行程后回家：家 $\to$ ?景點 A $\to$ ?景點 B? $\to$ ?景點 C? $\to$ ?景點 D? $\to$ ?家，且每段行程最多轉(zhuǎn)車? $k$ ?次。轉(zhuǎn)車時經(jīng)過的點沒有任何限制，既可以是家、也可以是景點，還可以重復(fù)經(jīng)過相同的點。例如，在景點 A? $\to$ ?景點 B 的這段行程中，轉(zhuǎn)車時經(jīng)過的點可以是家、也可以是景點 C，還可以是景點 D $\to$ ?家這段行程轉(zhuǎn)車時經(jīng)過的點。

假設(shè)每個景點都有一個分?jǐn)?shù)，請幫小熊規(guī)劃一個行程，使得小熊訪問的四個不同景點的分?jǐn)?shù)之和最大。

需要注意的是：這四個景點并不是給定的，而是自己選取的。

輸入格式

第一行包含三個正整數(shù)? $n, m, k$ 分別表示地圖上點的個數(shù)、雙向直達(dá)的點對數(shù)量、每段行程最多的轉(zhuǎn)車次數(shù)。

第二行包含 $n ? 1$ ?個正整數(shù)，分別表示編號為 $2, 3, \dots, n$ ?的景點的分?jǐn)?shù)。

接下來? $m$ ?行，每行包含兩個正整數(shù)? $x, y$ 表示點? $x$ ?和? $y$ ?之間有道路直接相連，保證? $1 \leq x, y \leq n$ ，且沒有重邊，自環(huán)。

輸出格式

輸出一個正整數(shù)，表示小熊經(jīng)過的? $4$ ?個不同景點的分?jǐn)?shù)之和的最大值。

輸入輸出樣例

輸入樣例#1

8 8 1?

9 7 1 8 2 3 6

1 2?

2 3?

3 4

4 5

5 6

6 7

7 8

8 1

輸出樣例 #1

27

輸入樣例#2

7 9 0?

1 1 1 2 3 4

1 2

2 3

3 4

1 5

1 6?

1 7?

5 4?

6 4?

7 4

輸出樣例#2

7

說明/提示

【樣例解釋 #1】

當(dāng)計劃的行程為? $1 \to 2 \to 3 \to 5 \to 7 \to 1$ ?時， $4$ ?個景點的分?jǐn)?shù)之和為? $9 + 7 + 8 + 3 = 27$ ，可以證明其為最大值。

附：行程? $1 \to 3 \to 5 \to 7 \to 8 \to 1$ ?的景點分?jǐn)?shù)之和為? $24$ 、行程? $1 \to 3 \to 2 \to 8 \to 7 \to 1$ ?的景點分?jǐn)?shù)之和為? $25$ 。它們都符合要求，但分?jǐn)?shù)之和不是最大的。

行程 $1 \to 2 \to 3 \to 5 \to 8 \to 1$ ?的景點分?jǐn)?shù)之和為? $30$ ，但其中 $5 \to 8$ ?至少需要轉(zhuǎn)車? $2$ ?次，因此不符合最多轉(zhuǎn)車? $k = 1$ ?次的要求。

行程 $1 \to 2 \to 3 \to 2 \to 3 \to 1$ ?的景點分?jǐn)?shù)之和為? $32$ ，但游玩的并非? $4$ ?個不同的景點，因此也不符合要求。

【樣例 #3】

見附件中的?holiday/holiday3.in?與?holiday/holiday3.ans。

【數(shù)據(jù)范圍】

對于所有數(shù)據(jù)，保證 $5 \leq n \leq 2500$ ， $1 \leq m \leq 10000$ ， $0 \leq k \leq 100$ ，所有景點的分?jǐn)?shù) $1 \leq s^{i} \leq 100000000$ 。保證至少存在一組符合要求的行程。

T2：策略游戲

題目描述

小 L 和小 Q 在玩一個策略游戲。

有一個長度為? $n$ ?的數(shù)組? $A$ ?和一個長度為? $m$ ?的數(shù)組? $B$ ，在此基礎(chǔ)上定義一個大小為 $n \times m$ ?的矩陣? $C$ ，滿足 $C^{i j} = A^{i} \times B^{j}$ 。所有下標(biāo)均從? $1$ ?開始。

游戲一共會進(jìn)行? $q$ ?輪，在每一輪游戲中，會事先給出? $4$ ?個參數(shù)? $l^{1}, r^{1}, l^{2}, r^{2}$ ，滿足 $1 \leq l^{1} \leq r^{1} \leq n$ 、 $1 \leq l^{2} \leq r^{2} \leq m$ 。

游戲中，小 L 先選擇一個? $l^{1} ～ r^{1}$ ?之間的下標(biāo)? $x$ ，然后小 Q 選擇一個 $l^{2} ～ r^{2}$ ?之間的下標(biāo)? $y$ 。定義這一輪游戲中二人的得分是 $C^{x y}$ 。

小 L 的目標(biāo)是使得這個得分盡可能大，小 Q 的目標(biāo)是使得這個得分盡可能小。同時兩人都是足夠聰明的玩家，每次都會采用最優(yōu)的策略。

請問：按照二人的最優(yōu)策略，每輪游戲的得分分別是多少？

輸入格式

第一行輸入三個正整數(shù) $n, m, q$ ，分別表示數(shù)組 $A$ ，數(shù)組 $B$ 的長度和游戲輪數(shù)。

第二行： $n$ ?個整數(shù)，表示 $A^{i}$ ，分別表示數(shù)組? $A$ ?的元素。

第三行： $m$ ?個整數(shù)，表示 $B^{i}$ ，分別表示數(shù)組? $B$ ?的元素。

接下來? $q$ ?行，每行四個正整數(shù)，表示這一次游戲的 $l^{1}, r^{1}, l^{2}, r^{2}$ 。

輸出格式

輸出共? $q$ ?行，每行一個整數(shù)，分別表示每一輪游戲中，小 L 和小 Q 在最優(yōu)策略下的得分。

輸入輸出樣例

輸入樣例#1

3 2 2

0 1 -2?

-3 4?

1 3 1 2?

2 3 2 2

輸出樣例#1

0

4

輸入樣例 #2

6 4 5?

3 -1 -2 1 2 0

1 2 -1 -3

1 6 1 4

1 5 1 4

1 4 1 2

2 6 3 4?

2 5 2 3

輸出樣例#2

0?

-2?

3

2

-1

說明/提示

【樣例解釋 #1】

這組數(shù)據(jù)中，矩陣? $C$ ?如下：

在第一輪游戲中，無論小 L 選取的是? $x = 2$ ?還是? $x = 3$ ，小 Q 都有辦法選擇某個? $y$ ?使得最終的得分為負(fù)數(shù)。因此小 L 選擇? $x = 1$ ?是最優(yōu)的，因為這樣得分一定為? $0$ 。

而在第二輪游戲中，由于小 L 可以選 $x = 2$ ，小 Q 只能選 $y = 2$ ，如此得分為? $4$ 。

【樣例 #3】

見附件中的?game/game3.in?與?game/game3.ans。

【樣例 #4】

見附件中的?game/game4.in?與?game/game4.ans。

【數(shù)據(jù)范圍】

對于所有數(shù)據(jù)， $1 \leq n, m, q \leq 100000$ ， $? 1000000000 \leq A^{i}, B^{i} \leq 1000000000$ 。對于每輪游戲而言， $1 \leq l^{1} \leq r^{1} \leq n$ ， $1 \leq l^{2} \leq r^{2} \leq m$ 。

其中，特殊性質(zhì) 1 為：保證 $A^{i}, B^{i} > 0$ 。
特殊性質(zhì) 2 為：保證對于每輪游戲而言，要么 $l^{1} = r^{1}$ ，要么 $l^{2} = r^{2}$ 。

T3：星戰(zhàn)

題目描述

在這一輪的星際戰(zhàn)爭中，我方在宇宙中建立了? $n$ ?個據(jù)點，以? $m$ ?個單向蟲洞連接。我們把終點為據(jù)點? $u$ ?的所有蟲洞歸為據(jù)點? $u$ ?的蟲洞。

戰(zhàn)火紛飛之中這些蟲洞很難長久存在，敵人的打擊隨時可能到來。這些打擊中的有效打擊可以分為兩類：

敵人會摧毀某個蟲洞，這會使它連接的兩個據(jù)點無法再通過這個蟲洞直接到達(dá)，但這樣的打擊無法摧毀它連接的兩個據(jù)點。
敵人會摧毀某個據(jù)點，由于蟲洞的主要技術(shù)集中在出口處，這會導(dǎo)致該據(jù)點的所有還未被摧毀的蟲洞被一同摧毀。而從這個據(jù)點出發(fā)的蟲洞則不會摧毀。

注意：摧毀只會導(dǎo)致蟲洞不可用，而不會消除它的存在。

為了抗擊敵人并維護各部隊和各據(jù)點之間的聯(lián)系，我方發(fā)展出了兩種特種部隊負(fù)責(zé)修復(fù)蟲洞：

A 型特種部隊則可以將某個特定的蟲洞修復(fù)。
B 型特種部隊可以將某據(jù)點的所有損壞的蟲洞修復(fù)。

考慮到敵人打擊的特點，我方并未在據(jù)點上儲備過多的戰(zhàn)略物資。因此只要這個據(jù)點的某一條蟲洞被修復(fù)，處于可用狀態(tài)，那么這個據(jù)點也是可用的。

我方掌握了一種苛刻的空間特性，利用這一特性我方戰(zhàn)艦可以沿著蟲洞瞬移到敵方陣營，實現(xiàn)精確打擊。

為了把握發(fā)動反攻的最佳時機，指揮部必須關(guān)注戰(zhàn)場上的所有變化，為了尋找一個能夠進(jìn)行反攻的時刻。總指揮認(rèn)為：

如果從我方的任何據(jù)點出發(fā)，在選擇了合適的路線的前提下，可以進(jìn)行無限次的蟲洞穿梭（可以多次經(jīng)過同一據(jù)點或同一蟲洞），那么這個據(jù)點就可以實現(xiàn)反擊。
為了使蟲洞穿梭的過程連續(xù)，盡量減少戰(zhàn)艦在據(jù)點切換蟲洞時的質(zhì)能損耗，當(dāng)且僅當(dāng)只有一個從該據(jù)點出發(fā)的蟲洞可用時，這個據(jù)點可以實現(xiàn)連續(xù)穿梭。
如果我方所有據(jù)點都可以實現(xiàn)反擊，也都可以實現(xiàn)連續(xù)穿梭，那么這個時刻就是一個絕佳的反攻時刻。

總司令為你下達(dá)命令，要求你根據(jù)戰(zhàn)場上實時反饋的信息，迅速告訴他當(dāng)前的時刻是否能夠進(jìn)行一次反攻。

輸入格式

輸入的第一行包含兩個正整數(shù) $n, m$ 。

接下來? $m$ ?行每行兩個數(shù)? $u, v$ ，表示一個從據(jù)點? $u$ ?出發(fā)到據(jù)點? $v$ ?的蟲洞。保證? $=? v (即u不等于v)$ ，保證不會有兩條相同的蟲洞。初始時所有的蟲洞和據(jù)點都是完好的。

接下來一行一個正整數(shù)? $q$ ?表示詢問個數(shù)。

接下來? $q$ ?行每行表示一次詢問或操作。首先讀入一個正整數(shù)? $t$ ?表示指令類型：

若? $t = 1$ ，接下來兩個整數(shù)? $u, v$ ?表示敵人摧毀了從據(jù)點? $u$ ?出發(fā)到據(jù)點? $v$ ?的蟲洞。保證該蟲洞存在且未被摧毀。
若? $t = 2$ ，接下來一個整數(shù)? $u$ ?表示敵人摧毀了據(jù)點? $u$ 。如果該據(jù)點的蟲洞已全部被摧毀，那么這次襲擊不會有任何效果。
若? $t = 3$ ，接下來兩個整數(shù)? $u, v$ ?表示我方修復(fù)了從據(jù)點? $u$ ?出發(fā)到據(jù)點? $v$ ?的蟲洞。保證該蟲洞存在且被摧毀。
若? $t = 4$ ，接下來一個整數(shù)? $u$ ?表示我方修復(fù)了據(jù)點? $u$ 。如果該據(jù)點沒有被摧毀的蟲洞，那么這次修復(fù)不會有任何效果。

在每次指令執(zhí)行之后，你需要判斷能否進(jìn)行一次反攻。如果能則輸出?YES?，否則輸出?NO。

輸出格式

輸出一共? $q$ ?行。對于每個指令，輸出這個指令執(zhí)行后能否進(jìn)行反攻。

輸入輸出樣例

輸入樣例 #1

3 6

2 3

2 1?

1 2

1 3

3 1

3 2

11

1 3 2?

1 2 3?

1 1 3?

1 1 2?

3 1 3?

3 3 2?

2 3

1 3 1

3 1?3?

4 2?

1 3 2

輸出樣例 #1

NO

YES?

NO

YES

NO?

YES

NO?

NO

說明/提示

【樣例解釋 #1】

蟲洞狀態(tài)可以參考下面的圖片, 圖中的邊表示存在且未被摧毀的蟲洞：

【樣例 #2】

見附件中的?galaxy/galaxy2.in?與?galaxy/galaxy2.ans。

【樣例 #3】

見附件中的?galaxy/galaxy3.in?與?galaxy/galaxy3.ans。

【樣例 #4】

見附件中的?galaxy/galaxy4.in?與?galaxy/galaxy4.ans。

【數(shù)據(jù)范圍】

對于所有數(shù)據(jù)保證： $1 \leq n \leq 500000$ ， $1 \leq m \leq500000$ ， $1 \leq q \leq 500000$ 。

T4：數(shù)據(jù)傳輸

題目描述

小 C 正在設(shè)計計算機網(wǎng)絡(luò)中的路由系統(tǒng)。

測試用的網(wǎng)絡(luò)總共有? $n$ ?臺主機，依次編號為 $1 ～ n$ 。這? $n$ 臺主機之間由? $n ? 1$ ?根網(wǎng)線連接，第? $i$ ?條網(wǎng)線連接個主機? $a^{i}$ ?和? $b^{i}$ 。保證任意兩臺主機可以通過有限根網(wǎng)線直接或者間接地相連。受制于信息發(fā)送的功率，主機? $a$ ?能夠直接將信息傳輸給主機? $b$ ?當(dāng)且僅當(dāng)兩個主機在可以通過不超過? $k$ ?根網(wǎng)線直接或者間接的相連。

在計算機網(wǎng)絡(luò)中，數(shù)據(jù)的傳輸往往需要通過若干次轉(zhuǎn)發(fā)。假定小 C 需要將數(shù)據(jù)從主機? $a$ ?傳輸?shù)街鳈C? $b$ （ $=? b$ ），則其會選擇出若干臺用于傳輸?shù)闹鳈C $c^{1} = a， c^{2}, \dots, c(^{m ? 1)，} c(m) = b$ ，并按照如下規(guī)則轉(zhuǎn)發(fā)：對于所有的? $1 \leq i < m$ ，主機? $c^{i}$ ?將信息直接發(fā)送給? $c^{i + 1}$ 。

每臺主機處理信息都需要一定的時間，第? $i$ ?臺主機處理信息需要? $v^{i}$ ?單位的時間。數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸非常迅速，因此傳輸?shù)臅r間可以忽略不計。據(jù)此，上述傳輸過程花費的時間為：?

現(xiàn)在總共有? $q$ ?次數(shù)據(jù)發(fā)送請求，第? $i$ ?次請求會從主機? $s^{i}$ ?發(fā)送數(shù)據(jù)到主機? $t^{i}$ 。小 C 想要知道，對于每一次請求至少需要花費多少單位時間才能完成傳輸。

輸入格式

輸入的第一行包含三個正整數(shù)? $n, Q, k$ ，分別表示網(wǎng)絡(luò)主機個數(shù)，請求個數(shù)，傳輸參數(shù)。數(shù)據(jù)保證? $1 \leq n \leq 200000$ ， $1 \leq Q \leq 200000$ ， $1 \leq k \leq 3$ 。

輸入的第二行包含? $n$ ?個正整數(shù)，第? $i$ ?個正整數(shù)表示? $v^{i}$ ，保證? $1 \leq v^{i} \leq 1000000000$ 。

接下來? $n ? 1$ ?行，第? $i$ ?行包含兩個正整數(shù)? $a^{i}, b^{i}$ ，表示一條連接主機? $a^{i}, b^{i}$ ?的網(wǎng)線。保證? $1 \leq a^{i}, b^{i} \leq n$ 。

接下來? $Q$ ?行，第? $i$ ?行包含兩個正整數(shù)? $s^{i}, t^{i}$ ，表示一次從主機? $s^{i}$ ?發(fā)送數(shù)據(jù)到主機? $t^{i}$ ?的請求。保證 $1? \leq? s^{i}, t^{i?} \leq? n ($ $s^{i !=}$ $? t^{i)}$ 。

輸出格式

$Q$ ?行，每行一個正整數(shù)，表示第? $i$ ?次請求在傳輸?shù)臅r候至少需要花費多少單位的時間。

輸入輸出樣例

輸入 #1

7 3 3

1 2 3 4 5 6 7

1 2

1 3

2 4?

2 5?

3 6?

3 7?

4 7?

5 6?

1 2

輸出 #1

12?

3

說明/提示

【樣例解釋 #1】

對于第一組請求，由于主機? $4, 7$ ?之間需要至少? $4$ ?根網(wǎng)線才能連接，因此數(shù)據(jù)無法在兩臺主機之間直接傳輸，其至少需要一次轉(zhuǎn)發(fā)；我們讓其在主機? $1$ ?進(jìn)行一次轉(zhuǎn)發(fā)，不難發(fā)現(xiàn)主機? $1$ ?和主機? $4, 7$ ?之間都只需要兩根網(wǎng)線即可連接，且主機? $1$ ?的數(shù)據(jù)處理時間僅為? $1$ ，為所有主機中最小，因此最少傳輸?shù)臅r間為? $4 + 1 + 7 = 12$ 。

對于第三組請求，由于主機? $1, 2$ ?之間只需要? $1$ ?根網(wǎng)線就能連接，因此數(shù)據(jù)直接傳輸就是最優(yōu)解，最少傳輸?shù)臅r間為 $1 + 2 = 3$ 。

【樣例 #2】

見附件中的?transmit/transmit2.in?與?transmit/transmit2.ans。

該樣例滿足測試點? $2$ ?的限制。

【樣例 #3】

見附件中的?transmit/transmit3.in?與?transmit/transmit3.ans。

該樣例滿足測試點? $3$ ?的限制。

【樣例 #4】

見附件中的?transmit/transmit4.in?與?transmit/transmit4.ans。

該樣例滿足測試點? $20$ ?的限制。

【數(shù)據(jù)范圍】

對于所有的測試數(shù)據(jù)，滿足? $1 \leq n \leq 200000$ ， $1 \leq Q \leq 200000$ ， $1 \leq k \leq 3$ ， $1 \leq a^{i}, b^{i} \leq n$ ， $1 \leq s^{i}, t^{i} \leq n$ ， $s^{i !} =? t^{i}$ 。

特殊性質(zhì)：保證? $a^{i} = i + 1$ ，而? $b^{i}$ ?則從? $1, 2, \dots, i$ ?中等概率選取。

寫在最后：

應(yīng)該下周題解能寫好，如果大家有想法歡迎留言哦！

這回題出的幾乎全是樹和圖，T1也不想往年一樣搞一道簽到題，估計平均分也高不了太多吧。

打字不易，莫忘三連！~~~

標(biāo)簽：