[Virtual] APIO 2021

2021-05-25

在打之前預估不會拿到太多分，所以決定在上課時間寫（反正現在是上網課），自己覺得應該都還不會，所以有點沒那麼認真在寫（即使認真我還是寫不出來啦）。

以下有雷，請不想被爆雷的人跳過整段

看完題目了，簡單來說就是， hexagon 就是凸六邊形面積 + 距離的問題，子題 1、2 拿到了但子題 3 的 BFS 不會實作。

jumps 就是點出度最多是 2 的 DAG，求一群連續的點到另一群連續的點的最短路（不帶權），感覺最可做，但是還在想。

roads 有點難，子題 2 是簡單的DP，可能是某種圖論問題，光題目本身沒觀察到什麼。

現在沒想法，有點在乾燒。

花了好久才拿到那 7 分，debug 有夠久，下次 debug 一定要好好本機編譯 grader了 ;w;，但是 jumps 還是沒有想法，有點想砸二維線段樹但不知道要怎麼做。

jumps 砸了 Floyd-Warshall 去做，但我想 BFS 可能會更好，其他題都在乾燒，我真的好爛喔 ;w;

BFS 一發拿下了，大概就沒想法了，目前的目標就是盡量撈奇怪的子題就好。

以上都是賽中稍微紀錄，賽後我再重新整理的。

賽後發現 hexagon $B=0$ 的 case 我的想法其實對了，只是差一點點，然後 jumps BFS 可以多做 $Q=5$ 這個子題， roads 也可以用樹 DP 去做，這樣總分加起來是有機會銅的，

然後賽中一直耍智障沒有處理 overflow，導致花了不少時間。

感覺上其實我會的東西不需要多太多，就可以拿到還可以看的成績， Score: 9/25/12 真的很爛，之後要好好接觸 OI 制的題目了。