tags: Competitive Programming

2021 附中資訊暑培模擬賽 賽後檢討

模擬競賽 I

題目

pA

直播循環
一個直播循環是由

$s$ 天的直播時段和

$r$ 天的休息時間構成。
現有位直播主要進行

$n$ 個遊戲的直播，第

$i$ 個遊戲需在某個循環的第

$a_i$ 天遊玩。且每個遊戲直播之間須間隔至少

$r$ 天的休息日。
求最少需幾個直播循環才能至少玩過所有遊戲一遍，並輸出每個遊戲須在第幾個循環進行直播（輸入任一種安排方式）。

---

$n\le 2\times {10}^5$

$0\le r\le s\le {10}^9$

---

Subtask

pB

兔田彩券
給定

$m$ 個數對

$(a_i,b_i),a_i\ne b_i$，每個數對的數字皆

$\le n$。
接著有

$q$ 筆詢問，每筆詢問給定

$(l,r,s,t)$，求有多少數對

$(a_i,b_i)$ 滿足

$(l\le a_i\le r\wedge s\le b_i\le t)$ 或

$(l\le b_i\le r\wedge s\le a_i\le t)$。

---

$1\le n\le 2000$

$1\le m,q\le 2\times {10}^5$

---

Subtask

pC

魔法師測驗
有一棵

$n$ 個節點的樹，每個節點有權重

$a_i$，求最長的路徑滿足路徑上的節點權重

$gcd\ne 1$，輸出該路徑的節點數。

---

$1\le n,a_i\le 2\times {10}^5$

---

Subtask

pD

刷怪塔
有

$T$ 筆測資，每筆測資有兩個數字

$a,b$。

令

$s$ 初始為

$1$，定義一次操作如下：

1. 選擇
   $a,b$ 數字較大者（若相同則選擇
   $a$），並將該數字減去
   $s$。
2. 將
   $s$ 的值增加
   $1$。

重複操作直到

$a,b$ 皆

$\le s$。

輸出總操作次數。

---

$1\le T\le {10}^5$

$0\le a,b\le {10}^{18}$

---

Subtask

pE

時空旅人之爭
有一棵

$n$ 個節點的樹，自第

$0$ 秒開始，複製人便佔領節點

$1$，並且每隔

$2$ 秒往相鄰節點擴散。

接著有

$q$ 筆詢問

$(s,t)$，代表從節點

$s$ 開始經過最短路徑到達

$t$。時間從

$0$ 秒開始計算，每前往下一個節點需要

$1$ 秒。求這段路程中有多少節點已經被複製人佔領。

---

$1\le n,q\le 2\times {10}^5$

---

Subtask

比賽結果

Score：135／Rank：3rd
.

比賽過程

開賽先下載所有題本，大概先花了15分鐘閱讀題本。

當時的難度排序：pA < pE < pC < pD < pB

pA 在紙上畫了一些圖後，馬上就想到 greedy+STL 就好了。

感覺這是最簡單的題目，沒什麼猶豫就寫下去了，刻模板 10 分鐘，但寫到後面才發現完了，我連 STL 的操作都不太熟悉，於是把 multiset 砍掉換成 map 才終於刻完。丟上去一發 AC。

00:35 pA 100分

接下來輪流想其他題目的作法。

pE 也是畫圖出來之後，很快想到 LCA+倍增二分搜，加上最近剛好有補到 LCA，所以我對實作滿有信心的，這題於是被我排在前面。

pC 感覺樹 DP，有觀察到每個數字的質因數不多，可是還是沒有複雜度好的想法，只有想到枚舉每個

$\le 2\times {10}^5$ 的質因數後套樹直徑。

pD 二分搜，但還要分一堆 case，非常麻煩，感覺寫下去了就會炸掉。

pB 有注意到

$n$ 特別小，除此之外沒任何想法，感覺是要寫線段樹或是莫隊，我對這種區間問題真的完全沒轍QQ。但是有 15 分是很水的暴力分，寫完 5 分鐘就丟上去了。

01:04 pB 15分

