IOI 2022

高中最終戰，因為回國後都太忙了這幾天才有空寫，希望我沒有忘記太多東西 QQ。

計分板·題目

Day 1

題目

pA 鯰魚養殖場 (fish)

3 / 6 / 9 / 14 / 21 / 17 / 14 / 16 = 100

有一個池塘是 的表格，還有 隻魚，每隻魚有重量，第 隻在 。你要蓋一些碼頭，一個碼頭是一個 column 中靠下方的連續一些格子。你能抓到一條魚的條件是那一格沒有碼頭，且它左右至少有一格碼頭（下面不算）。

求你抓到的魚的總重量最多可以是多少。

、

第一直覺就是要 DP。我第一眼看到以為是超水 DP，只要維護 第 個 column 碼頭蓋到 的前 個 column 的答案，再用線段樹轉移就好，快寫完的時候才發現這樣同一隻魚會重複算到。

仔細想了想，每一個 column 都可以分成下一 column 的碼頭要變高或變低兩種況。如果是變低的話，那這一 column 的魚都只會被左邊 column 抓到，一樣用線段樹轉移，無論前一 column 到這一 column 是變低還變高都很簡單。但下一 column 要變高就有點麻煩了，如果這一 column 比前一 column 高（也就是低中高），那也很簡單，不過高低高就有中間重複算的問題。花了一點時間想後，才發現高低高不如中間不要蓋，這樣就解決了。

pB 囚徒的挑戰 (prison)

5 / 5 / 55 = 65

有 500 個人，他們會按照任意的順序進入一個房間，每個人只會進去恰一次。房間裡有一個黑板，一開始上面只有一個數字 ，還有兩個提袋 A,B，裡面有不同數量的錢幣。每個囚犯進去房間後，可以先看看黑板上的數字，然後決定打開 A 和 B 的其中一個，查看錢幣數量後，修改黑板上的數字（可以和本來一樣），或說出 A 和 B 哪一個錢幣比較少，有人回答後就會停止。

你要決定當一名囚犯看到數字 時要打開哪一個提袋，並打開提袋看到 後要做出的動作，目標是讓囚犯回答正確答案，並且寫上黑板的最大數字盡量小。

標準的 IOI 怪題，最後一個子題的給分方式是一個怪怪的給分表。

前兩個子題的最大錢幣數量是 ，對 內的數字分 塊，先讓第一個人（看到數字 ）去看提袋 A，記錄塊編號後，讓第二個人（看到 塊數量的正整數）去看提袋 B，如果在不同塊就有答案了，不然就記錄那個數字是塊裡的第幾個數字，再加上塊數量來分辨，第三個人就可以回答答案。這樣會用到最大的數字大概是 45 左右，可以拿到可憐的 10 分。

既然要比大小，第一個想到的就是要比字典序。最後一個子題的最大錢幣數量是 ，轉成二進位有 個 bit，所以就要用到 個人，第 個人記錄最高數來第 個 bit，並且每個人交替打開 A,B 袋，這樣就只會用到 種數字，可以拿 46 分。其實最後一位可以不用記錄，因為看到最後一位就知道一定是最後一位不一樣了，只要看是 0 還是 1 就知道這一袋是比較大還比較小，因此只要 種數字，拿到 55 分，總分 65。

pC 廣播電塔 (towers)

4 / 11 / 12 / 14 / 17 / 19 / 23 = 58

有 座塔排成一列，第 座塔的高度是 。

接下來有 筆詢問，每筆詢問給 ，求你最多可以選幾座塔使得它們兩兩可以互相通訊。兩座塔能互相通訊的條件是它們中間有一座塔（不一定要被選），高度比兩座塔都高至少 。

因為 IOI 最愛 Cartesian tree，所以就先來想 Cartesian tree (O)。做一棵大的放上面的 Cartesian tree，首先兩座塔要通訊肯定會選它們的 LCA，所以換成每個點去顧兩個子樹裡能不能互相通訊。

如果某個點 的兩個子樹裡，都存在高度 的點，那就不應該選 ，因為 肯定不能跟它們通訊，不選 的話，在它的子樹裡就可以選到至少 2 個點，除此之外， 的所有祖先也都不應該選，理由相同。我們說這些不該選的點是標記點，我們知道標記點都不能選，而且對於任一個非標記點，它的子樹裡最多都只能選一個點（可以當中介塔的點一定是標記點）。這樣就可以得出，要選一個點的條件是「父親是標記點、自己不是標記點」。

