0%

2021 全國賽

最後一次全國賽了 :(。這次比賽很酷,什麼都不能帶進去,連筆都要用他提供的,而且筆居然只有原子筆,我完全不敢畫題本(下面那個題本就是我的)。還有出去喝水上廁所都要寫記錄表,然後要簽名,到後來每個人寫字都超級醜 XD。

計分板·題目

因為最後才知道可以帶程式碼所以我沒有備份 QQ。

我懶得打題敘所以作法直接跟過程寫在一起吧。 (O

過程

開場打完 vimrc、default code 後一樣先讀題。A 是看完就做完了的水題、B 是不難的數學題,看完 C 後我花了一段時間想怎麼做,因為往年都有照難度排序,所以我就認為 C 應該不難,而且看起來也不難,但因為一直想不到,連子題都不會做,只好先看下一題。D 看完就想到是二分搜,E 只會做 的子題,F 稍微想了一下後覺得可以 DP,G 是樹壓平,H 看起來好難,I 是最後一題應該很難吧。因為看題目看太久了,後面幾題我都沒多想。

看完題目後,決定寫的順序是 ABDFG。開始的時候就有點想上廁所,寫完 A 就趕快去上(還上太久被工作人員關心),回來寫 B。B 我一開始的作法(程式碼)是做法向量,然後用外積找線段交點的方式找投影點,但只有 30 分,稍微想了一下覺得沒寫錯,應該是卡精度,就決定先放著,待會再回來寫。

接下來快快地寫掉 D 後,F 推了一下 DP 式, 現在到第 個城市且有賣東西、已經賣了 個需要的最少花費,注意題目限制裡的水果數量不多,所以這樣狀態數是好的,轉移的時候枚舉下一次要在哪裡賣,搭配一下前綴和可以做到 城市數)轉移。

F 和 G 都順利地一次 AC,現在時間已經過了兩個多小時,趕快回去寫 B,我換了一個作法,是直接用內積找投影點,傳上去 60 分,我再改了一下換成精度高一點的作法才過。

過半場,目前 500 分,接著就交替想了各個題目,C 還是沒有想法,E 有想到 18 分子題可以用線段樹做,但很麻煩所以先不寫,H 看起來還是好難所以我還是沒想,我決定稍微想一下 I,畢竟至少子題應該可做,然後就發現,啊,這不是水題嗎。

我的 DP 式長這樣: 表示考慮前 個 column,第 個 column 的軌道是平的開始、斜的開始還是平的結束(斜的結束直接視為是新軌道斜的開始)的方法數,轉移式:

因為我發現可以 DP 後就想到是要線性遞迴,所以就推了線性遞迴的式子,有些人的不能。先傳一次確定正確性後,寫了矩陣快速冪,然後 AC。

這個時候已經快三個半小時,目前 600 分,心想大概是剩下三題決勝負了,去把 E 的 19 分和 H 的暴力寫掉,然後就交替想 C 跟 E。為什麼我不想 H 呢?好問題,我也想知道。

四個多小時的時候,當我正想開寫 E 的 18 分,我忽然通靈到,C 有正環(其實非負環就好)的話,這個環肯定有至少一個節點能當起點,花了點時間想證明但想不出來,但反例也構不出來,就決定放手一搏,畢竟這個 100 分比 18 分多很多。

因為前陣子教讀書會有教怎麼用 Bellman-ford 找正環,雖然一時想不起來怎麼證明的,但還是勇敢地寫下去。我那個時候好像以為範圍到 所以用了 SPFA,反正差不多。

找完正環後下一個問題是要判斷哪些節點可以當起點,因為時間快不夠了,所以我本來打算直接寫滿分解,然後發現我本來的想法是爛的,只好先寫部份分,至少確定正確性。很幸運地一次過了(如果你看計分板發現我傳了兩次,第一次是我要傳 D 傳錯題),這個時候是 4:56,過的那一瞬間我又想到很好寫的滿分解的寫法,但還是來不及在結束前寫完。

總結

結束後我在紙上算了一下分數, 是……,好,來問其他人分數吧。然後 shaun 就跟我講我的分數其實是 XD。

可以拿手機後我急著去和已經開手機的人要計分板看,本來估我應該第 6 名左右,結果……

總分 667,rank 4。

幹,又是第四名。

而且 H 還一堆人 AC,我看到計分板後想十秒就想到怎麼做了 = =。只要我賽中有任何一刻好好去想 H 怎麼做,應該就想得出來了,直接浪費 85 分。

這次最大的敗筆應該是在 C 浪費太多時間,沒寫題的時候我其實大部分都在想 C,因為我覺得既然放在第三題,那應該不難(賽後發現題目是照名稱排序的,只是剛好前兩題比較簡單),而且看起來真的沒很難。

再加上我最後那個通靈其實跟前面想的都沒關係,所以如果我把前面想 C 的時間拿一點去 H,那我的分數也至少會有 700 分,再加最後如果 C 有寫出來就 800 分了。

最大的敗筆應該是我一直都假設 C 是簡單題而且不想 H,可能是因為 H 看起來像那種很經典的題目,我每次遇到都不會寫的那種,我真的好爛 = =。