## 0x01 2020 花中一模 題解 --- ### 大綱 - pA - 簽到題 (Registration) - pB - 決鬥 (Duel) - pD - 大排長龍 (Lineup) - pC - 蜂窩迷圖 (Hexagon) - pE - 道路建設 (Road) - pF - 燒雞 (Chicken) --- ## pA - 簽到題 (Registration) ---- - 給 $N$ $\small(1 \le N \le 2000)$ 個數字 $a_i$ $\small(0 \le a_i \le 10^6)$ - 可以把原序列切成 **任意段** - 求每一段的中位數之和的 **最大值** - 有 $T$ $\small(T = 100)$ 筆測資 ---- ### Subtask - $[20]$ $N = 1$ - $[50]$ $N \le 100$ - $[30]$ $N \le 2000$ ---- ### Subtask 1 ($N = 1$) - 數列長度只有 $1$，所以也只有一種切法 - 直接輸出 $a_1$ 就可以了 ---- $\color{red}{WA}$ $(20/100)$ ---- ### 小性質 - 經由 Subtask 1 可以發現，一個數字的中位數就是他自己 - 所有數字都 $\ge 0$？ - 直接輸出所有數字的和！ ---- $\color{red}{WA}$ $(70/100)$ ---- - 好像忘了什麼？ - 還要對 $10^9 + 7$ 取餘數 ---- $\color{lime}{AC}$ $(100/100)$ --- ## pB - 決鬥 (Duel) ---- - $2N$ $\small(2 \le N \le 3 \times 10^5)$ 個人分成黑白兩隊 - 黑隊每個人有一個數字 $a_i$ $\small(1 \le a_i \le N)$ - 白隊每個人有一個數字 $b_i$ $\small(1 \le b_i \le N)$ - $\forall 1 \le i \le N$ 比較 $[\min(a_i, b_i), \max(a_i, b_i)]$ 區間裡面哪一隊數字大的比較多 ---- ### Subtask - $[23]$ $N \le 2000$ - $[20]$ $1 \le a_i, b_i \le \min(N, 2000)$ - $[16]$ $a_i = 1$ - $[41]$ $N \le 3 \times 10^5$ ---- ### Subtask 1 ($N \le 2000$) - 咦？好像可以暴力？ - 寫寫看吧，反正又不虧 ---- $\color{cyan}{TLE}$ $(23/100)$ 或 $(43/100)$ ---- ### Subtask 2 ($a_i, b_i \le 2000$) - 每次詢問的範圍跟上面那筆一樣ㄟ - 總共的詢問大約有 $\frac{2000^2}{2} = 2 \times 10^6$ 種，不如先把他存起來吧 ---- - 枚舉左界 $1 \le L \le \min(N, 2000)$ - $\forall L \le R \le \min(N, 2000)$ 求出區間 $[L, R]$ 的答案 ---- $\color{red}{WA}$ $(43/100)$ ---- ### Subtask 3 ($a_i = 1$) - 好像跟上面那筆差不多呢 - 總共的區間只有 $3 \times 10^5$ 種，也可以先算出來 ---- - $\forall 1 \le i \le N$ 處理出編號 $1 \sim i$ 的答案 ---- $\color{red}{WA}$ $(16/100)$ - 加上前面的就有 $(59/100)$ ---- ### 性質一 - 每次對戰的結果都是固定的 - 很好證明ㄅ - $a_i$ 跟 $b_i$ 都不會改變 ---- - 既然是固定的那是不是可以預處理呢？ - 但是狀態數高達 $4.5 \times 10^{10}$ 種？ ---- ### 性質二 - 區間 $[L, R]$ 對戰的結果等於 $[1, R]$ 的結果扣掉 $[1, L-1]$ 的結果 - 假設前 $10$ 分鐘我得了 $7$ 分，且前 $4$ 分鐘我得了 $3$ 分，請問第 $5 \sim 10$ 分鐘我總共拿到幾分？ ---- - 只要處理出所有 $[1, i]$ 的情況就可以了！ - 黑隊勝場數 - 白隊勝場數 - 詢問 $[L, R]$ 的時候就用 $[1, R] - [1, L-1]$ 的結果來判斷 ---- - 時間複雜度 $O(N)$！ ---- $\color{lime}{AC}$ $(100/100)$ ---- - 這種技巧叫做前綴和，是競賽中常出現的咚咚ㄛ --- ## pD - 大排長龍 (Lineup) ---- - 你需要模擬一個 queue - 有 $Q$ $\small(1 \le Q \le 5 \times 10^5)$ 次操作 - 把所有值加上 $k$ $\small(1 \le k \le 10^6)$ - 把前面的 $x$ $\small(1 \le x \le 10^6)$ 個數字 pop 掉 - 在最後面加入 $y$ $\small(1 \le y \le 10^6)$ 個 $0$ - 每次操作完都要求出 queue 裡面的最大值 ---- ### Subtask - $[9]$ $Q \le 1000$，$x = y = 1$ - $[8]$ 沒有 pop 的動作 - $[35]$ $y = 1$ - $[19]$ $Q \le 1000$，$\sum{y} < 2^{31}$ - $[29]$ $Q \le 5 \times 10^5$ ---- ### Subtask 1 ($Q \le 1000$，$x = y = 1$) - 直接暴力 >< ---- $\color{cyan}{TLE} / \color{orange}{RE}$ $(9/100)$ ---- ### Subtask 2 (沒有 pop 的動作) - 最大值會是誰？ ---- - 第一個人一定有最多片口罩 - 他最一開始就在那裡，而且每次發口罩都會給到他 - 把所有 $k$ 加起來就好 ---- $\color{red}{WA}$ $(8/100)$ - 加上前面的是 $(17/100)$ ---- ### 小性質 - queue 裡面的數字一定非嚴格遞減 - 後面的人比較晚來怎麼可能會拿到更多東西？ ---- - 每次求最大值可以輸出 queue.front() 就好！ ---- ### Subtask 3 ($y = 1$) - 人數不會超過 $5 \times 10^5$ - 每個人最多只會進一次 queue 也只會離開一次 queue - 操作 $2$、$3$ 可以暴力 - 詢問目前也可以做到 $O(1)$ - 不過第一種操作要怎麼辦？不能用迴圈直接跑吧 ---- - 運用剛才提到的前綴和想法 - 如果只把答案紀錄在第一個人跟最後一個人身上 - 要把第一個人 pop 掉的時候再把答案傳下去？ ---- - `front` 表示最前面的人的編號，`back` 表示最後面的人的編號 - `ans[i]` 表示第 $i$ 個人的答案 - 每次對所有人發口罩就 `ans[front] += k, ans[back+1] -= k` - 當操作二中，第 $i$ 個人要被丟掉的時候就 `ans[i+1] += ans[i]` ---- $\color{orange}{RE}$ $(44/100)$ - 合起來是 $(52/100)$ ---- - 感覺已經很接近正解了？ - 是的，沒錯 - 感覺如果總共的人數不會超過 $10^6$ 就可以做掉了？ - 是的，沒錯 ---- - 教個小技巧：離散化 - 如果數字很大，但是其實重要的只有數字間的相對關係那就可以使用 - 例如說：$[77, 10, -9, 6, 10]$ 就可能被離散化成 $[4, 3, 1, 2, 3]$ - 實作上可以先把所有數字存到陣列裡 - 對陣列進行排序，把一樣的數字去掉 - 再對每個數字二分搜他是第幾大的 ---- - 要怎麼應用到這題ㄋ ---- - 先重新定義： - `front` 表示最前面的人的編號，`back` 表示最後面的人的編號 $+1$ - 注意這個 $+1$，剛剛操作中真正用到的不是 `back` 而是 `back+1` - 先把所有數字存下來 - 紀錄每次操作完的 front 跟 back - 離散化~~~ ---- - 咦？這樣就做完了？ - 是的，沒錯 ---- $\color{lime}{AC}$ $(100/100)$ --- ## pC - 蜂窩迷圖 (Hexagon) - 抱歉這題官解假解了，不過已經修好了 ---- - 給你一棵 $N$ $\small(2 \le N \le 10^5)$ 個點的樹 - 小 Y 跟小 P 分別在點 $1$ 跟點 $N$ - 輪流往相鄰的地方移動，但是不能移動到有人走過的點 - 不能走的就輸了 - 問你誰會贏 ---- ### Subtask - $[27]$ $N \le 300$ - $[9]$ $u_i = i$，$v_i = i+1$ - $[16]$ 點 $1$ 跟點 $N$ 相鄰 - $[48]$ $N \le 10^5$ ---- ### Subtask 2 ($u_i = i$，$v_i = i+1$) ---- - 圖大概長那樣  ---- - 每個人的走法都是固定的 - 判奇偶性就好 >< - $N \equiv 1 \pmod{2}$ 就是 $\texttt{Little Y}$ - $N \equiv 0 \pmod{2}$ 就是 $\texttt{Little P}$ ---- $\color{red}{WA}$ $(9/100)$ ---- ### Subtask 3 (點 $1$ 跟點 $N$ 相鄰) - 小 Y 跟小 P 的移動不會對對方造成策略上的改變 - 只要計算出小 Y 跟小 P 最多能走多少步再比較即可 - 從點 $1$ 跟點 $N$ 各 dfs 一次 ---- $\color{red}{WA}$ $(16/100)$ - 這樣就有 $(25/100)$ 了 ---- ### 小性質 - 注意到只有 $1 \sim N$ 的那條路徑上才是有意義的 - 如果其中一個人離開那條路徑那答案就確定了 ---- ### 官解 - dp - 把樹壓成序列，$d_i$ 表示「從 $1 \sim N$ 路徑上的第 $i$ 個點離開最多可以再走幾步」 - 最多可以再走幾步 $\Leftrightarrow$ 子樹深度 - 依序去看小 Y 在路徑上走 $i$ 步之後離開會不會獲勝、小 P 在路徑上走 $i$ 步之後離開會不會獲勝 - 可以就直接輸出解答 ---- $\color{lime}{AC}$ $(100/100)$ --- ## pE - 道路建設 (Road) ---- - 給定 $N$ $\small(1 \le N \le 10^5)$ 個點的權重 $a_i$ $\small(0 \le a_i \le 10^7)$ - 在兩個城市 $i$, $j$ 之間建邊的花費是 $a_i + a_j$ - 將其中 $M$ $\small(0 \le M \le 10^5)$ 條邊 $(u_i, v_i)$ 的價格改成 $w_i$ - 求最小生成樹權重 ---- ### Subtask - $[19]$ $N, M \le 1000$ - $[6]$ $M = 0$ - $[13]$ $w_i \le a_{u_i} + a_{v_i}$ - $[41]$ $a_1 \le a_2 \le \dots \le a_N$ - $[21]$ $N, M \le 10^5$ ---- ### Subtask 1 ($N, M \le 1000$) - 暴力啦，暴力 - $O(N^2)$ 建邊做 MST ---- $\color{cyan}{TLE}$ $(19/100)$ ---- ### Subtask 2 ($M = 0$) - 沒有特殊權重的邊 - 所有點都要被連到一次 - 都連到權重最小的就好啦 o(*￣▽￣*)ブ ---- - 把點權 sort 之後輸出 $(a_1 + a_2) + (a_1 + a_3) + \dots + (a_1 + a_N)$ - $= a_1 \times (N-2) + (a_1 + a_2 + a_3 + \dots + a_N)$ ---- $\color{red}{WA}$ $(6/100)$ - $(25/100)$ GET！ ---- ### Subtask 3 ($w_i \le a_{u_i} + a_{v_i}$) - 顯然答案只會比 $M = 0$ 的情況更好 - 把點權最小的點到其他所有點，以及額外的 $M$ 個限制都一起做 MST ---- $\color{red}{WA}$ $(19/100)$ - 你會拿到 Subtask 2 跟 3 - $(38/100)$ GET！！！ ---- ### 官解 - priority queue + dsu - 假設輸入已經按照點權排序 $(a_1 \le a_2 \le \dots \le a_N)$ - 把剛剛會用到的邊都丟進去 priority queue 裡面 - 用並查集判斷兩個點能不能連邊 ---- <!-- This part of editorial is too vauge, I need to fix it. --> - 不過如果 $w_i > a_{u_i} + a_{v_i}$ 可能會被丟到很後面，讓邊權比較小的 $a_{u_i+1} + a_{v_i}$ 跟 $a_{u_i} + a_{v_i+1}$ 進不來 - 對每個限制 $(u_i, v_i, w_i)$，如果 $w_i > a_{u_i} + a_{v_i}$ 就把 $(u_i + 1, v_i)$ 跟 $(u_i, v_i + 1)$ 也丟進來 ---- $\color{red}{WA}$ $(47/100)$ - 你會拿到 Subtask 2 跟 4 - 加起來就是 $(79/100)$ ㄌ >< ---- - 如果把點權直接排序後面的 $M$ 個限制會爆掉 - 存一個 map 來表示本來的第 $i$ 個數字在 sort 之後被丟到哪裡ㄌ ---- $\color{lime}{AC}$ $(100/100)$ --- ## pF - 燒雞 (Chicken) ---- - 給你一棵 $N$ $\small(1 \le N \le 3 \times 10^5)$ 個點的樹，每個點都有點權 $a_i$ $\small(1 \le a_i \le 2)$ - 請找出最小的正整數 $K$ 使圖中不存在一條 **簡單路徑** 的權值和為 $K$。 ---- ### Subtask - $[11]$ $N \le 2000$ - $[29]$ $u_i = i$，$v_i = i+1$ - $[7]$ $a_1 = 1$，$a_2 = a_3 = \dots = a_N = 2$ - $[53]$ $N \le 3 \times 10^5$ ---- ### Subtask 1 ($N \le 2000$) - 可以暴力 $O(N^2)$ dfs 拿到所有點對的距離 - 答案的值最高就是 $2N$ - $\forall 1 \le i \le 2N$，檢查有沒有點對的距離是 $i$。 ---- $\color{cyan}{TLE} / \color{orange}{RE}$ $(11/100)$ ---- ### Subtask 3 ($a_1 = 1$，$a_2 = a_3 = \dots = a_N = 2$) - 把路徑權值分為 **奇數** 跟 **偶數** 來看 - **最長** 偶數權值的路徑就是以 $1$ 為根，$(所有子樹的直徑最大值) \times 2$ - **最長** 奇數權值的路徑就是某條經過點 $1$ 的鍊 - 如果點 $1$ 只有一個孩子，答案就是 $(樹的深度) \times 2 + 1$ - 不然，答案就是 $(第一深的子樹深度 + 第二深的子樹深度) \times 2 + 1$ ---- $\color{red}{WA}$ $(7/100)$ ---- ### 小性質 - 注意到一條權值和 $w > 2$ 的路徑只會有四種形式： - $1 - \dots - 1$ - $1 - \dots - 2$ - $2 - \dots - 1$ - $2 - \dots - 2$ ---- - 每一種形式都可以經由拆掉一個或兩個端點來構造出權值和 $w-2$ 的路徑 - 只要找出 **權值最大** 的奇數跟偶數路徑就可以了 ---- ### 官解 - 樹 dp - 對每個點維護他往下可以到的最大奇數權值跟最大偶數權值 - 對每個點都更新一次答案 - 做完了 (?) ---- $\color{lime}{AC}$ $(100/100)$ --- ## 題本、測資跟官解都在[這裡](https://drive.google.com/drive/folders/1YEZJ7uf3UKq_DD3aMm7sxn0AGHwhp529?usp=sharing) ### 然後[這邊](https://codeforces.com/group/GG44hyrVLY/contests)有 judge 可以上傳程式碼供賽後補題