全國資訊能力競賽 2021
最後一年的全國賽了
去年因為不會矩陣不會構造也不會DP燒雞兩個半小時只有三等
總之賽前的目標是定在不用考初選的二等
主要還是被去年初選嚇到怕了= =
總之直接進入比賽ㄅ
賽前計畫和全國模擬賽的其實差不多，有興趣可以參考看看
題目
有空會補
比賽過程
首先一樣先花半小時看完題目，看完大致想法
pA 廢到笑
pB 點到直線距離 但幾何燒雞不知道要怎麼判方向
pC 不會
pD 二分搜 + 拓樸排序 構造解的話這題CSES有類似的梗
pE 沒特別的想法
pF MCMF!!!
pG 樹壓平 然後認真想我到底有沒有看錯題目
pH 部分分很多 直覺二分搜
pI 只看完題目而已 但也有注意到部分分有64
總之看完就開始寫
pA 秒掉
[00:32:17] pA AC 100
考慮到pB沒想清楚細節，pC又想了一下還是沒啥想法，就乖乖先去刻pD
[00:54:51] pD WA
智障bug
[00:56:56] pD AC 100
之後想到了pB的作法
[01:14:56] pB WA 30
看了很久沒看到就先跳
回去想pF的MCMF怎麼建模
想了一下發現不太對，就和pB交互看
到了快兩個小時都沒出來發現不太對 忽然想到pG裸題還沒寫就先寫
[02:03:00] pG WA 0
看到WA當下真的頗崩潰，以為是題目看錯就回去重看一遍
結果後來在檢查一次發現是線段樹忘記push
連這種小學生錯都會犯真的是沒救了= =
[02:11:10] pG AC 100
寫完回去pF發現我後面建模建到把題目意思搞混了 重新再看一遍發現只是簡單DP
[02:39:32] pF AC 100
後來回去想了pE的subtask，想了幾個解都被自己hack掉，發現已經快到喇分線了，就去想了pH
想了一下總覺得的subtask不難，但還是先刻了一個排列爆搜
[03:11:19] pH 15
之後想了pI 一臉就是線性遞迴 + 矩陣快速冪，總之沒花多少時間就把轉移式先寫好
[03:18:50] pI 64
這時最智障的事情發生了，因為我的矩陣列出來的維度是5，我不知道是腦袋撞到還是怎樣，總覺得這樣TL = 0.1s不會過
總之這36分就被我直接放掉了= =
然後回去繼續寫了一些pE的假解
然後總覺得pB是一定要拿滿的東西
當下就回去改了一下還是過不了
這時就想起今年初選燒雞後得出的結論：找不到錯就換想法刪掉重寫
想了一下想到三分搜的作法
[03:59:31] pB AC 100
這個人沒救了啦 剩一小時才AC水題
剩一個小時，稍微看一下自己還沒拿滿的分數：
pC 0, pE 0, pH 15, pI 64
感覺沒空想滿分解了，就直接以部分分為主
雙指標
[04:34:56] pE 19
greedy亂做，其實沒嚴謹證不過還是過了
[04:40:50] pH 40
剩下20分鐘砸在pC的33上，因為太狗幹了很可惜的在比賽鈴聲的時候才寫到剩一行輸出答案
然後就結束了QQ
成績
Score: 623/900, rk: 8
幸運的撈到了二等獎，再少撈一筆subtask就下去了 怕爆
這場精神狀況還算不錯，不過以後可能還是要多練五小時的比賽了吧
檢討
這場真的很多地方可以檢討，畢竟自己還是認為打得頗爛@@
首先放掉pI 36真的很白癡，尤其我比賽前兩天才刻過矩陣快速冪，而且發現我刻矩陣快速冪只要4分鐘
加上我那題的矩陣只有5 * 5，而且有單純的DP轉移式，加起來我寫的時間甚至不用10分鐘
那這種有高機率過的東西我到底在猶豫什麼?
追根究柢還是我在pB卡太久，那題至少卡了我半小時，那些時間足夠讓我把pC的33分拿到手，丟完矩陣快速冪，
再講遠一點，pH 17分也是寫完40分的greedy就能合理想到解的東西，只是就是沒時間寫@@
其實也跟我之前講過的一樣，全國賽的重點在不能被水題卡太久，只要一不小心被卡住一定就會有來不及寫的事情發生= =
不過以後可能也不會有像全國賽這種比賽了，還是乖乖vir OI好了
總之還是蠻開心有達成自己賽前的目標，最後還是祝各位初選順利> <