2021 附中暑期培訓模擬競賽 II | 競程

題目

pA - 機器鴨

有兩個長度為 $n$ 的序列 $a, b$ ，有隻機器鴨會從原點依照這個序列移動，第 $i$ 個時刻，機器鴨會直線移動向量 $(a_i, b_i)$ 。

請重新排列序列 $a, b$ ，使得機器鴨能夠走回原點，並且移動過程中不會走到已經走過的點。無解輸出 $-1$ 。

$3 \leq n \leq 100$
$1 \leq |a_i|, |b_i| \leq 300$
$a_i \neq a_j$

子任務	分數	額外輸入限制
1	5	$n = 3$
2	20	$n \leq 6$
3	28	$\forall 1 \leq i < n, b_i = 1$
4	47	無額外限制

pB - 惡地之路

$n$ 點 $m$ 邊帶權無向圖，每條邊有權重 $p_i$ ，定義從某點 $s$ 走到 $t$ 的票價為「路徑的權重和 $\times$ 經過的邊數」。

輸出從節點 $1$ 走到節點 $1 \sim n$ 的最小票價。

$1 \leq n \leq 2000$
$1 \leq m \leq 30000$
$1 \leq p_i \leq 10^6$

子任務	分數	額外輸入限制
1	8	$n \leq 5, m \leq 10$
2	5	$s = 1, m = n - 1$ ，且對於所有編號 $1$ 到 $n - 1$ 的轉乘站 $i$ ，都與轉乘站 $i + 1$ 有道路連接
3	12	$m = n - 1$
4	14	每個轉乘站都恰有兩條道路與其他轉乘站連接
5	20	$n \leq 100$
6	23	$n \leq 300, m \leq 1000$
7	18	無額外限制

pC - 調色盤

有一長度為 $n$ 的序列 $c$ ，並有一數字 $k$ 。

$q$ 筆詢問 $(l, r)$ ，求有多少數對 $(i, j)$ ，滿足 $l \leq c_i \leq c_j \leq r \land |c_i| - |c_j| \leq k$ 。

$1 \leq n, k, q, c_i \leq 10^6$

子任務	分數	額外輸入限制
1	3	$k = 10^6$
2	7	$n, q \leq 50$
3	12	$n, q \leq 500$
4	18	$n, q \leq 10000$
5	21	$n, q \leq 10^5$
6	39	無額外限制

pD - 告示牌

$n$ 個字串 $s_1,...,s_n$ 要寫到一個告示牌上，一個字串必定只能出現在一行，不可斷開。

在不超過 $k$ 行的情況下，告示牌最少需要有多寬？

$1 \leq k, \sum_{i=1}^{n} |s_i| \leq 2 \times 10^5$

子任務	分數	額外輸入限制
1	3	$s$ 中沒有空白
2	9	$\vert s \vert \leq 20$
3	16	$\vert s \vert \leq 1000$
4	73	無額外限制

pE - 變色蠑螈

一種魔法可用數對 $(a, b)$ 表示，代表可以將數字 $a$ 轉換成數字 $b$ ，或是反過來將 $b$ 轉換成 $a$ 。

現在有 $n$ 個要求，每個要求以 $(c, d)$ 表示，表示要將數字 $c$ 轉換成數字 $d$ ，請問最少需要學會幾種魔法才能達成上述要求。

$1 \leq n \leq 2 \times 10^5$
$1 \leq a, b, c, d \leq 10^9$

子任務	分數	額外輸入限制
1	6	$c_1 = c_2 = \dots = c_n$
2	4	$c_i, d_i \leq 2$
3	9	$c_i, d_i \leq 4$
4	17	$n, c_i \leq 1000$
5	31	$c_i \leq 2 \times 10^5$
6	33	無額外限制

比賽結果

2021 summer practice contest 2
------------------------------
Problem Difficulty:
pD < pE < pB < pC < pA
------------------------------
00:40 pA 0
00:42 pA 0
00:45 pA 0
00:50 pA 0
00:52 pA 0
01:11 pB 39
01:19 pB 39
01:22 pB 39
01:25 pB 39
01:42 pB 39
01:57 pD 100
02:05 pA 28
02:49 pC 37
02:52 pC 37
02:55 pE 6
02:59 pE 0
------------------------------
Score Gained:
pA 28
pB 39
pC 37
pD 100
pE 6

