竞赛中常见的影响速度的几点
在很多情况下,题目有思路但是会TLE,基本上都是卡输入输出,故在此总结一下,影响程序运行速度,不过建立在时间复杂度正确的情况下。
cin/cout 解绑
这是一个初学者基本上都会遇到的坑,原生的cin/cout的速度非常慢,因为要和scanf/printf进行同步,所以需要加上。
1 | std::ios::sync_with_stdio(false);std::cin.tie(0); |
注意解绑后,不能再使用scanf和printf,以及getchar
解绑后的cin/cout的速度比scanf快,cin输入的数据类型在编译时期就会确定,而scanf则是在运行时解析字符串,即以下代码
1 | int main() { |
endl
endl在使用时不仅仅是换行,还会清空缓冲区,速度上可能比”\n”换行慢了10倍。
所以大家完全可以加上
1 |
03/02优化
如果代码中有stl的话,请一定加上下面这段代码,开启O3优化。
1 |
原理的话举例如下所示
1 | int main() |
编译器在编译时就帮你算出了一些值。
可以简单的理解为,开了优化,编译器就会延长编译的时间来进行优化,使得程序的运行时间尽可能的短。
vector的push_back()
vector的push_back()虽然是均摊的O(1),但是当数据量大的时候会很慢。所以如果需要使用的话。可以
1 | signed main(){ |
除此之外,还有一个stl叫deque,可以前push/pop,后push/pop,还有随机读取的能力。但是常数会大一点。
unordered_map/set
如果只是使用一个映射关系的话,不需要有序的话,可以尝试unordered_map,基本上快一倍
inline/register
这个东西在开启了O3优化后基本上编译器都帮你干了,所以在此不再说明
const int mod
不加const的话,取模会慢很多,但是开O3后,编译器会帮你手动优化
结构体线段树
有两种写线段树的方法,一种是数组,另一种是包在结构体里面
1 | struct node{ |
存图的方式
经过测试,vector和链式前向星的速度
vector跑了0.0488s,链式前向星跑了0.0224s,明显是链式前向星快一些