本博客建立于 2020 年 11 月 6 日晚，于次日正式認證后更新涉及題目的內容并公開，本人未提前知曉認證試題，請讀者不必恐慌，
Day -4
久違地 AK 了一場模擬賽，
Day -2
因為模擬賽不給大樣例，T3 T4都A了，反而掛了 SB 模擬和歐拉路板子題，300分，
不過呢也是好事，至少不會給自己太大的壓力吧，
Day -1
吹了一上午的水，中午離校，
下午去看考場，和門衛對線后對方表示沒有接到任何通知，所以進不去……？
然后回家看了會 CDQ 分治，還是無法理解它的本質，
因為太久沒寫狀壓dp，就寫了個斯坦納樹練練手，又一次驚異于這個絕妙的構思，
寫了個整體二分，調了半天發現又是手賤把 vr 寫成了 r……
搜了幾篇游記看看發現完全沒用，
寫了發左偏樹，還WA了一次
眾所周知，考前復習板子的作用是把它移出考綱
睡了
Day 1
夢見在熬夜打麻將
上午劃水，看了下板子
下午進考場，感覺精神狀態不錯
13:50 就進機房了，然而不讓動電腦……
感覺這鍵盤比自己的還好用？
14:20 發題，密碼好像是什么 他山之石？
怎么輸都不對
過了會兒進來個作業人員說這是上午的密碼……orz
然后在大螢屏上打出真正的密碼，可以攻玉？
先是把 0 輸成 o，然后還是怎么輸都不對，旁邊的老哥也怎么輸都不對，監考過來看了我的螢屏一眼，
“你輸的括號呢？”
……
T1 ……大模擬
T2 奇怪的東西
T3 好像是個資料結構？
T4 詭異的博弈論
先把月份天數的陣列打出來！然后什么都不會了……
把公元前看成負數+1，可以少判很多奇怪的東西，感覺十分精神污染，就直接一個月一個月加，1582 年 10 月特判一下，貌似就有 80 分了？
后面隨便打個暴力都有三四十分吧，先放了
15:00 發現 T2 非常的水，隨便寫一下就過大樣例了，特判一下 2 64 2^{64} 264 ，但感覺非常不穩，
15:20 開 T3 ，怎么看都像可持久化線段樹合并，但這個 256M 空間限制了我的想象力……而且 DAG 線段樹合并的復雜度好像不太對，
遇事不決根號分治？考慮按每個函式的呼叫次數資料分治，發現沒有任何用處，
然后看了下部分分，只有乘隨便做，只有加……維護每個函式的呼叫次數？
有乘法的話把這個呼叫次數帶個前面乘的數的逆元的權就可以了？
那就是記錄一下之前的乘積，然后乘到這個點的線段樹上再亂搞一下？
16:00 了，感覺有點虛，就先打了個指數級暴力，懶得分析有多少分，
發現不用線段樹啥的，直接記錄每個點的貢獻往下甩鍋就可以了，
于是在草稿紙上寫下了：
- 拓撲排序
- 倒著計算每個點乘上的數 m u l u mul_u mulu?
- 正著計算每個函式的貢獻 f u f_u fu?
寫出來大樣例死活過不去，就把暴力拉過來測，發現大樣例暴力跑得飛快……
把最后一步乘以總的乘積注釋掉，發現第一個答案和暴力是一樣的，但注釋前不一樣，說明是總乘積算錯了？
重新開個檔案人肉而二分，最后發現我拓撲排序只把虛點壓進佇列里了，但有些沒用的點會貢獻度數，導致一些點入不了隊……
改了之后很快過了，
17:00，寫了個資料生成器對拍
然后 RE 了，調了一下發現生成器有環，就強制讓編號大于自己
然后暴力 T 了，就把資料改得非常小，
然后還是拍不上，標程好像輸出不了檔案，但雙擊 exe 運行是對的，開始以為是暴力太慢，但改了順序和一步一步執行都沒用，后來發現批處理有個叫 call 的命令……
17:30拍上了，掛在后臺慢慢跑， T4肯定沒希望了，就用 vector 寫了個指數級暴力，很快過了，
回去突然發現 T1 拿不到 80 分……于是冷靜分析正解，
拿暴力人肉二分歷法起點到公元元年和消失的 10 天的天數，然后前面 4 年為周期，后面 400 年為周期先算出整塊的，剩下的先年后月暴力，日直接加上，1582年后面兩個月硬討論，
還有 15 分鐘，邊開虛擬機邊調 T1，最后 5 分鐘調出來了，隨便測了下就交了，
預估
T1 因為 1582 年后面兩個月的硬討論出了點問題，會在 1582.12.1 \text{1582.12.1} 1582.12.1 和 1583.1.1 \text{1583.1.1} 1583.1.1 掛掉，民間資料只有 40pts，
T2 k = 64 k=64 k=64 并沒有判完，還是會 ub，
T3 0 0 0 求的逆元是 0 0 0，所以一旦乘了 0 0 0 輸出會全是 0 0 0 ，不知道會不會卡，
T4 其實狀態只有 O ( n ) O(n) O(n) 個，復雜度是 O ( n 2 ) O(n^2) O(n2) 的，
最低 40+60+60+55=215，最高 100+100+100+55=355,期望 40+95+80+55=270
真刺激
聽天由命了
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/208780.html
標籤：其他