###### tags: `Competitive Programming` <style> .lv1 { color: #e33d3d; font-weight: bold; } .lv2 { color: #e05e1d; font-weight: bold; } .lv3 { color: #bfad0b; font-weight: bold; } .lv4 { color: #1ec93b; font-weight: bold; } </style> # 2021 附中資訊暑培模擬賽 賽後檢討 ## 模擬競賽 I ### 題目 #### pA :::info **直播循環** 一個直播循環是由 $s$ 天的直播時段和 $r$ 天的休息時間構成。 現有位直播主要進行 $n$ 個遊戲的直播，第 $i$ 個遊戲需在某個循環的第 $a_i$ 天遊玩。且每個遊戲直播之間須間隔至少 $r$ 天的休息日。 求最少需幾個直播循環才能至少玩過所有遊戲一遍，並輸出每個遊戲須在第幾個循環進行直播（輸入任一種安排方式）。 **** $n \leq 2 \times 10^5$ $0 \leq r \leq s \leq 10^9$ **** **Subtask** ![](https://i.imgur.com/I7y0ACy.png) ::: #### pB :::info **兔田彩券** 給定 $m$ 個數對 $(a_i, b_i), a_i \neq b_i$，每個數對的數字皆 $\leq n$。 接著有 $q$ 筆詢問，每筆詢問給定 $(l, r, s, t)$，求有多少數對 $(a_i, b_i)$ 滿足 $(l \leq a_i \leq r \land s \leq b_i \leq t)$ 或 $(l \leq b_i \leq r \land s \leq a_i \leq t)$。 **** $1 \leq n \leq 2000$ $1 \leq m, q \leq 2 \times 10^5$ **** **Subtask** ![](https://i.imgur.com/JYOmDfQ.png) ::: #### pC :::info **魔法師測驗** 有一棵 $n$ 個節點的樹，每個節點有權重 $a_i$，求最長的路徑滿足路徑上的節點權重 $gcd \neq 1$，輸出該路徑的節點數。 **** $1 \leq n, a_i\leq 2 \times 10^5$ **** **Subtask** ![](https://i.imgur.com/pHaS4Eh.png) ::: #### pD :::info **刷怪塔** 有 $T$ 筆測資，每筆測資有兩個數字 $a, b$。 令 $s$ 初始為 $1$，定義一次操作如下： 1. 選擇 $a, b$ 數字較大者（若相同則選擇 $a$），並將該數字減去 $s$。 2. 將 $s$ 的值增加 $1$。 重複操作直到 $a, b$ 皆 $\leq s$。 輸出總操作次數。 **** $1 \leq T \leq 10^5$ $0 \leq a, b \leq 10^{18}$ **** **Subtask** ![](https://i.imgur.com/CPcdi8a.png) ::: #### pE :::info **時空旅人之爭** 有一棵 $n$ 個節點的樹，自第 $0$ 秒開始，複製人便佔領節點 $1$，並且每隔 $2$ 秒往相鄰節點擴散。 接著有 $q$ 筆詢問 $(s, t)$，代表從節點 $s$ 開始經過最短路徑到達 $t$。時間從 $0$ 秒開始計算，每前往下一個節點需要 $1$ 秒。求這段路程中有多少節點已經被複製人佔領。 **** $1 \leq n, q \leq 2 \times 10^5$ **** **Subtask** ![](https://i.imgur.com/Xxftbug.png) ::: ### 比賽結果 :::danger **Score：135／Rank：3rd** . ![](https://i.imgur.com/rXMMxTp.png) ::: ### 比賽過程 開賽先下載所有題本，大概先花了15分鐘閱讀題本。 當時的難度排序：`pA < pE < pC < pD < pB` pA 在紙上畫了一些圖後，馬上就想到 greedy+STL 就好了。 感覺這是最簡單的題目，沒什麼猶豫就寫下去了，刻模板 10 分鐘，但寫到後面才發現完了，我連 STL 的操作都不太熟悉，於是把 multiset 砍掉換成 map 才終於刻完。丟上去一發 AC。 <span class="lv4">**00:35 pA 100分**</span> 接下來輪流想其他題目的作法。 pE 也是畫圖出來之後，很快想到 LCA+倍增二分搜，加上最近剛好有補到 LCA，所以我對實作滿有信心的，這題於是被我排在前面。 pC 感覺樹 DP，有觀察到每個數字的質因數不多，可是還是沒有複雜度好的想法，只有想到枚舉每個 $\leq 2\times 10^5$ 的質因數後套樹直徑。 pD 二分搜，但還要分一堆 case，非常麻煩，感覺寫下去了就會炸掉。 pB 有注意到 $n$ 特別小，除此之外沒任何想法，感覺是要寫線段樹或是莫隊，我對這種區間問題真的完全沒轍QQ。但是有 15 分是很水的暴力分，寫完 5 分鐘就丟上去了。 <span class="lv2">**01:04 pB 15分**</span> pD 的 20 分也很好水，先拿了簡單二分搜的 8 分，再拿暴力 12 分。 這裡比較雷的點是，明明 8 分的二分搜很好寫（大概兩分鐘就可以寫完），但我心態上一直覺得二分搜才 8 分感覺沒什麼價值，莫名地一直猶豫到底要不要寫，或是去想正解，拖一拖結果拖了 15 分鐘才拿掉。我到底在想什麼啊wwwwwwwwww <span class="lv2">**01:27 pD 20分**</span> 這時已經過半場，pC 樹 DP 依舊只有那個暴力的想法，這題子題切得很細但我完全沒有認真讀，很主觀地認為這個做法頂多 10~20 分，加上對於 pE 的滿分解太過自信，也沒想著要撈分就直接刻下去了。 LCA 的部分很順，5 分鐘就搞定，但最後的倍增二分搜沒有想清楚就直接寫，導致碰到一大堆 bug，碰一個 bug 就多加幾行特判處理，搞到最後 code 長得很肥。 好不容易範測過了，丟上去，結果 <span class="lv1">**02:01 pE 0分**</span> 心中默念一聲幹之後回去好好看子題，結果我連一條鍊的測資都沒過。於是隨便生了一個鍊的測資，結果又找到更多問題，但我沒有打算重寫，反而是在那複雜的 code 上面又多加了更多的 if。看似解決了又丟上去。 <span class="lv1">**02:16 pE 0分**</span> 糟糕，心態越來越不對，已經砸了 50 分鐘在這題了但我沒有收手，給自己停損點但都是給假的。一直很懊惱很不捨，寫了那麼長的 code 但一分也沒有，抱著「**只要再修一下可能就可以 AC 了，現在放棄的話前面那一個小時就全都白費**」這種斷不開的糟糕想法一直燒到比賽剩 20 分鐘。 <span class="lv1">**02:27 pE 0分**</span> <span class="lv1">**02:37 pE 0分**</span> 這時候頭已經很脹痛，腦中思緒全部打結，心態上又一直很自責、懊悔，暴躁到敲了幾下鍵盤後去上廁所，但心情還沒完全平復就又回到電腦桌前。 這時候才開始寫 pC 的暴力分，順便加個唬爛剪枝（按照質因數出現的次數排序做樹直徑）。質數篩 + 質因數分解 + 樹直徑 DP 刻完大概剩 5 分鐘，結果測了範測，完了，是爛的。最後就盯著 code 盯到結束前 30 秒，很情感地把 code 丟了上去，想當然的一分都沒有。 <span class="lv1">**02:59 pC 0分**</span> ### 賽後檢討 先說說耍智障的地方，真的太多了。 1. pA 居然刻到後面才發現不能用 multiset 而要用 map。 2. pB 耍笨，套到二維平面上才發現只需要二維前綴和就行了，但我所有的思考過程全都在一維直線上，沒跳脫出來。 3. pC 有兩個智障 bug。 - 我所有的 code 都是 1-based 的，但輸入數字的時候卻從 index 0 開始輸入。 - 樹 DP 有一段 code ```cpp if (tag[u] == 0) { dp[u] = 0; return; } ``` 關鍵在於不能馬上 return 而是要繼續 dfs，真是智障。 4. pE 爛在倍增二分搜，結果只是我沒有注意到我的寫法會讓指針跳到 LCA 上面。 策略的檢討留到最後面一起統整，但這整場打得真的很不滿意。 ## 模擬競賽 II ### 題目 #### pA :::info **機器鴨** 有兩個長度為 $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$ **** **Subtask** ![](https://i.imgur.com/RYYx1b1.png) ::: #### pB :::info **惡地之路** $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$ **** **Subtask** ![](https://i.imgur.com/AAVdnJr.png) ::: #### pC :::info **調色盤** 有一長度為 $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$ **** **Subtask** ![](https://i.imgur.com/mKV7e2U.png) ::: #### pD :::info **告示牌** $n$ 個字串 $s_1,...,s_n$ 要寫到一個告示牌上，一個字串必定只能出現在一行，不可斷開。 在不超過 $k$ 行的情況下，告示牌最少需要有多寬？ **** $1 \leq k, \sum_{i=1}^{n} |s_i| \leq 2 \times 10^5$ **** **Subtask** ![](https://i.imgur.com/n8OUdlZ.png) ::: #### pE :::info **變色蠑螈** 一種魔法可用數對 $(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$ **** **Subtask** ![](https://i.imgur.com/r5xK5b9.png) ::: ### 比賽結果 :::warning **Score：210／Rank：2nd** . ![](https://i.imgur.com/LY1UmTe.png) ::: ### 比賽過程 賽前 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。 ![](https://i.imgur.com/M0ZVhKw.png) 上面那個是爛掉的輸入，下面是好的，有夠奇怪。 丟上去結果吃了 WA（賽後覺得吃 WA 不意外）。 <span class="lv1">**00:40 pA 0分**</span> 賽中沒發現是題目讀錯，又耍智障了 15 分鐘結果一分都沒有 <span class="lv1">**00:42 pA 0分**</span> <span class="lv1">**00:45 pA 0分**</span> <span class="lv1">**00:50 pA 0分**</span> <span class="lv1">**00:52 pA 0分**</span> 前面發生的一堆意外、pA 一直燒，加上過了一個小時卻一分都沒有。這時心態基本上已經崩了，完全不想繼續寫下去。觸犯比賽的大忌。 上廁所回來，心情恢復一些但沒完全回復，這時選擇繼續想其他題目。 pB 最短路徑，感覺可以直接砸 dijkstra，但沒有想清楚這其實是假解。 pC 完全不會，區間問題是我的痛點，只有 $O(nq)$ 雙指針的想法。 pD 裸二分搜，有信心直接 AC。 pE 讀題目的時候有讀到一個魔法可以從 a 變成 b 也可以反過來（無向邊），但放到腦中思考的時候自動變成了有向邊，於是就卡住，完全沒注意到這是並查集水題QQ。 這時我覺得 pD 雖然比較簡單，但我實作 dijkstra 比較穩定，於是就先從 pB 開始寫。10 分鐘後寫完就丟上去了。 <span class="lv3">**01:11 pB 39分**</span> 有點慶幸總算有分數了，但我預期的是滿分，百思不解又繼續盯著 code，然後開始很智障地改一些沒有用處的實作小細節。這樣一拖又浪費了 30 分鐘 <span class="lv3">**01:19 pB 39分**</span> <span class="lv3">**01:22 pB 39分**</span> <span class="lv3">**01:25 pB 39分**</span> <span class="lv3">**01:42 pB 39分**</span> 心態又更糟了，甚至一度認為是測資的問題。上完廁所後才終於肯跳題。 pD 穩定地刻完二分搜就丟上去了，一發 AC。應該先寫這題來穩住心態的。 <span class="lv4">**01:57 pD 100分**</span> 接下來開始撈分，首先是 pA，這時候我才注意到我看錯題目，被自己笨死。 讀了子題，前 25 分可以暴力 $O((n!)^2 \times n^2)$ 拿掉，28 分觀察到可以先對 $a$ 排序，前 $n-1$ 個向量所形成的軌跡會是一個下凸包，最後則回到原點。於是改了一下剛剛的 code，丟上去 28 分。 <span class="lv2">**02:05 pA 28分**</span> 這時候想刻 25 暴力分，沒想到除了要重寫外還需要刻向量模板。但我完全沒注意到 pC 更好撈而且分數更多，眼裡就只有 pA。 悲慘的是，我寫爛了，連範測都沒過。 剩下半個小時才驚覺時間不夠，這時才跳去 pC。邊寫邊想實作細節，幸好沒有出問題。 <span class="lv3">**02:49 pC 37分**</span> 3 分只要加個特判就行了，多加幾行 if 丟上去我就去撈 pE 了，沒有去注意有沒有拿到，結果竟然沒有。 <span class="lv3">**02:52 pC 37分**</span> pE 的 6 分只要把 pair 丟進 set 就行了。 <span class="lv2">**02:55 pE 6分**</span> 再來有 4 分是只要分 case，但因為我沒注意到邊是雙向的所以就沒有拿到QQ。 <span class="lv1">**02:59 pE 0分**</span> ### 賽後檢討 一樣先列出這場出狀況＆耍智障的地方。 1. 賽前拉肚子／開場網路爛掉／pA 輸入吃到奇怪字元。 2. pA 讀錯題目。 3. pB 單層 dijkstra 大假解，分層 dijkstra 可以拿 82 分，完整做法是 DP。對分層 dijkstra 還不是很熟，這是我的盲點。 4. pD 最簡單沒有先寫。 5. pE 思考的時候忘記是無向邊，整場被自己雷死。 6. 糟糕的難度排序。 7. pC 的 3 分沒拿到，是因為我在拿 37 分的時候為了加快 judge 結果，特意加了這行： ```cpp if (n > 10000) return 0; ``` 結果忘記拔掉qwq。 ## 總檢討 ### 賽前 1. 不要熬夜，11 點前就要上床。 2. 可以寫些水題維持手感也穩住心態。 3. 賽前一小時就要睡午覺，睡半小時起來才有時間讓腦袋暖機。 4. 深呼吸告訴自己「我超電」、「我可以的」，但不是「我一定可以拿300分」。 ### 策略修正 1. 開場**讀題 15 分鐘**，讀題時務必連**子題配分**都要讀過一遍。 2. **打模板的時間 5 分鐘**，打的時候不要一直思考有什麼忘記打，浪費腦力，反正之後要用再補就好。 3. 按照**難度排序**題目的技能要再加強。 ![](https://i.imgur.com/H0ZIGyL.png) 4. **時間分配**： - **觀察性質 3 分鐘** - **思考解法 7 分鐘** - **總實作時間 20 分鐘** - **debug 10 分鐘** 拿分間隔控制在 20 分鐘，最多不超過 30 分鐘。 停損點：思考 10 分鐘連 subtask 都沒想法就跳，**卡了 40 分鐘**一定要跳，不要一直想「"應該"還差一點就 AC 了」。 5. **觀察性質**： - 注意變數範圍，誰特別大／特別小，作法 80% 跟它有關。 - 題目「保證」某種性質 $\rightarrow$，作法 99% 跟它有關。 - 常見手法： - 對 OOO 排序 - 數值丟到數線上 - 數對 (a, b) $\rightarrow$ 二維平面 - 區間問題：離線、雙指針、單調性 6. **思考解法**： - 寫下範測，釐清題目。 - 可以構造複雜點的測資幫助思考。 停損點：**10 分鐘**。 7. **實作**： - 想到什麼 subtask 就寫什麼。 - 評估實作細節 2~3 分鐘。 - 分段 check 程式。 停損點：**20 分鐘**。 7. **debug** 時，先用 1 分鐘檢查有沒有智障 bug。 - <span class="lv1">沒開 long long</span> - <span class="lv1">陣列戳出界</span> - <span class="lv1">寫好的函式忘記呼叫</span> - <span class="lv1">0-base／1-base</span> - <span class="lv1">忘記初始化</span> - <span class="lv1">==打成=</span> 構造測資，可以試試邊界測資，不要一直盯著 code。 有可能假解只是自己沒發現。 停損點：**10 分鐘**。 ### 賽中心態調整 1. 把比賽想成是跟出題者決鬥，AC 了代表運氣好決鬥獲勝，WA 了也只代表沒有打贏出題者，滿正常的事，絕對不要認為是因為自己實作爛實力爛，換一題跟他打就好。 2. 不要急著想拿滿分，大部分的 AC 都是一點一點分數累積上去的，就算想到滿分解也是一樣。 3. 丟一筆 submission 就去廁所，過半場吃點心。 4. 換題的時候，一切重新 reset，剛剛發生了什麼事都不重要，不要掛在心上。 5. 你炸掉大家也都會炸掉。 ## 實用文章 1. [IOI 前國手 張程凱 - IOI 準備心得](https://hackmd.io/Cd5AugwvQlmhrH-97O1PVw) 2. [IOI 前國手 曹宸睿 - TOI 入營考訓練](https://slides.com/emanlaicepsa/toi/?fbclid=IwAR1XBQiTBGzPdiCh8SiAdMepXzlqBNE7Na9P0kULFkqE05wUovc7PwvCFuc) 3. [TOI 一階電神 林柏瑄 - 2021 TOI 心得文](https://www.facebook.com/permalink.php?story_fbid=873924860066850&id=100023480331778) 4. 電神們的建議 ![](https://i.imgur.com/VgGbghy.png) ![](https://i.imgur.com/m4C837I.png) ![](https://i.imgur.com/YXKRJhS.png)