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 看起來像那種很經典的題目，我每次遇到都不會寫的那種，我真的好爛 = =。