2016.9.20图论考试总结

今日试题

今天的题目全是原题,我的图论还是可以的,写对了两道题。

然而大家的图论都很好,尤其是我出现了小小的失误,结局很悲惨……209,rank7。

全是些送肉的大原题……我原来都考过。

但是我的图论算法,尤其是tarjan实在是太不熟练了,考场上写得很慢。

第一题就是平面图转对偶图dijkstra,这道题我30分钟就写A了。

第二题tarjan缩点然后做拓扑序DP,写完了发现我的tarjan模板是个错的,然后左想右想才想清楚,写完了发现又有些奇葩错误,一直写了2个半小时这才AC。正是由于这道题时间花的太久,第三题没时间想了。

第三题是个贪心,但是边界情况超级多,很多trick点,难得想到。

更重要的是,我写的时候在i做循环变量的循环里再次用i循环,简直做大死!!!

最后的结果是跪烂……半小时写完后只有十几分钟了,没发现这个错误,最后只有9分。

事实上我还没有判断次大和次次大,还有一个块内的直径,结果就算是改过来了也只有几十分……

还有一些什么dep数组不清空啦之类的,最后都跪烂了……

总而言之,图论的算法一定要再打几遍模板,考场要合理安排时间,切不可在一道题上花费太多时间。

图论不能只看不写,一定要亲自写,亲自拍,亲自交,不能松懈。

就是这样了……

不如来评论一发?