[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 + 最大主元法可以过。