存档

文章标签 ‘NOCOW’

USACO The Clocks|BFS

2010年12月1日 3 条评论

The Clocks一题看完之后第一个想到的就是BFS(其实很有多方法可以解决,有兴趣可以去参考参考NOCOW的解题代码)。对于这样的BFS,我都是定义结构体来作为节点,像本题中使用一个state字符串来记录当前的状态,然后最开始用了一个vector来记录已经出现过的状态,结果在提交的时候悲剧的TLE了。
于是各种加优化,想了想,中间产生大量状态,然后每次都从头到尾的搜索vector效率是低了点(对于vector来说,全局的find函数是O(N)的复杂度),于是改用map,map排序了,复杂度O[......]

继续阅读

分类: USACO题解 标签: , , , , ,