去年全國賽燒雞後已經過了一年了，總算又到了這個時候。去年我賽前賽中都超級緊張的，不過可能是因為已經比過比全國賽還恐怖的比賽 (?)，所以這次不怎麼緊張。

不知道為什麼這次全國賽是星期五和星期六，所以星期五可以不用去學校 (X)，今年晚上住在台大尊賢館，住超好但台北人不能住 QQ，不過晚上可以吃那裡的晚餐，吃得超飽，然後跑去別人的房間裡玩遊戲，那間房間裡大概擠了 20 多個人吧 XD。

計分板

題目

前情提要：我在測機的時候發現一秒大約可以跑 $2 \times 10^9$ 次加法。

pA 礦砂採集

100/100

有 $n$ 種礦物，第 $i$ 種有 $w_i$ 公斤，每一公斤的價值是 $v_i$ 元，還有一個可以放 $m$ 公斤的東西的背包，每一種礦都可以取任意重量，求放進背包裡的東西價值最大可以是多少。

題敘故意寫得很像多重背包，我就在想這也太難了吧，第一題就是多重背包，而且 $nm$ 是 $10^8$，如果用二進位分解應該會 TLE，難不成要單調隊列嗎？

仔細看了一下發現只是分數背包而已，Greedy 就會過了。

pB 村莊與小徑

100/100

給一張邊有權重（可能負）的 DAG，求節點 1 到每個點的最短路徑和。

看完題目想說可以用 Dijkstra 或拓樸排序，然後覺得拓樸比較好寫所以就用拓樸了，後來才想起來有負邊不能用 Dijksta。

pC 樣本解析

100/100

給一些只含有小寫英文字母的集合 $S_1,S_2,...,S_n$ 和 $X$，求

1. 有多少個 $i$ 滿足 $S_i \cap X = \emptyset$。
2. 有多少個 $i$ 滿足 $S_i \subset X$。
3. 有多少個 $i$ 滿足 $X \subset S_i$。
4. 有多少個 $i$ 滿足 $S_i$ 和 $X$ 部分相交。
5. 有多少種將 $X$ 分成 $X_1$ 和 $X_2$ 的方式，滿足 $X_1,X_2,S_1,S_2,...,S_n$ 兩兩不部分相交。

保證 $S_1,S_2,...,S_n$ 互不部分相交且互不相等，且 $X$ 至少與一個 $S_i$ 部分相交，且不與任何一個 $S_i$ 相等。 $n \leq 18$

前面四個都是簡單的實作，看到 $n \leq 18$ 我也沒想太多，就直接 $O(n 2^n)$ 暴力做第 5 個了。

找到隨便一個和 $X$ 部分相交的 $S_i$，那 $X$ 的拆法就只能是拆成 $X - S_i$ 和 $X \cap S_i$，這樣就只需要 $O(n)$ 檢查就好了。

pD 水果包裝

100/100

有 $n$ 個水果，第 $i$ 個的重量是 $w_i$，然後機器會按照 $p_1,p_2,...,p_n$ 的順序將水果裝袋。有 $m$ 個袋子，機器在裝某個水果時，會把它放到總重最小的那個袋子裡，如果有等重的會放到編號最小的那個裡面。 已知全部裝完後，第 $i$ 個袋子裡的水果有哪些，求 $p_1,p_2,...,p_n$，或者說無解。

可以模擬一次過程，先找現在哪個袋子重量最小，然後就會知道要拿那個袋子裡的其中一個水果放進去，不過放進袋子裡的順序是隨意的，所以要找哪個水果要先放進去。因為要避免無解，就是要避免有袋子在裝完之前，就有出現其他已經裝完的袋子總重更小，所以把重量小的水果先放進去總是好的。

pE 共同朋友

100/100

給一張 $n$ 個點的圖，求有多少對點有共鄰點。 $n \leq 2500$，圖可以是完全圖。

本來想說應該是把度數 $\leq \sqrt{n}$ 的點跟大於的分開處理，寫完後才想到可能是完全圖所以根本不能這樣分。

後來想說一秒可以跑 $2 \times 10^9$ 次加法，如果我用 bitset 來判有沒有共鄰點，大概需要做 $2500 \times 2500 \times 2500 / 64 = 244140625$ 次，而且這題給兩秒，應該可以過，丟上去就過了。

pF 歡樂外送點

100/100

