狗狗昂赛 & 八九十月面经总结

肥宅快乐水 发表于 2018-11-2 10:03
贼牛逼， 感觉你是稳的。

n很大这个可能跟蓄水池方法有点像么。。

对对对就是蓄水池
我又忘记说了  矩形也是平行坐标轴的  计算距离简单很多

[hide=180]

请问楼主多久知道onsite结果的？～～

5.3是找shortest path还是longest path呀？spfa第一次听说，是shortest path faster algorithm吗？是和https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm算法一样的吗？
longest path好像可以用topology sort：https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

秋天和你 发表于 2018-11-2 11:18
请问楼主多久知道onsite结果的？～～

不到十天送的HC，hc当天下午通知过了

当当当 发表于 2018-11-2 11:32
5.3是找shortest path还是longest path呀？spfa第一次听说，是shortest path faster algorithm吗？是和http ...

longest，所以有环就不行。
可以用任何求最短路的方法，spfa只是其中一种。

当当当 发表于 2018-11-2 11:32
5.3是找shortest path还是longest path呀？spfa第一次听说，是shortest path faster algorithm吗？是和http ...

最长最短都一样，把边变成-1就是最短路了

非常感谢您的分享，这是很好的信息

第一题lz用DP做，是把整个三角形都求出来吗？如果用递归+memorization会不会省一些时间？谢谢lz！

iverson1122 发表于 2018-11-3 01:36
第一题lz用DP做，是把整个三角形都求出来吗？如果用递归+memorization会不会省一些时间？谢谢lz！

是的。
递归应该能省时间，然而费空间。