TOI 2022 1!

Created2022-04-03Updated2022-04-05

原本是有打日記，但打一打發現每天都差不多就想說算了，放一些重要的事情就好ㄌ

總覽

今年的課程表跟去年有點像，唯一的差別大概是模考又被往前搬了一個小時回到九點

教授的課跟往常一樣，除了王炳豐老師外都不太會管，所以我大多的時間還是在補題，virtual 好像也只 vir 一場吧

然後今年還是有逼我們寫怪怪 Uva 題的環節，到底甚麼時候可以把這東西拔掉阿，有夠討厭 @@

國手課的部分跟去年重疊性有點大，但還是聽得蠻開心的

觀察力訓練還是拼拼圖，雖然今年拼圖課大家都在上課中間拼，拼圖課反而沒甚麼人在拼XD

然後還是有體育課 = =，但今年體育課三天下雨，唯一上的一天的活動也沒到去年那麼操

倒是休閒娛樂少了不少，gartic 其實兩個禮拜下來沒玩幾次，jstris 去年選訓我玩很多，今年倒也沒什麼玩，大螢幕動漫也沒有去年那麼頻繁，而且因為 ZCK 還是蛋餅回來播了壽司大相撲導致到後來都在播那個

餐點的話因為西餐廳換店了晚上關了導致現在晚餐只有自助餐，原本以為要吃兩個禮拜的自助餐了，但最後幾天因為自助餐老闆吵架所以都改成訂便當或是其他外面的東西

飯店還是很棒的西門捷絲旅，只是今年從兩人房變成三人房
今年飯店後的休閒少了桌遊變得比較少活動，每天基本上就只有狼人殺和日麻兩團，但還是玩得蠻開心的XD

總之，每天就是刷題、耍廢、狼人殺、耍廢的無限循環，但也蠻喜歡這樣的生活的

一模

一模策略的話其實跟去年差不多，只是覺得波路特石禮拜三回來講的一個東西很有道理：每一題看完先花 10 - 15 分鐘認真想一下，就決定在模考用了
總覺得沒經過 virtual 就在正賽用新的策略好像有點糟糕，但我還是用了

過程

總之開賽先打完模板看完題目，每題停了 10 - 15 分鐘想了一下，大致的結果：

  • pA O(n2+ClogC)\mathcal{O}(n^2 + ClogC) 很好拿，剩下不會
  • pB 有一個顯然的 O(n)\mathcal{O}(n) 狀態 O(n)\mathcal{O}(n) 轉移的 dp
  • pC 前幾天才在 CSA 寫過幾乎一樣的題目，但我是寫根號。然後我記得那時候問 AC 有說這題可以不用根號，但我也沒有再問詳細的做法，當下就感覺頗燒雞的。後來這 10 分鐘想了一下也確實沒想到更好的做法
  • pD 沒啥特別的想法，大概就是凸包 DP 之類的東西

感覺每題都蠻可做的，有點意外，所以就從 pA 開始寫
pA 寫 O(n2+ClogC)\mathcal{O}(n^2 + ClogC) 的時候 codeblocks 在雷當掉了三次，是還好沒花太多時間就想到解決方法了，寫完之後丟了也順利拿到

pA TLE Score 56

再想沒幾秒就發現 O(n2)\mathcal{O}(n^2) 可以用排容壓成 O(ClogC)\mathcal{O}(ClogC)，寫完之後傳卻發現還是沒過滿分

這時候應該就要跳了，但 pA 感覺就是壓一下就會過了，所以又花了一些時間壓但還是過不了，之後亂試一下發現只跑一次 O(ClogC)\mathcal{O}(ClogC) 的話不會爆 TL，就靈機一動想說把一個算因數數量的 O(ClogC)\mathcal{O}(ClogC) 改成 O(nC)\mathcal{O}(n \sqrt C)，然後他就莫名奇妙過了

pA AC Score 100

拿了一題心態也有點穩定下來了，就繼續先寫 pB 的 O(n2)\mathcal{O}(n^2)，但花了一段時間寫完發現自己算完 dp 後根本就不會算答案 = =，燒雞

之後回去看 pC，又想了一下真的沒辦法就只好寫 O(nm⋅logm)\mathcal{O}(n \sqrt m \cdot log m) 的解，不知道是鍵盤原因還是我今天就是不會實作，總之我還是寫了超久才寫完，然後傳

