前言 & 一些廢話
Written by pooh at 2025/01/28
新的一年的第一篇 Blog! 這段時間雖然有 vir 了一些比賽跟去了 IOIC，但 vir 的比賽都是那種有一天已經被暴雷導致完全沒有意義的 (e.g. IOI 2016，那年真的很得)。所以就沒有寫成 blog。IOIC 的遊記應該是不會寫，因為大部分別人都有寫了，我自己除了用唬爛跟題目對抗以外沒有做什麼特別的事，所以不打算寫。
新的一年的第一篇 blog 就寫我在除夕跟 browntoad, owoovo & guagua vir JOIOC 吧。
正文開始
題目
打題目，真的很累
賽中過程
0:00
讀完第一次題目以後的感想是 : 阿怎麼沒有有用的子題。
然後就開始陷入苦思，pC 一開始題目沒讀清楚以為他不一定是一棵樹，想說先縮完 BCC-E 以後再看看要幹嘛，但因為不想寫 Tarjan 所以決定先想好 A, B。
實際分數: 0 / 0 / 0
精神分數: 5 / 0 / 0
0:55
大概想了一小時以後得到的結論如下 :
pA 只要可以維護每一個距離有幾個點 u 可以 1 -> u -> N，就可以知道答案了，想一想就發現其實我們根本可以每次修改就暴力 dfs，找到所有他不能走以後會受影響的點。注意到每個點除非他的子節點們 (他的下跟左) 或父節點們 (上跟右) 有人從滿足上面的條件變不滿足他的才有可能從滿足變不滿足。所以他最多在這個改狀態的 dfs 被戳到 4 次，均攤一下超級好。
pB 完全沒想法，感覺最佳解會是一端的點是 [i, i + N - 1]，所以枚舉一下 i 可以有個
pC 應該是
實際分數: 0 / 0 / 0
精神分數: 100 / 35 / 100
然後就是從這一刻開始我的精神分就沒有改過了 QAQ。
1:12
pA 順利 AC，順便感嘆一下他真的是個很好的題目。
實際分數: 100 / 0 / 0
精神分數: 100 / 35 / 100
1:41
pC 一發 AC，然後就開始思考 pB 到底要怎麼優化。
實際分數: 100 / 0 / 100
精神分數: 100 / 35 / 100
2:04
先寫了一個
實際分數: 100 / 35 / 100
精神分數: 100 / 35 / 100
然後我就開始想 pB 到底可以做什麼事，發現我不會把 i 移到 i + 1，然後想說還是我隨機一下或 pooling 三分搜一下，但都沒有用，一整個被卡爆，他測資生太好了 (不對，應該說我的唬爛都沒有道理)。
中間一度重想過還是其實他上一個 Subtask 根本不是要我那樣，但也沒想到好作法，然後就倒了。
檢討
總分 : 235
大概是 Rank 37。
這場的 Rank 真的不是一般的得，因為題目性質切不了子題，導致大家分數都黏在一起。
很喜歡 pA，但還是希望題目難度不要這麼極端，不過主要還是因為我不夠強所以不能破台，如果能夠強一點的話就可以當 BOI 打了。
然後 pB 的正解真的可以環狀三分搜，只是是不同的
但我覺得 pB 的利用中位數