全國資訊學科能力競賽 2020

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

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

計分板

題目

前情提要：我在測機的時候發現一秒大約可以跑 次加法。

pA 礦砂採集

100/100

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

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

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

pB 村莊與小徑

100/100

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

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

pC 樣本解析

100/100

給一些只含有小寫英文字母的集合 和 ，求

1. 有多少個 滿足 。
2. 有多少個 滿足 。
3. 有多少個 滿足 。
4. 有多少個 滿足 和 部分相交。
5. 有多少種將 分成 和 的方式，滿足 兩兩不部分相交。

保證 互不部分相交且互不相等，且 至少與一個 部分相交，且不與任何一個 相等。

前面四個都是簡單的實作，看到 我也沒想太多，就直接 暴力做第 5 個了。

找到隨便一個和 部分相交的 ，那 的拆法就只能是拆成 和 ，這樣就只需要 檢查就好了。

pD 水果包裝

100/100

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

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

pE 共同朋友

100/100

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

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

後來想說一秒可以跑 次加法，如果我用 bitset 來判有沒有共鄰點，大概需要做 次，而且這題給兩秒，應該可以過，丟上去就過了。

pF 歡樂外送點

100/100

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

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

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

pG 矩陣相乘

0/100

給兩個 矩陣 、，已知 是一個最多只有 個非零元素的矩陣，求所有非零元素的位置和值。
，時限 6.5 秒。

完全不會做 QQ。

pH 跑跑遊戲場

38/100

給一個數字 ，還有一隻只能往右和往下走的老鼠，構造一個迷宮，可以在格子與格子之間放障礙物，使得老鼠從左上角走到右下角的方法數恰為 。
，如果迷宮大小是 ，會得到 分。

我的構造方法長這樣：

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

pI 黑白機

9/100

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

9 分是 的暴力，滿分解好像是 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 制那麼大，先好好把題目都讀完也能做得比較順。