這樣就做完了 的兩個子題，拿到 23 分。接著去做 的子題，會改變的東西只有 ，我們說「兩個子樹裡都存在高度 的點」的點是「好點」，會發現會讓每個點是好點的 都會滿足 某個數字，而會讓一個點會被選的 ，就是使得它和它的所有子孫不是好點、使得它的父節點是好點的 ，因此會讓某個點是標記點的 是一個區間，預處理好後就可以回答了。

再來我想了很久要怎麼做 ，才發現是水題。對於一段遞增或遞減的區間，會被選的一定只有最低那個而已，也就是說會被選到的東西只有谷底，而在 的時候所有谷底都可以選，因此先找好所有谷底、再好好處理一下詢問的左右界就可以了。

最後一個小時我都在做所有 皆相同的 subtask。想法大致上是混合前面所有 subtask 的作法，我們只 care 所有谷底跟山頂（local minimum 和 maximum），根據前面的結論，某個谷底要選的條件是，左邊和右邊比較矮的山頂（比較矮的那個是 Cartesian tree 上的父節點）高度比自己高 ，而且在山頂的另一側也有一個比這個山頂低 的谷底。滿足這個條件的時候，詢問的區間會包含某個固定的區間，然後問題就會變成二維偏序，只不過這題強制在線，所以要寫個持久化線段樹。

我寫完後發現還得處理詢問區間造成的多出來的谷，然後就寫不完了 QQ。

過程

老樣子開場打模板、讀題，讀完題後如上面所說，以為 pA 是超水題，pB 只會做分塊，pC 沒什麼想法。

因為以為 pA 很水，所以就直接開寫滿分解了，因為是一邊想一邊寫所以寫了有點久，還寫得很亂，寫完後測範測才發現是錯的（還敢不測範測 QQ），因為我讀題就花了快一個小時又浪費了很多時間，還不會做我認為的水題讓我覺得很緊張，但還是硬著頭皮在腦袋一片混亂下想到正確的作法，只是因為又是一邊想一邊寫，導致寫了很久。最後在 1 小時 55 分 AC，從 200 名變 10 幾名 (?)。

再來去做 pB，沒有直接寫分塊的想法，畢竟不太好寫，而是多想了一下，想到了比字典序的方式，在 2 小時 32 分拿到 65 分，然後這題分數就沒再變多了 QQ。

接著就是做 pC 了，想了很久總算有點想法，三個多小時的時候拿到 的 23 分，因為目前為止分數有 188 分了，心情也輕鬆了一點，很快就想到 的作法，只不過寫了有點久，3:51 才寫完。

再來就是做 ，我心想會 的話， 都一樣應該就呼之欲出了，結果並沒有， 超水。雖然計分板上我從過 到過 只花不到 20 分鐘，但我前面其實花了很多時間想 ，太笨了。不過確實對 都一樣有一點提示的作用。

目前分數是 205，超過 200 了，接下來我有兩個選擇，做 pB 或繼續做 pC。我前面其實也有時不時去想 pB，但一直沒有什麼突破性的想法，而 pC 看起來離答案不遠，所以我決定去做 pC。在大約 4:20 的時候，我想到了 都一樣的作法，只是要用持久化線段樹而且只剩半個多小時。

我還沒寫 pC 的第一個子題（只有 4 分），但我覺得寫持久化線段樹一分一秒都很重要，所以我就決定先開寫，最後來不及再去寫那個 4 分。最後剩十分鐘我超想上廁所，但去上廁所的話一定會來不及。結果就是有東西沒考慮到所以來不及寫完，只好剩五分鐘的時候先去拿 4 分，然後去上廁所，上完回來就已經結束了。

總結

分數 100 / 65 / 58 = 223
rank 22，在金牌中後段

因為手機放在房間裡（比賽在飯店裡類似宴會廳的地方），沒辦法馬上看計分板，只好先到處打聽分數。聽到 balbit 說他 225、他問到的其他人差不多也都這個分數，所以我想說我的分數應該還算可以。後來 LO（guide）來找我們，給我看直播計分板，是結束前幾分鐘的，我好像是第 19 名左右，雖然出去後看到的低了一些，不過還算可接受。（還有一天要打，就算不能接受也得接受……）

不過比賽過程真的有點慘，pA 假解浪費太多時間，果然還是不應該一開始就寫滿分解 @@。

結束後問到 pB 作法是拆成形狀大概是 的式子，然後 剛好是 20，應該是用 DP 湊出來的。我覺得我多想一點可能想得到，但還是做 pC CP 值比較高。

balbit 的 pC 都一樣也是用持久化線段樹，真希望我 pA 不要浪費時間 =_=。

Day 2

pA 數位電路 (circuit)

2 / 7 / 9 / 4 / 12 / 27 / 28 / 11 = 100