pD 的 20 分也很好水，先拿了簡單二分搜的 8 分，再拿暴力 12 分。

這裡比較雷的點是，明明 8 分的二分搜很好寫（大概兩分鐘就可以寫完），但我心態上一直覺得二分搜才 8 分感覺沒什麼價值，莫名地一直猶豫到底要不要寫，或是去想正解，拖一拖結果拖了 15 分鐘才拿掉。我到底在想什麼啊wwwwwwwwww

01:27 pD 20分

這時已經過半場，pC 樹 DP 依舊只有那個暴力的想法，這題子題切得很細但我完全沒有認真讀，很主觀地認為這個做法頂多 10~20 分，加上對於 pE 的滿分解太過自信，也沒想著要撈分就直接刻下去了。

LCA 的部分很順，5 分鐘就搞定，但最後的倍增二分搜沒有想清楚就直接寫，導致碰到一大堆 bug，碰一個 bug 就多加幾行特判處理，搞到最後 code 長得很肥。

好不容易範測過了，丟上去，結果

02:01 pE 0分

心中默念一聲幹之後回去好好看子題，結果我連一條鍊的測資都沒過。於是隨便生了一個鍊的測資，結果又找到更多問題，但我沒有打算重寫，反而是在那複雜的 code 上面又多加了更多的 if。看似解決了又丟上去。

02:16 pE 0分

糟糕，心態越來越不對，已經砸了 50 分鐘在這題了但我沒有收手，給自己停損點但都是給假的。一直很懊惱很不捨，寫了那麼長的 code 但一分也沒有，抱著「只要再修一下可能就可以 AC 了，現在放棄的話前面那一個小時就全都白費」這種斷不開的糟糕想法一直燒到比賽剩 20 分鐘。

02:27 pE 0分
02:37 pE 0分

這時候頭已經很脹痛，腦中思緒全部打結，心態上又一直很自責、懊悔，暴躁到敲了幾下鍵盤後去上廁所，但心情還沒完全平復就又回到電腦桌前。

這時候才開始寫 pC 的暴力分，順便加個唬爛剪枝（按照質因數出現的次數排序做樹直徑）。質數篩 + 質因數分解 + 樹直徑 DP 刻完大概剩 5 分鐘，結果測了範測，完了，是爛的。最後就盯著 code 盯到結束前 30 秒，很情感地把 code 丟了上去，想當然的一分都沒有。

02:59 pC 0分

賽後檢討

先說說耍智障的地方，真的太多了。

1. pA 居然刻到後面才發現不能用 multiset 而要用 map。
2. pB 耍笨，套到二維平面上才發現只需要二維前綴和就行了，但我所有的思考過程全都在一維直線上，沒跳脫出來。
3. pC 有兩個智障 bug。
   • 我所有的 code 都是 1-based 的，但輸入數字的時候卻從 index 0 開始輸入。
   • 樹 DP 有一段 code
   ​​​​if (tag[u] == 0) {
   ​​​​    dp[u] = 0;
   ​​​​    return;
   ​​​​}
   

   關鍵在於不能馬上 return 而是要繼續 dfs，真是智障。
4. pE 爛在倍增二分搜，結果只是我沒有注意到我的寫法會讓指針跳到 LCA 上面。

策略的檢討留到最後面一起統整，但這整場打得真的很不滿意。

模擬競賽 II

題目

pA

機器鴨
有兩個長度為

$n$ 的序列

$a,b$，有隻機器鴨會從原點依照這個序列移動，第

$i$ 個時刻，機器鴨會直線移動向量

$(a_i,b_i)$。

請重新排列序列

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

$-1$。

---

$3\le n\le 100$

$1\le |a_i|,|b_i|\le 300$

$a_i\ne a_j$

---

Subtask

pB

惡地之路

$n$ 點

$m$ 邊帶權無向圖，每條邊有權重

$p_i$，定義從某點

$s$ 走到

$t$ 的票價為「路徑的權重和

$\times$ 經過的邊數」。

輸出從節點

$1$ 走到節點

$1\sim n$ 的最小票價。