Total Score: 210
Final Rank:  2nd

比賽過程

賽前 5 分鐘還跑去拉肚子，有點雷。

開場時網路爛掉，pE 點「下載題本」一直沒反應，於是重複點了 20 幾次，最後受不了去看其他題，正要看的時候剛剛的按鈕突然全部有了反應，於是我又連續 20 幾次點了「取消下載」，有夠靠北。

一樣先讀題，15 分鐘。比較慘的是我 pA 跟 pE 沒讀仔細，漏了關鍵限制，所以難度排序一整個大亂。

當時的難度排序：pA < pD < pB < pC < pE，幾乎把正確順序整個倒過來。

pA 以為鴨子移動過程可視為瞬間移動，想說只要 $\sum a_i$ 跟 $\sum b_i$ 都 $=0$ 那隨便排列 $a, b$ 都有高機率是正確答案。但我忘記是直線前進所以經過的路徑也不能有交點。

不只讀錯題想法還一點都不嚴謹，有夠笨。反正就以為是簽到題就開始寫下去了。

結果過程中碰到很弔詭的 bug，題本疑似有不乾淨的字元，我直接複製到 code 底下再貼到 console 竟然沒辦法輸入，於是又重新檢查模板、主程式，又換了好幾次寫法，最後改成手動輸入才終於安分地吃進數字。莫名其妙地又浪費二十分鐘在解決看不見的 bug。

上面那個是爛掉的輸入，下面是好的，有夠奇怪。

丟上去結果吃了 WA（賽後覺得吃 WA 不意外）。

00:40 pA 0分

賽中沒發現是題目讀錯，又耍智障了 15 分鐘結果一分都沒有

00:42 pA 0分

00:45 pA 0分

00:50 pA 0分

00:52 pA 0分

前面發生的一堆意外、pA 一直燒，加上過了一個小時卻一分都沒有。這時心態基本上已經崩了，完全不想繼續寫下去。觸犯比賽的大忌。

上廁所回來，心情恢復一些但沒完全回復，這時選擇繼續想其他題目。

pB 最短路徑，感覺可以直接砸 dijkstra，但沒有想清楚這其實是假解。

pC 完全不會，區間問題是我的痛點，只有 $O(nq)$ 雙指針的想法。

pD 裸二分搜，有信心直接 AC。

pE 讀題目的時候有讀到一個魔法可以從 a 變成 b 也可以反過來（無向邊），但放到腦中思考的時候自動變成了有向邊，於是就卡住，完全沒注意到這是並查集水題 QQ。

這時我覺得 pD 雖然比較簡單，但我實作 dijkstra 比較穩定，於是就先從 pB 開始寫。10 分鐘後寫完就丟上去了。

01:11 pB 3 9分

有點慶幸總算有分數了，但我預期的是滿分，百思不解又繼續盯著 code，然後開始很智障地改一些沒有用處的實作小細節。這樣一拖又浪費了 30 分鐘

01:19 pB 3 9分

01:22 pB 3 9分

01:25 pB 3 9分

01:42 pB 3 9分

心態又更糟了，甚至一度認為是測資的問題。上完廁所後才終於肯跳題。

pD 穩定地刻完二分搜就丟上去了，一發 AC。應該先寫這題來穩住心態的。

01:57 pD 10 0分

接下來開始撈分，首先是 pA，這時候我才注意到我看錯題目，被自己笨死。

讀了子題，前 25 分可以暴力 $O((n!)^2 \times n^2)$ 拿掉，28 分觀察到可以先對 $a$ 排序，前 $n-1$ 個向量所形成的軌跡會是一個下凸包，最後則回到原點。於是改了一下剛剛的 code，丟上去 28 分。

02:05 pA 2 8分

這時候想刻 25 暴力分，沒想到除了要重寫外還需要刻向量模板。但我完全沒注意到 pC 更好撈而且分數更多，眼裡就只有 pA。