有 個輸入閘和 個 threshold gate，一個 threshold gate 有至少一個輸入，輸入可以是輸入閘或另一個 threshold gate，除了 0 號閘（是 threshold gate）不是任何閘的輸入外，其他的閘都是恰一個閘的輸入。每個 threshold gate 都有各自的參數 ，如果它有 個輸入那要滿足 ，表示當它有至少 個輸入的狀態是 1，那它的狀態就是 1，否則是 0。

給你所有輸入閘的狀態，求有幾種設定參數的方式，使得 0 號閘的狀態是 1。有 筆詢問，每筆詢問會反轉一個區間的輸入閘的狀態，輸出反轉後的答案。

白話文就是有一棵樹，給你所有葉節點是 0 或 1，要你給每個非葉節點決定一個正整數 子節點數量，它有至少 個子節點是 1 它就是 1，不然是 0，求有幾種方法讓根節點是 1。

第一眼看到就覺得是那種我最不會做的題目，畢竟要算數量。、 的子題很簡單，只要 DP 就好了。

接下來有兩個完全二元樹的子題和一個滿二元樹的子題，看起來二元樹很重要。假設某個節點 的兩個子節點中，其中一個考慮它的子樹，讓它是 1 的方法有 種、全部方法有 種，另一個是 和 ，那麼 是 1 的方法有：

• ：
• ：

相加就是 ，換句話說就是子節點 1 對答案的總貢獻會乘上 、子節點 2 會乘上 ，往下推後每個葉節點都帶有一個權重，答案就是葉節點狀態乘權重的總和，用線段樹可以做區間反轉。

做完了二元樹的 case，我就猜不是二元樹的狀況是一樣的，每個節點對答案的貢獻，都是自己的「兄弟的子樹裡的總方法數」倍，換句話說每個葉節點的權重是除了它的所有祖先外，所有節點的參數選擇方法總數。

把三個子節點的式子爆開後發現是對的，在暴力裡加個 assert 也是對的（雖然我因為 assert 寫錯多花了點時間），然後就 AC 了。

雖然過了很開心但我只覺得這是一個爛結論題……。

題外話，他的模數是 ，我本來想說怎麼模一個那麼怪的偶數，賽後才發現它是 。

pB 最稀有的昆蟲 (insects)

10 / 15 / 14.06 = 39.06

有 隻蟲，每隻蟲有各自的種類。你有一台機器，你可以做三種操作：

• 把一隻指定的蟲放進去。
• 把一隻指定的蟲拿出來。
• 詢問機器裡，出現最多次的昆蟲種類是出現幾次。

求出現最少次的種類是出現幾次。

每種操作最多可以做 40000 次，。

又是標準的 IOI 怪題，給分方式是對 給分， 是每種操作的次數最大值。

看到這種題目的第一個想法是二分搜，二分搜答案，檢查 時把昆蟲一隻一隻放進去，每放一隻就詢問一次，如果數量多於 ，就把剛剛那隻拿出來然後記著，最後記下來的所有蟲屬於的種類，就是數量 的種類。然後先把機器清空，再把記下來的蟲一隻一隻放進去，詢問回傳多於 1 就把剛剛放進去的拿出來，這樣機器裡的蟲就是不重複種類的了，最後再把其他的蟲也放進去看種類有沒有在裡面，就知道每隻蟲屬於的種類出現次數是不是多於 。

這樣子操作一次要花三種操作各大約 步，二分搜要做 11 次，但要 才會有分數。解決辦法是先把超過 次的拿掉，如果所有都 ，那就代表最多只有 種，每種各別挑出來，否則就用本來的作法。這樣是 步， 選 4 的話就可以壓進 20 的範圍了。（ 是我忘記我怎麼做了。）

後來我有亂調 看看，有稍微變高一點點 (?)。

pC 千島群島 (islands)

5 / 5 / 21 / 24 / 45 = 55

有 座島和 個船，第 條船一開始停在第 座島，當它停在第 座島時你可以把它開到 ，它停在 時你可以把它開到 ，你只能開你所在的島的船，開完後你會到目標的島上，並且船會停在那裡，你不能連續開同一條船兩次。

你一開始在 ，你要找到一個開船的方式，使得你造訪至少一個 以外的島，並且最後回到 ，而且所有的船都在初始位置。可能會無解。

、，答案不能超過 步，如果正確輸出有沒有解但沒有構造解的話可以拿 35% 的分數。

我一開始讀錯題目了，沒看到船要回到初始位置（還敢不看範測？），再加上有一題超水題很正常，所以我就以為它是超水題了。船不用回初始位置的話就很簡單，只要找到一個環就好，我寫完後就找很久我為什麼錯，才發現我讀錯了。（這造成的慘案請看過程。）

