2022 北市賽心得

昨天在師大比北市賽，這裡是計分板。

這次跟去年一樣是用筆電打比賽，用得有點不習慣，去年北市賽好像是佳作，所以今年我想著不要燒雞就好。

開場我先把六題題目看過一遍，題目如下：

$\text{pA}$：有 $n \leq 300$ 個人，可以把每個人塗成黑色或白色，每個人被塗成黑色的快樂值是 $a_i$，被塗成黑色的快樂值是 $b_i$，另外有 $m$ 筆關係，給你 $c_i, d_i, w_i$，如果編號 $c_i$ 跟 $d_i$ 的人同顏色，那會有 $w_i$ 的額外快樂值，問你最大可以得到的快樂值。

$\text{pB}$：有 $n\leq 5\times 10^5$ 個數字，每次可以選相鄰兩個，將小的刪掉，並將總和加上大的值，問你剩下一個數字時總和最小可以是多少。

$\text{pC}$：有 $n\leq 200$ 個技能，給你每個技能的名字、學習此技能需要的經驗值與學習完會增加的攻擊力，另外會有 $m$ 個關係，給你技能 $a$ 跟技能 $b$，代表你在學習技能 $b$ 之前需要先學習技能 $a$。你有 $e\leq 2000$ 個經驗值，問你最後攻擊力最多可以增加多少。

$\text{pD}$：給你兩個字串 $s, t$，每次要找到 $t$ 裡最左邊的 $s$ 並刪掉，直到沒有 $s$ 為止，問你最後的字串。($|s|\leq 1000, |t| \leq 6\times 10^5$)

$\text{pE}$：有 $n$ 個人，每個人一開始的 $a_i$ 是 $0$，共有 $m$ 天，每天會選 $k$ 個人，讓他們的 $a_i$ 增加 $1$，並且每天都會有排名，假設五個人的 $a_i$ 分別為 $8, 7, 7, 6, 3$，那排名就會是 $1, 2, 2, 4, 5$，請你最後分別輸出 $n$ 個人在這 $m$ 天裡的平均排名。($n, m\leq 3\times 10^5$)

$\text{pF}$：有一個容量為 $B$ 的穀倉 ($B$ 可能為無限)，一開始有 $b$ 單位的飼料，有 $n\leq 10^5$ 天，每天飼料價格為 $a_i$，需要餵 $b_i$ 單位的飼料，需要滿足餵完飼料後剩下飼料的量不超過 $B$，問你最少要花的錢。

一開始我覺得可以很快寫出來的是 $\text{pB}$，我的作法是每次選最小的數字，然後看他左邊比較小還是右邊比較小，一個一個刪掉就好了，$\text{pB }100/100$。再來我去寫 $\text{pC}$，這很明顯是樹背包，我寫了一個合併兩個 $\text{vector}$ 的函式，然後就可以按拓樸順序去做他，每棵樹的祖先記得要連一條邊到 $0$ 號節點。我原本以為將迴圈上界設成他目前最大能達到的複雜度可以到 $O(ne)$，但其實好像是 $O(ne^2)$，反正就過了，$\text{pC }100/100$。我接著看 $\text{pD}$，我的想法是用 $\text{hash}$ 比對字串，如果比對到了，就把那個字串刪掉，然後往左移 $n$ 位繼續比對，我是用 $\text{link list + deque}$ 實作，寫了 $100$ 多行結果很神奇的沒有出錯，賽後我才發現用 $\text{kmp}$ 就可以很快找到，而且刪除還更簡單，$\text{pD }100/100$。再來我去寫 $\text{pF}$ 的部分分，如果 $B$ 是無限的，那我每次不夠的量用之前最小的價格買就好了 $\text{pF }44/100$。然後我去寫 $\text{pA}$ 的部分分，$m = 0$ 直接取 $\max(a_i, b_i)$，$n$ 很小時可以位元枚舉，然後我有想到可以把問題轉成最小割，只是我懶得刻 $\text{Flow}$ 而且我不知道怎麼建模，$\text{pA }55/100$。接著我去寫 $\text{pE}$ 的部分分，$n, m$ 很小時我直接用一個 $\text{BIT}$ 維護，很大時我就想不到了。最後我想到 $\text{pF}$ 了，假設在前 $i$ 天買的量為 $\text{buy}_i$，餵的量為 $\text{feed}_i$，假設想在第 $d\leq i$ 天買 $k$ 單位的飼料，那要滿足 $b + \text{buy}_i - \text{feed}_i + k\leq B$，移項就會變成 $k\leq B - b + \text{feed}_i - \text{buy}_i$，我用一個 $\text{pq}$ 存最小價錢與他是哪一天，計算出他能買的最大值，這可以用線段樹維護，之後 $\text{buy}$ 會增加，可以想像成是在線段樹上加值，如果扣掉之後變成 $0$ 了，那就可以從 $\text{pq pop}$ 掉了 $\text{pF }100/100$。

最後我拿到 $486/600$ 分，與其他兩人同分，然後是一等二，我覺得這個結果是在我預料之外的，我原本想說如果能進全國賽就很開心了，其實讓我最開心的是明年不用打校隊初選跟複選了，而且還可以在 $\text{TIOJ}$ 出題 $\text{hehe}$。

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！