悲慘的是，我寫爛了，連範測都沒過。

剩下半個小時才驚覺時間不夠，這時才跳去 pC。邊寫邊想實作細節，幸好沒有出問題。

02:49 pC 3 7分

3 分只要加個特判就行了，多加幾行 if 丟上去我就去撈 pE 了，沒有去注意有沒有拿到，結果竟然沒有。

02:52 pC 3 7分

pE 的 6 分只要把 pair 丟進 set 就行了。

02:55 pE 6分

再來有 4 分是只要分 case，但因為我沒注意到邊是雙向的所以就沒有拿到 QQ。

02:59 pE 0分

賽後檢討

一樣先列出這場出狀況＆耍智障的地方。

賽前拉肚子／開場網路爛掉／pA 輸入吃到奇怪字元。
pA 讀錯題目。
pB 單層 dijkstra 大假解，分層 dijkstra 可以拿 82 分，完整做法是 DP。對分層 dijkstra 還不是很熟，這是我的盲點。
pD 最簡單沒有先寫。
pE 思考的時候忘記是無向邊，整場被自己雷死。
糟糕的難度排序。
pC 的 3 分沒拿到，是因為我在拿 37 分的時候為了加快 judge 結果，特意加了這行：
```
if (n > 10000) return 0;
```
結果忘記拔掉 qwq。

總檢討

賽前

不要熬夜，11 點前就要上床。
可以寫些水題維持手感也穩住心態。
賽前一小時就要睡午覺，睡半小時起來才有時間讓腦袋暖機。
深呼吸告訴自己「我超電」、「我可以的」，但不是「我一定可以拿 300 分」。

策略修正

開場讀題 15 分鐘，讀題時務必連子題配分都要讀過一遍。
打模板的時間 5 分鐘，打的時候不要一直思考有什麼忘記打，浪費腦力，反正之後要用再補就好。
按照難度排序題目的技能要再加強。
時間分配：
- 觀察性質 3 分鐘
- 思考解法 7 分鐘
- 總實作時間 20 分鐘
- debug 10 分鐘
拿分間隔控制在 20 分鐘，最多不超過 30 分鐘。停損點：思考 10 分鐘連 subtask 都沒想法就跳，卡了 40 分鐘一定要跳，不要一直想「"應該"還差一點就 AC 了」。
觀察性質：
- 注意變數範圍，誰特別大／特別小，作法 80% 跟它有關。
- 題目「保證」某種性質 $\rightarrow$ ，作法 99% 跟它有關。
- 常見手法：
  - 對 OOO 排序
  - 數值丟到數線上
  - 數對 (a, b) $\rightarrow$ 二維平面
  - 區間問題：離線、雙指針、單調性
思考解法：
- 寫下範測，釐清題目。
- 可以構造複雜點的測資幫助思考。
停損點：10 分鐘。
實作：
- 想到什麼 subtask 就寫什麼。
- 評估實作細節 2~3 分鐘。
- 分段 check 程式。
停損點：20 分鐘。
debug 時，先用 1 分鐘檢查有沒有智障 bug。
- 沒開 long long
- 陣列戳出界
- 寫好的函式忘記呼叫
- 0-base／1-base
- 忘記初始化
- ==打成=
構造測資，可以試試邊界測資，不要一直盯著 code。有可能假解只是自己沒發現。停損點：10 分鐘。

賽中心態調整

把比賽想成是跟出題者決鬥，AC 了代表運氣好決鬥獲勝，WA 了也只代表沒有打贏出題者，滿正常的事，絕對不要認為是因為自己實作爛實力爛，換一題跟他打就好。
不要急著想拿滿分，大部分的 AC 都是一點一點分數累積上去的，就算想到滿分解也是一樣。
丟一筆 submission 就去廁所，過半場吃點心。
換題的時候，一切重新 reset，剛剛發生了什麼事都不重要，不要掛在心上。
你炸掉大家也都會炸掉。

題目

比賽結果

比賽過程

賽後檢討

總檢討

賽前

策略修正

賽中心態調整

實用文章