[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制的題目了。