TOI 2022 2!

這次講模考就好，其他小事沒啥特別的就不提了

三模

過程

開場一樣先看題目 + 每題想一下

看完題目只覺得兩題 communication 是三小 = =

pA：會第一筆和第三筆，滿分沒啥想法，感覺就是掃描線資結之類的
pB：想了一下有一個唬爛的想法，感覺蠻好的但我不會估(?
pC：會 k = 126，感覺 r = 1 那一筆蠻可做的但我還不會
pD：會前兩筆，滿分解還不會，感覺一臉要倍增

我想了一下決定從 pB 開，因為是純唬爛不知道會長怎樣還是先寫比較好

寫完之後傳

pB Score 23

後面都超過次數了 QQ
想了一下發現一個地方可以做點優化

pB Score 87

蛤？這麼高？

心裡想說那這題應該很好唬爛吧，每個人應該都很高就先丟掉去做 pC

pC 搞了一下互動格式後拿到 k = 126

pC Score 28

之後認真想了一下 r = 1 和 k = 93，感覺這兩個都可做但交替想了一下還是不會就先放掉去想 pD

pD 想了一下發現列出矩陣會變成 $\mathcal{O}(28^6log(10^{15}))$ 之類的詭異複雜度。然後不知道從哪裡看到的怪東西讓我覺得這可以壓到 $\mathcal{O}(28^4log(10^{15}))$

我賽中就覺得滿分解應該是那個，但我不會就喇完前兩筆先放掉

pD Score 45

這時忽然發現不對，因為我還離國手線差 64 分，理論上應該要全力做一題滿分才對，所以我決定想 pA 滿分，因為這種幾何題感覺就會有人做出來，沒做出來就會很虧 = =

想了一下就發現掃描線在掃的時候圓的相對位置不會變，然後就想到一個解好像可以把樹蓋出來做 dfs 之類的

但是他要 Treap，想了想就決定硬刻下去了，不然也沒救

Treap 倒是十分鐘就刻完了，但刻完之後再認真想一下才發現這是假解 = =

然後我就呆掉了，完全不知道要怎麼做

到這裡大概剩半小時，就趕快回去想 pC 的 subtask，但還是都沒想到就結束了 = =

然後因為我 pB 的解是 random 所以我不時會回去傳解，它最後變成 90 分

pB Score 90

結果

Score: 24 + 90 + 28 + 45 = 187, rk: 8

結果 pD 是全場最水@@，根本不是甚麼怪東西，只要 bitset 就好

其實有點生氣，連續兩年都被三模 pD 打爆，還剛好都是 bitset = =

不過 pB 倒是莫名拿了全場最高，我花在這題的時間甚至不到半小時欸，整個爽賺

這分數差其實剛好和我 pD 掉的分數一樣，所以說到底還是我太笨想不到 pA 和 pC

事實上，pA 我賽中的想法其實很接近了，只是我太執著於想要把那棵樹蓋出來
沒想到用比較暴力的方式就能處理完了

雖然實作頗長但以我的實作能力我不覺得寫不完，不過還是算了吧，終究還是自己太笨

現在變成差國手線 101 分，基本上是沒救了，四模就輕鬆玩吧~

如果我有 pD 多 55 分的話可能還有一絲希望，但差到破百這就真的沒辦法了

四模

過程

一樣先讀題目，這次有一題 communication 和一題我期待很久的 output only

這次的策略有想要逼自己盡量想滿分解，畢竟再不想滿分解就真的沒救了

pA：互動怪題，只覺得用某種方法可以得出相鄰兩項的比重，但還沒想清楚
pB：output only，因為這 output only 是構造題，所以根本不知道要從哪裡下手
pC：只會第二筆和第三筆，滿分真的好難orz
pD：很可做，但一臉就會被卡常

直接寫 pD，因為想法還蠻乾淨的所以大概不到 20 分鐘就寫完了，寫完丟

pD Score 23

恩，不意外被卡常
開壓了十幾分鐘發現還是壓不過
這時我就覺得已經沒救了，因為感覺每個人都是壓常大師就我壓不過

我做了一個以結果來看蠻正確的決定：丟掉這題去想自己想玩的 pA 和 pB

pA 和 pB 來回交互想了一下，pB 寫了一個 heuristic 的爆搜拿到了前四筆

pB Score: 16

之後一直在想 pB 某個怪 case，但真的想不到，構造有夠難 = =
也去亂優化前面的 heuristic 發現還是跑不動 n <= 200 的 case

中間一直在想要不要去 pC 至少喇完那兩筆，原本不想這樣做的原因是感覺拿到了也沒用

但後來還是決定回去拿，10 分鐘就寫完了拿了也不虧

pC Score: 13

後來 pB 真的想不到沒辦法就回去 pA，忽然通靈到一個方法可以找相鄰兩項的比例
感覺可以拿到的分數蠻不錯的就直接開寫，寫了一陣子噴了一堆 bug 後終於有分數了

pA Score: 33

恩，怎麼沒拿到第四筆？

這時大概剩下 20 分鐘，看很久找不到哪裡錯就等到上傳時限沒了就開始亂改亂傳
主要是我猜測有一個常數我調太小導致他精度不夠，常數越高當然會越準但分數也會比較低

那就來二分搜一下吧

於是我就手動用 judge 二分搜，終於在最後 7 分鐘拿到了第四筆的 partial

pA Score: 46.24

後來再多傳幾次也不知道分數有沒有變高就結束了

結果

Score: 46.24 + 16 + 13 + 23 = 98.24, rk: 2

總成績：rk: 7，國手線 -71.7

拿到二位其實頗意外，主要是我以為 pD 會有很多人壓過，但事實上只有 balbit 而已
這場也拿到 pA 的全場最高和 pB 唯一解出前四筆，雖然最後沒當上國手但以這樣的成績結束最後一場模考也算滿意了

以結論來說我差國手線 71.7 分，如果我有拿到三模 pD 的話可能就會變成遺憾了吧，該說我沒拿到反而比較好嗎(X

真的要說的話問題還是一模考太差吧，一模就差線破百了後面追的很辛苦 QQ
三四模倒是意外靠 heuristic 拉了不小的分數，但因為自己還是有不小心多噴不該掉的分數，所以到後來就沒救了

雖說沒當上國手難免還是有點失落，畢竟我當初會想拚資奧有一大原因就是有想國手的夢想，現在這個夢想已經永遠實現不了了 QQ

我也差不多該從 OI 退役了，高中競程也只剩下 APIO 和 YTP 了，希望這兩個比賽能順利 > <