pC WA Score 0

看到 0 分愣了很久，應該很合理能想到是被卡 Hash，但我想了很久才想到這個可能
後來因為我只需要前綴和後綴的 Hash 值，所以直接用一個 trie 搞定

pC TLE/MLE Score 11

發現全部的前後綴 string 有點多，所以塞不下也會 TLE，燒雞就回去 pD

pD 實在是沒啥想法，DP 枚舉的東西不對導致的狀態一直卡在 O(n5)\mathcal{O}(n^5)，這時候剩下大概兩個小時，又覺得自己要拿到那 11 分需要一些時間，所以決定先放掉最後再回來喇

回去 pB，盯著前面寫下的東西發現有一個超級好寫的狀態 O(n2)\mathcal{O}(n^2) 轉移 O(1)\mathcal{O}(1) 的 dp 解，寫了不到 10 分鐘就寫完了

pB TLE Score 56

這時候有想到一個 pB 的優化解，花了不少時間把它寫完之後才發現是假解，我真的好笨喔 @@

發現剩快一個小時就先去拿 pD 11，以為是凸包刻爛 debug 了二十分鐘，結果是 while 打成 if，完全不知道自己在幹嘛 = =

pD TLE Score 11

回去 pC，拿了之前的 code 把一個 hash 改成兩個就過第二筆了

pC TLE Score 37

這時候大概剩下 20 分鐘，原本想要就停住看能不能想到 pD 很肥的第二筆

我算一下現在我的複雜度是 O(nm⋅logm)\mathcal{O}(n \sqrt m \cdot logm)，而那個 log 是塞 hash 值的 map，因為是 hash 所以可以視為 random 的，那這樣套 unordered_map 感覺好像就可以壓掉 log 了欸
沒 log 的話以師大 judge + 師大測資好像不是不可能的事，總之我把 map 換成 unordered_map 之後就傳

pC AC Score 100

我真的沒有預期他會過，所以看到 AC 的瞬間有點被嚇到

這樣算一下成績，267，以這場的難度好像算普通吧，但只剩下 10 分鐘就只能盯著 pD 第二筆 subtask 發呆，好像快要想到就結束了

結果

Score: 100 + 56 + 100 + 11 = 267, rk: 7

國手線下 96 分，二階線上 45 分

出來馬上聽到 syl 和 che 都破台就有點嚇到，還在擔心會不會全世界都 300+ 然後我沒在二階線上，還好是沒有，但和國手線就拉開蠻大的差距了 QQ

後來破台的多一個 balbit，wiwi 和 FHVirus 只缺 pD 37 就破台，導致國手線直接飛起來惹 =w=

怎麼說，雖然我覺得我打得頗遭，pC 沒賽過的話甚至會掉到二階線外。以這場的難度要有 300 我才會滿意，但既然我還是有在二階線上，現在要做的事情就是穩穩的打完二模，如果有三四模的話再來追吧

檢討

  1. 沒先仔細想清楚，在假解浪費太多時間 (pB)
  2. debug 智障錯花太久 (pD)
  3. 實作速度燒雞，花有點多時間 (pB, pC)
  4. 被卡常應該要跳題，在這上面花太多時間讓前期心態有點炸 (pA)

二模

二模策略跟一模基本上一樣，主要就是先求打穩再說

過程

總之一樣先看題目 + 想 10 - 15 分鐘

  • pA 前兩筆顯然位元 dp，滿分解應該是樹 dp，但要還不知道怎麼處理節點往上走的情況
  • pB 互動怪題，前兩筆是裸的 dp 和二分搜，感覺切成 5 * 5 或是 1 * 25 做 dp 可能會有一點分數
  • pC 怪題，這裡想的題目是錯的所以就不講我那時候想了什麼了
  • pD 裸的 dp 題，轉移式列出來顯然可以斜率優化

很意外模考居然有那麼裸的題，所以直接開寫，先寫了一個 O(n2)\mathcal{O}(n^2) 驗了 dp 後直接寫了一棵李超傳

pD WA Score: 43

WA??
我以為我被卡常，點下去看居然 WA 了兩筆 subtask???
因為有一筆 subtask 很好寫，就馬上寫了那筆丟上去

