[Solution] Tokyo 2007
And Then There Was One
經典題,遞推。
Prime Gap
簡單題
Minimal Backgammon
DP
Lowest Pyramid
比較麻煩的題目,大體做法是枚舉一個點,根據距離相等可以枚舉另一個點(這些點很少了),然后確定下最后一個點,check.
Geometric Map
比較麻煩的預處理 + dijstra
Slim Span
經典問題了,按邊大小排序,每次加一條邊,如果形成環去掉環上最小的邊。check
The Morning after Halloween
BFS,最后用A*過掉的。用max(當前位置到目標位置)估價
Bug Hunt
簡單模擬
Most Distant Point from the Sea
可以用二分+半平面交。
但也可以想象所有邊朝里面擠壓,這樣最后要么是兩條邊壓到一起,要么三條邊壓成一個點。O(n^3)枚舉。
The Teacher's Side of Math
注意到p,q都是質數,所以答案是0必須是所有其他項系數全為0,這樣就可以解方程了。
用long double + 最大主元法可以過。