# 全國賽心得

## 全國模擬賽 RK3

一來看到 A 蠻水的，是堆疊木條看能延伸到多長，直接猜重的放下面，開始模擬
#### [0:13] pA AC

AC 後我就把全部題目看完

B 把一堆陣列接起來找最大連續和， dp 或枚舉應該可做
C 以為直接輸出一模一樣陣列，發現不對猜是怪怪 greedy，連部分分都不會，覺得不可做
D 構造一組邊權並有給邊之間的大小關係使 $a$ 到 $b$ 之間的路徑長最短為 $d$，猜是某種最短路或 dsu+構造
E 只會暴力 好難
F 好像每次詢問完都會切成一棵棵子樹，感覺可做
G 進位制問題，只會暴力
H 這三小，幾何+互動題一堆函式呼叫畫圖，直接當不可做
I 算所有子集乘積乘子集大小的總和，感覺是神奇的數學或 dp

B 枚舉尾找頭用 multiset 維護，過程忘記先找單純一個陣列的最大連續和吃兩次 WA
#### [0:43] pB AC

感覺 D 有機會做出來，先把邊權設成 $1$ 到 $m$ 發現可以只留一條路徑，其他有更大的邊可以直接設成 INF，不夠可以把路徑中最大的加到夠，然後就開始了漫長的 WA 旅程，WA 了好幾次發現 dsu 是爛的，就直接用 dijkstra 維護路徑總和最小及路徑上最大值最小，只拿到部分分
#### [2:10] pD 52.5
找不太到 WA 在哪裡，開始 assert，發現是最後最短路路徑總和不是 $d$，發現漏一個 case，把 dijkstra 改成二分搜+dijkstra，複雜度 $O(NlogMlogM)$
#### [2:20] pD AC

F 依舊沒啥想法，先去開 I
沒想到甚麼好的 DP 方式，但感覺可以湊出來
題目要的是
$a_1+a_2+...+a_n+2a_1a_2+2a_1a_3+...+3a_1a_2a_3+3a_1a_2a_4...+na_1a_2...a_{n-1}a_n$
猜這東西可能跟這兩個東西有關
$(a_1+a_2+...+a_n)$
$(a_1+1)(a_2+1)(a_3+1)...(a_n+1)$
湊了一陣子發現答案就是
$a_1(a_2+1)(a_3+1)...(a_n+1)+$
$a_2(a_1+1)(a_3+1)...(a_n+1)+$
$a_3(a_1+1)(a_2+1)(a_4+1)...(a_n+1)+$
$...$
$a_n(a_1+1)(a_2+1)...(a_{n-1}+1)$
然後預處理 $(a_1+1)(a_2+1)(a_3+1)...(a_n+1)$
加模逆元就可以 $O(NlogN)$ 做到
#### [3:07] pI AC

認真想了 F 發現以 $A$ 為根詢問的點一定是葉子，每次詢問完都會確定答案是不是在這子樹，如果要確定在哪個子樹，最差要用子樹數量 -1 次，所以要花費最多次的子樹必定最先詢問，這個我好像某次 CF 看錯題目有想到差不多的東西。
然後就可以推出 DP 式
假設 $son_1,son_2...$ 是以 $dp[son_1]>=dp[son_2]>=...$ 排序過的
$dp[u]=max({dp[son_1]+0,dp[son_2]+1,dp[son_3]+2...})$
複雜度 $O(NlogN)$
#### [3:25] pF AC

剩下題目完全沒想法，把暴力分拿一拿
#### [4:06] pE 7
#### [4:32] pG 9

就結束了
賽後發現原來大家都在燒雞，我反而算寫的很順的，運氣很好的拿到第三名附加一張酷酷的獎狀

## 正式全國賽 RK8
### 新竹好冷...
寒流來加新竹的風...超級冷....
### 比賽過程

比賽一開始先把全部題目看完
我自己排出來是 $C<E<D<F<I<G<B<<H<<A$

C 簡單的區間 DP 複雜度 $O(N^2)$
#### [0:23] pC AC

D 感覺是水題但還是沒想法，先去寫 E

一堆齒輪接在一起的問題，範圍都很小
我不知道我在幹嘛，一直沒想清楚甚麼時候要算 $i$ 甚麼時候要算 $i+1$
WA 了兩次 還浪費很多時間

#### [1:03] pE AC

還是沒有 D 的想法 zzz...
繼續往下開 F

求幾種 $W$ 滿足得
$w_i+w_j=W$
$w_i+w_j \leq A_i+A_j$
$w_i+w_j \leq B_i+B_j$
$w_i+w_j \leq C_i+C_j$
$w_i = 1e6,2e6,3e6$
$A_i,B_i,C_i<=6e6$
應該是枚舉 $w_i+w_j$ 總共只有 $6$ 種可能
把整個陣列用 $w_i$ 分成三個
枚舉的時候對 $A$ 做雙指標，$B,C$ 離散化後用線段樹查
複雜度 $O(6 NlogN)$
但過程卡了一些 bug，還發現要特判 $w_i=w_j$ 不然可能會戳到 $i=j$
我把線段樹加上回溯就可以了

#### [1:55] pF AC

繼續想了一下 D，還還還是沒有 D 的想法 qqq
繼續往後開去看 I

看完馬上破梗，題目根本在唬人
直接調和級數 $O(NlogN)$ 砸過去，過程被卡了一兩次常數
把 mod 改成用減的
拔掉 define int long long
加上 pragma

#### [2:21] pI AC

打算先回來把 D 寫掉，但一直沒有想法...
B 感覺是神奇的 DP 優化像 slope trick 或轉移點單調之類的
過程先把 B 顯然的 $O(NM)$ DP 寫掉

#### [2:43] pB 31(????)
正常 $O(NM)$ 是 36 分，但我看錯範圍陣列開太小，還沒發現我沒拿到 5 分的 $O(NM)$ 子題就跳題了
慘... 直接少 5 分

然後就跟 D 幹下去
過程唬爛了一兩次也失敗了

花了很久很久終於發現 $x$ 與 $+$ 之間的 $|$ 都會轉成同一種
然後又發現修改的 $+$ 只會在一組 $x$ 之間沒有 $+$ 的
這麼簡單的東西我居然過了 4 個多小時才發現...到底在幹嘛...

#### [4:26] pD AC

然後那時候我有點緊張，被一些簡單題卡太久
想拿點 G,H 的分數一直看錯題目，結果甚麼都沒拿到到結束了
我把 G 的題目看錯沒看到他給的 deg 是每個編號的...
我以為是無序的，害我一直弄不出來
賽後發現 G 其實不難，慘...

最後結果在 RK8
就算過了 G 也還是在二等，也不會改變甚麼，只是覺得很可惜
只少不用比初選了 好讚

### 趣事
第一天到新竹高鐵站 Littlecube 穿短袖短褲出去吹風，然後剛好沒風。
晚宴跟去年一樣好吃有油飯，但今年就沒給燒雞了
感覺整桌就我一直在吃，前面幾道菜都是我先動的，有些人都在害羞不太敢夾(?
Foxdd 在晚宴的後半段一直四處 poke,merge 人 超得

住宿也跟去年一模一樣，只是我這的地方從 11 樓變 12 樓而已

晚上很多人聚集在 Littlecube 和 Koying 的房間耍廢，交大學長 HNO2, shaun, Gino 也有來，結果房間主人 Littlecube 一直在寫題、Koying 在處理 NHDK 的模擬賽事情。
shaun 還說去年 balbit 就是大家都在玩他在寫題結果就一等一了，然後今年 Littlecube 也拿到一等一 orz。

我的賽前預測拿一等獎的名單全中