pD WA Score: 0

當下直接認定測資爛掉，我實作再怎麼爛 C=1C = 1 的 case 也不會寫爛吧 = =
不過後來想一想有想我會不會是 INF 設太小，但改完還是一樣就想說算了就丟掉這題了

因為 pA 只會前兩筆而且我寫那兩筆只要不到 10 分鐘，所以就先去寫了 pB

pB 我先寫切成 5 * 5 的作法，互動題弄了一些時間，但比起去年一模這次算是用的蠻順利了
總之寫完又抓了一下蟲總算拿到了分數

pB Partial Score: 40.???

小改一下就多拿第一筆

pB Partial Score: 46.???

因為實在沒其他比較好的想法，就先把第二筆的二分搜也寫完

pB Partial Score: 54.???

恩，54 感覺還不錯，多試了幾種不同的長寬發現最高大概就這樣了，就先丟掉去想 pC

差不多這時候吧，pD 發公告說待會會 rejudge，基本上可以認定是 AC 了

pC 想一想發現照我解讀題目的話會沒辦法 AC 這題，這樣有點怪所以又重讀一次題目發現漏看一個條件

看完就 claim 了每一個 pair 的和要相等，不然沒道理它可以 AC
因為這個 claim，所以很合理的會想到 subtask1 怎麼做，因為大概也是 10 分鐘可以做完的東西所以我先沒寫

繼續想一想發現把這些 pair 放到圖上很合理，就把他轉成：

「你要在一張 4-regular graph 保留一些邊，使每個連通塊都是環且每個點都在一個環上」

然後就燒雞了，這東西根本不知道要怎麼找，後來亂寫了一個 dfs 但直接吃了 TLE

這時候大概剩一個半小時吧，我覺得我想不出 pA，就算想到我有高機率寫不出來，所以花了 10 分鐘寫完前兩筆就放掉

pA TLE Score: 32

也順便把 pC 第一筆拿完

pC TLE Score: 10

大概剩一個小時，我在想我要把時間花在 pB 還是 pC，我選擇了 pB，因為 pC 那東西我真的想不到比較好的做法去弄他 = =

pB 我想到的改良法是先用前面的方法找出最佳解路徑，然後再詢問最佳解路徑周圍一些邊的大小，花了快半小時寫完後發現沒有比較好，我也不知道為什麼
總之後來就是一直亂改亂丟，但分數還是沒變

然後因為 pD rejudge 他有補償時間給被影響的人，我運氣不錯撿到了六分鐘，但我多那六分鐘還是做不了什麼就結束了 QQ

結果

Score: 32 + 54 + 10 + 100 = 196, rk: 8

國手線下 96 分

總之是穩住二階了，結果 pC 是直接抄 IMO 2020 p3，有夠氣 = =
到底為什麼要偷 IMO 的題阿，之前偷 CF 題就算了，那至少還是資訊題
但在資訊比賽放這種大比賽的數學題顯然只會讓一部分的人受益R，完全不懂 = =

不過我也是蠻笨的，pC 歸成圖論卻沒想到跑個匹配就做完第二筆 subtask 了 = =

完全沒和國手線拉近，現在就希望三四模考好靠 60% 拉上去吧~

檢討

賽中想 pC 的時候其實有一瞬間有找歐拉迴路的想法，有點後悔沒繼續想下去
畢竟這種怪題基本上只能憑忽然的想法，有想過卻沒繼續想就顯得有些可惜 QQ
不過說真的繼續想歐拉迴路可能也有高機率推不到滿分解ㄅ，就算了

整體來說這場打得比一模好很多，也沒什麼失誤

一些廢話

模考題目品質逐漸樂觀

一模出太水先不說，pA 卡常實在是很糟糕
很多人是被卡常送下去的，畢竟一被卡就是直接 -48
其他的話 pC 還是有點無聊吧，pB 和 pD 都還不錯

二模老實說我還蠻喜歡 pA 和 pB 的，但 pC 偷數奧題真的很扯 = =
那些出題的 484 不知道一堆比數奧的都在這裡R
就算是這樣也不該偷一個 IMO 題，還是兩年前的
更何況還是那一年的 p3，完全不公平
然後 pD 就是無聊的經典裸題，沒啥好說的

總之，現在我只希望三四模題目正常一點 = =