第一個子題 有解若且唯若 往 至少有兩條船、 往 至少一條船。

第二個子題的船是雙向的完全圖，就拿三個點，有兩個環各正反走一次就好。

第三個子題是第 個船和第 個船方向剛好相反，如果把這樣的一對船視為一條無向邊，那只要從 能走到一個度數至少 3 的點，或者有環通過 就有解。

第四個子題是第 個船和第 個船一樣，一樣把它們當成一條邊的話，有解的條件就是可以從 走到一個環。

因為要構解，而且解是輸出船的編號，所以寫了滿久的。

過程

開場讀題，看錯 pC 以為是水題，pA 看起來好可怕，不過先把二元樹的想完了，pB 知道可以二分搜但次數超過一點點不知道怎麼辦。

先做 pC，花了一堆時間發現我看錯題，但因為乍看之下沒有很難，再加上水題的第一印象，我就又花了點時間想。有好幾次以為我想到解了，但是準備要寫的時候又發現是錯的，反覆幾次之後我才確定這題沒有我想的那麼簡單，所以先去做有點想法的 pA。

pA 決定先寫暴力，然後用暴力驗滿分解的猜測，因為一直耍笨所以還 WA 了一次，開場兩個小時第一次 submit 只有 2 分差點哭出來 QQ。我 assert 還寫錯東西導致 assert 出來是錯的，讓我慌了一下，還好我沒有直接認為猜測是錯的而是認為我寫錯了。雖然經歷了一番波折，還是在 3:06 拿到了 AC。

接下來回去做 pC，我心裡還沒完全放棄所以還是有花一點時間想，不過都沒什麼進展，只好把子題都寫掉。因為很難寫所以寫了很久（而且我剛剛沒有把子題的細節想清楚），在 4:02 才把該拿的分數都拿完。

最後只剩一個小時，當然就是至少要拿到 pB 的一點分數。拿因為真的沒剩多少時間了（我第一次在最後一個子題拿到分數已經是 4:48），所以分數很少，最後幾分鐘亂改參數，比賽就在很想哭的狀態中結束了。

總結

分數 100/39.06/55 = 194.06
Day 2 rank 41，小慘

賽中壓力整個超級大，畢竟我有一個小時都在浪費時間，再扣掉讀題的一個小時，實際上寫的時間只有三個小時。

出去後
我：超可怕，我兩個多小時才有分數。
教授：嗯我們也這麼覺得。
我很抱歉 QwQ。

啊不就還好沒有即時計分板（教授應該也是一個小時才能看一次之類的，其他人大概只能看直播裡偶爾出現的計分板），不然大家都被我嚇死。

賽後聽到 pB 做一輪其實只要 次，就先預處理好每一個種類的最後一隻蟲是誰，就不用第二步驟，要是有再多 30 分鐘我應該會想到吧……。整個超級虧，我的步數直接變兩倍，好好做的話至少會有 50 出頭的分數 @@，金牌就我最低分。

主要的問題應該出在 pC 真的浪費太多時間，55 分已經是第 9 名的分數了，根本就不該在那邊浪費一堆時間想，更何況讀錯題。

總總結

兩天的分數分別是 223 和 194.06，總分 417.06，總排名 29。

第二天出場的時候跟教授要計分板看，第 29 名，整個嚇死，金牌線大約就會落在 29 左右，非常可怕。不過從計分板人數算起來今年金牌線會在 30，就算再少幾個人應該也還是 29，而且擔心也沒用了，所以我也沒有太緊張。

雖然我已經不是 OI 選手了但還是做點檢討來警惕後人 (?)。兩天基本上有浪費時間的問題，只是 day 2 比較嚴重而且比較不合理（是讀錯題造成的），至少 day 1 的浪費時間沒有很久而且對 AC 是有貢獻的，day 2 浪費的第二個小時跟掛機沒什麼兩樣。

還有就是兩天都是做完一題再去做下一題，就是卡題的意思，兩天的浪費時間都是因為卡題，像 day 2 如果意識到 pC 讀錯題了就先去做已經有初步想法的 pA，還有想一點 pB，應該會好很多，至少到最後時間不會那麼趕，而不是硬著頭皮想要想出 pC 的滿分解。day 1 卡 pA 倒沒有造成太大的影響，畢竟 pA 確實是最簡單的題目，只不過卡題是個高風險低報酬的行為。

本來的時間規劃大概都是在第二個小時把認為水的分數都拿到，因為我覺得我還是比較適合保守策略，只是兩天都在覺得水的題目上出包導致策略全亂。

雖然過程上很糟糕，但至少結果還是很幸運的還不錯，好在 day 1 分數高把 day 2 救回去。呼籲大家不要卡題 QQ。