---

$1\le n\le 2000$

$1\le m\le 30000$

$1\le p_i\le {10}^6$

---

Subtask

pC

調色盤
有一長度為

$n$ 的序列

$c$，並有一數字

$k$。

$q$ 筆詢問

$(l,r)$，求有多少數對

$(i,j)$，滿足

$l\le c_i\le c_j\le r\wedge |c_i|-|c_j|\le k$。

---

$1\le n,k,q,c_i\le {10}^6$

---

Subtask

pD

告示牌

$n$ 個字串

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

在不超過

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

---

$1\le k,\sum _{i=1}^n|s_i|\le 2\times {10}^5$

---

Subtask

pE

變色蠑螈
一種魔法可用數對

$(a,b)$ 表示，代表可以將數字

$a$ 轉換成數字

$b$，或是反過來將

$b$ 轉換成

$a$。

現在有

$n$ 個要求，每個要求以

$(c,d)$ 表示，表示要將數字

$c$ 轉換成數字

$d$，請問最少需要學會幾種魔法才能達成上述要求。

---

$1\le n\le 2\times {10}^5$

$1\le a,b,c,d\le {10}^9$

---

Subtask

比賽結果

Score：210／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 39分

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

01:19 pB 39分
01:22 pB 39分
01:25 pB 39分
01:42 pB 39分

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

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

01:57 pD 100分

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

讀了子題，前 25 分可以暴力

$O((n!{)}^2\times n^2)$ 拿掉，28 分觀察到可以先對

$a$ 排序，前

$n-1$ 個向量所形成的軌跡會是一個下凸包，最後則回到原點。於是改了一下剛剛的 code，丟上去 28 分。

02:05 pA 28分

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

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

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

02:49 pC 37分

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

02:52 pC 37分

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

02:55 pE 6分

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

02:59 pE 0分

賽後檢討

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

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

   結果忘記拔掉qwq。

總檢討

賽前

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

策略修正

1. 開場讀題 15 分鐘，讀題時務必連子題配分都要讀過一遍。

2. 打模板的時間 5 分鐘，打的時候不要一直思考有什麼忘記打，浪費腦力，反正之後要用再補就好。

3. 按照難度排序題目的技能要再加強。
   

   

4. 時間分配：

   • 觀察性質 3 分鐘
   • 思考解法 7 分鐘
   • 總實作時間 20 分鐘
   • debug 10 分鐘

   拿分間隔控制在 20 分鐘，最多不超過 30 分鐘。
   停損點：思考 10 分鐘連 subtask 都沒想法就跳，卡了 40 分鐘一定要跳，不要一直想「"應該"還差一點就 AC 了」。

5. 觀察性質：

   • 注意變數範圍，誰特別大／特別小，作法 80% 跟它有關。
   • 題目「保證」某種性質
     $\to$，作法 99% 跟它有關。
   • 常見手法：
     • 對 OOO 排序
     • 數值丟到數線上
     • 數對 (a, b)
       $\to$ 二維平面
     • 區間問題：離線、雙指針、單調性

6. 思考解法：

   • 寫下範測，釐清題目。
   • 可以構造複雜點的測資幫助思考。

   停損點：10 分鐘。

7. 實作：

   • 想到什麼 subtask 就寫什麼。
   • 評估實作細節 2~3 分鐘。
   • 分段 check 程式。

   停損點：20 分鐘。

8. debug 時，先用 1 分鐘檢查有沒有智障 bug。

   • 沒開 long long
   • 陣列戳出界
   • 寫好的函式忘記呼叫
   • 0-base／1-base
   • 忘記初始化
   • ==打成=

   構造測資，可以試試邊界測資，不要一直盯著 code。
   有可能假解只是自己沒發現。
   停損點：10 分鐘。

賽中心態調整

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

實用文章

1. IOI 前國手 張程凱 - IOI 準備心得

2. IOI 前國手 曹宸睿 - TOI 入營考訓練

3. TOI 一階電神 林柏瑄 - 2021 TOI 心得文

4. 電神們的建議