平面上所有格子點都是一個城市，然後有 $n$ 個城市是外送點，第 $i$ 個外送點會提供 $w_i$ 的繁榮度，所有跟他曼哈頓距離 $\leq r_i$ 的點的繁榮度都會增加 $w_i$，求最繁榮的城市繁榮度是多少。

曼哈頓距離 $\leq r_i$ 的範圍就是一個轉了 45 度的正方形，所以可以把點旋轉 45 度，然後就會變成求最大矩形覆蓋。經過一些畫圖 (?) 之後發現可以把座標轉成 $(x - y, x + y)$，這樣就會轉 45 度了，再來就用掃描線 + 線段樹算最大矩形覆蓋。

然後有一個特殊 case 是因為轉完座標之後，會有本來不是格子點的點變成格子點，這樣就會誤判，不過測資裡沒有這狀況也沒人（吧）在賽中想到 (?)。其實只要多開一棵線段樹，奇偶數分開處理就好了。

pG 矩陣相乘

0/100

給兩個 $n \times n$ 矩陣 $A$、$B$，已知 $A \times B$ 是一個最多只有 $2n$ 個非零元素的矩陣，求所有非零元素的位置和值。 $n \leq 2800$，時限 6.5 秒。

完全不會做 QQ。

pH 跑跑遊戲場

38/100

給一個數字 $T$，還有一隻只能往右和往下走的老鼠，構造一個迷宮，可以在格子與格子之間放障礙物，使得老鼠從左上角走到右下角的方法數恰為 $T$。 $T \leq 10^{18}$，如果迷宮大小是 $n \times m$，會得到 $\max(100, 100-2((n+m)-90))$ 分。

我的構造方法長這樣：

這樣就可以弄出走到那裡的方法數是 1、2、4、8、16、……的格子，然後把 $T$ 二進位分解，如果有那個位數就把綠色的地方打開，沒有就擋掉，這樣走到右下角的方法數就會是打開的地方加起來。這樣 $n$ 會是 $\log_2(T) + 1$，$m$ 是 $\log_2(T) + 2$，$n+m$ 最多是 121，會拿到 38 分。

pI 黑白機

9/100

有兩台機器：黑機和白機，還有 $n$ 件事，第 $i$ 件事在白機上做要花 $w_i$ 秒、黑機做要花 $b_i$ 秒，在一台機器上做完一件事後，那台機器上會有那件事的資料，把第 $i$ 件事的資料傳到另一台機器要 $t_i$ 秒。 要做第 $i$ 件事，必須滿足那台機器上有第 $1$ 到 $i-1$ 件事的資料，且每件事都只能做一次，求最快什麼時候能做完所有事。

9 分是 $O(n2^n)$ 的暴力，滿分解好像是 2D/1D DP 優化，但我只會 1D/1D 而且還列不出好的轉移式 QQ。

過程

開場一樣先打完 .vimrc 後讀題目，讀到 pH 覺得題本怎麼還那麼厚，才發現這次有 9 題（以前都只有 8 題）。看完之後認為 pA~pE 是水題，pF 應該是某種資料結構，pG~pI 則是沒什麼想法。

一個多小時的時候寫完了前四題，然後覺得 pE 沒有我想得那麼簡單（其實有），所以先去寫 pF，本來我用動態開點線段樹，然後一直 RE/MLE（CMS 分不出來），多試幾次後決定離散化，然後就過了。做完後決定去亂做 pE，然後也過了，這個時候比賽已經開始了兩個小時多。

接下來就是交替想最後三題，然後想到 pH 的 38 分解，丟上去後過一陣子沒什麼突破性想法，就先去寫 pI 的暴力分，這個時候是 3 小時 13 分，也是我分數最後一次改變的時候 (?)，在這之後我的想法就沒什麼進展了 QQ。

結語

總分 647/900，rank 4

比賽結束後被卡在場地裡不能去拿手機，所以大家都在到處問分數，除了前三名外問到的每個人都只比我低一點點，想說大概是 4~6 名左右吧，放人之後去拿手機看，居然是第 4 名，還滿開心的，從上次連三等獎都沒有到這次二等一，也算是雪恥成功 (?)。

比賽剛開始大概十分鐘的時候外面有人說我還在睡覺，其實我一直都是先把題目看完再開始寫，從我第一次打 OI 制比賽（去年北市賽）的時候就是這樣了，不過我這次才發現原來這樣做的人是少數，大部分人看到水題就開始寫了。我會這樣做是因為 OI 制通常不會照難度排序，而且 OI 制的時間壓力不像 ICPC 制那麼大，先好好把題目都讀完也能做得比較順。