存档

文章标签 ‘TLE’

USACO Arithmetic Progressions

2010年12月3日 4 条评论

Arithmetic Progressions题目大概意思:一个等差数列是一个能表示成a, a+b, a+2b,…, a+nb (n=0,1,2,3,…)的数列。在这个问题中a是一个非负的整数,b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p^2+q^2的数的集合)S中长度为n的等差数列。
这个题目拿到手感觉只能暴力搜索,事实便是如此。而且题目给了5秒钟的时限,于是我就开始写搜索了。提交之后在中间某一组数据果断超时了。实在想不到该怎么优化。后来看了[......]

继续阅读

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

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题解 标签: , , , , ,