USACO:Arithmetic Progressions的一些体会

来源:互联网 时间:1970-01-01

此题在算法上没有什么好说的,就是暴力搜索,但是这个题目给我很深的印象,来自于其中的细节把握。因为简单的暴力搜索无法满足时间要求,所以需要在此基础上进行一些细节的改良,现在把我的做题体会总结一下:

1.对于其中搜索等差项范围的优化,我感觉是最直接有效的,通过给定的长度N判断从而缩小搜索的范围,可以将时间缩小到原来的1/N;

2.依然是搜索的优化,搜索算法也很关键。如果线性的搜索,依然难以通过。这里提供几个思路:位图法(O(1)),类似计数排序搜索(O(1),比较占空间,但此题可以尝试),使用set类型(O(lgn),未尝试,估计可以)。

3.其他细节的优化,例如减少赋值操作等,这里特别提一点:关于函数参数的传递方式。对于内置类型等采用值传递就可以,对于vector等类型,尤其是当其元素数量巨大的时候一定记住选择引用传递,避免复制,可以有效的减少时间,在这个题目中我体会的很深。一开始我采用值传递vector,Test 6都没有通过,后来只是将值传递改为引用传递,程序就跑完了所有的9个Test。真是令我目瞪口呆,可见参数的传递方式对于大数据量的参数传递效率的影响尤为明显。


相关阅读:
Top