全國賽心得

全國模擬賽 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 (N l o g M l o g M)

[2:20] pD AC

F 依舊沒啥想法，先去開 I
沒想到甚麼好的 DP 方式，但感覺可以湊出來
題目要的是

a_{1} + a_{2} + . . . + a_{n} + 2 a_{1} a_{2} + 2 a_{1} a_{3} + . . . + 3 a_{1} a_{2} a_{3} + 3 a_{1} a_{2} a_{4} . . . + n a_{1} a_{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 (N l o g N)

做到

[3:07] pI AC

認真想了 F 發現以

A

為根詢問的點一定是葉子，每次詢問完都會確定答案是不是在這子樹，如果要確定在哪個子樹，最差要用子樹數量 -1 次，所以要花費最多次的子樹必定最先詢問，這個我好像某次 CF 看錯題目有想到差不多的東西。
然後就可以推出 DP 式
假設

s o n_{1}, s o n_{2} . . .

是以

d p [s o n_{1}] >= d p [s o n_{2}] >= . . .

排序過的

d p [u] = m a x (d p [s o n_{1}] + 0, d p [s o n_{2}] + 1, d p [s o n_{3}] + 2. . .)

複雜度

O (N l o g N)

[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} = 1 e 6, 2 e 6, 3 e 6

A_{i}, B_{i}, C_{i} <= 6 e 6

應該是枚舉

w_{i} + w_{j}

總共只有

6

種可能
把整個陣列用

w_{i}

分成三個
枚舉的時候對

A

做雙指標，

B, C

離散化後用線段樹查
複雜度

O (6 N l o g N)

但過程卡了一些 bug，還發現要特判

w_{i} = w_{j}

不然可能會戳到

i = j

我把線段樹加上回溯就可以了

[1:55] pF AC

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

看完馬上破梗，題目根本在唬人
直接調和級數

O (N l o g N)

砸過去，過程被卡了一兩次常數
把 mod 改成用減的
拔掉 define int long long
加上 pragma

[2:21] pI AC

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

O (N M)

DP 寫掉

[2:43] pB 31(???)

正常

O (N M)

是 36 分，但我看錯範圍陣列開太小，還沒發現我沒拿到 5 分的

O (N M)

子題就跳題了
慘… 直接少 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。

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