## 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$)
----
- 圖大概長那樣
![](https://i.imgur.com/flbT3F5.png)
----
- 每個人的走法都是固定的
- 判奇偶性就好 ><
- $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 可以上傳程式碼供賽後補題
{"metaMigratedAt":"2023-06-15T13:38:39.462Z","metaMigratedFrom":"YAML","title":"0x01 2020 花中一模 題解","breaks":true,"description":"pA - 簽到題 (Registration)","contributors":"[{\"id\":\"e573a1ba-d69b-44a7-a0d5-9d817fb786cc\",\"add\":8259,\"del\":393}]"}