总结ACM竞赛中常见的影响运行速度的几点
转载声明：本文转自知乎，已经过作者同意转载。
前一场的codeforces的D题有很多人反应思路差不多但是会TLE，基本上都是卡输入输出了，所以这里就在这里总结一下，有哪些会影响程序的运行速度。不过这是建立在你的时间复杂度是正确的情况下。
cin/cout 解绑
这是一个初学者基本上都会遇到的坑，原生的cin/cout的速度非常慢，因为要和scanf/printf进行同步。
所以需要加上。
std::ios::sync_with_stdio(false);std::cin.tie(0);注意解绑后，不能使用scanf和printf了，快读也是不可以的，因为快读的getchar也是C语言里面的。
解绑后的cin/cout的速度是比scanf要快的，cin输入的数据类型是在编译时期就会确定的，而scanf则是在运行时解析字符串。也就是你可以写出这样的代码。
int main() {
char s[20];
cin >> s;
int n;
scanf(s, &n);
cout << n << endl;
}endl
endl在使用的时候不仅仅是换行，还会清空缓冲区。速度上可能比"\n"换行慢了10倍。
所以大家完全可以加上
#define endl "\n"O3/O2优化
如果你的代码里有stl的话，请一定加上这句话，开启O3优化。
#pragma GCC optimize(3)不过一般的OJ都是默认开启的，洛谷需要手动点一下。只要记住一直带着O3优化就可以了。
原理的话我可以举个例子。
比如这段代码。
不开优化的汇编是这样的
而我们只需要加上O3优化
汇编就变成了这样
编译器在编译的时候就帮你算出了一些值。
可以简单的理解为，开了优化，编译器就会延长编译的时间来进行优化，使得程序的运行时间尽可能的短。
不过比赛的时候基本上都会开上优化的。还有一些特殊的情况，据说由于开了O3后生成的汇编指令太多导致速度变慢，但是我没有遇到过。大部分的比赛都是开的O2优化。
vector的push_back()
vector的push_back()虽然是均摊的O(1)，但是当数据量大的时候会很慢。所以如果需要使用的话。可以
signed main() {
cin >> n;
vector<int>v(n + 1);
for (int i = 1; i <= n; i++)cin >> v[i];
}还有一个stl叫deque，可以前push/pop，后push/pop ，还有随机读取的能力。但是常数会大一点。
来源:STL容器 vector,list,deque 性能比较 - sailing - C++博客(http://www.cppblog.com/sailing/articles/161659.html)
不过这个测试好像没有开优化，所以会出现vector比数组慢很多。我本地开优化测试跑的速度为
数组0.2185s vector 0.4057s 不会出现数量级的差距。
unordered_map / set
如何你只是需要一个映射关系的话，不需要有序的话，可以尝试unordered_map。看了一些测试数据，基本上快了一倍吧。
inline/register
这个东西在开启了O3优化后基本上编译器都帮你干了。所以可以不用说了。
#define int long long
很多人觉得这个会影响速度，但其实看过一些测试数据后你会就发现int 和 long long 的速度差不多的。
C++ 基本计算的速度 | 小灰灰灰灰的博客(https://blog.lyh543.cn/2019/08/20/cpp-calculating-efficiency/)
但是浮点数就慢很多了，大概差一个数量级。
当然long long 在取模除法的时候就会明显慢于int，所以需要看情况来使用。
这个地方可能比较迷惑，所以我自己也测试了一下。
测试代码如下
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int rd() {
return rand()*rand();
}
signed main() {
int re = 0;
double res = 0;
for (int cnt = 1; cnt <= 10; cnt++) {
clock_t start, end;
start = clock();
int s = 0;
for (int i = 1; i <= 10000000; i++) {
s += i;//累加
s += rd();//加随机数
s = max(s, rd());// 判断
s = rd() / i;//除法
s = rd() % rand();//取模
s += (rd() % i + i + max(rd(), rd()) % 114514 + i + i + i + i / 114 + i * 514) % 114514;//混合
}
end = clock();
res += (double)(end - start) / CLOCKS_PER_SEC;
re = s ^ re;
}
cout << res / 10 << endl;
return re;
}
也就是说当代码中已有简单的运算的时候，define int long long 的影响很少。
但是如果是有很多取模运算的时候，就要考虑一下了。
const int mod
不加const的话，取模会慢很多的。我当初百度之星有一道斯特林数的题就是因为没有加const导致T了好几发。
但是开了O3后，编译器会帮你手动优化的。
结构体线段树
有两种写线段树的方法，一种是数组，另一种是包结构体里面。
struct node {
int sum, lz;
}tree[MAXN << 2];
int sum[MAXN << 2];
int lz[MAXN << 2];理论上第一个cache命中率高一些，我用洛谷上的线段树模板题尝试过，快不了多少其实。
不过用结构体写可以用代码补全（确信
存图的方式
我测试了一下vector和链式前向星的速度。
vector跑了0.0488s ，链式前向星跑了 0.0224s ，明显是链式快一些。
云剪贴板 - 洛谷(https://www.luogu.com.cn/paste/ov0xs40u) 代码这里
数据是使用洛谷的数据生成器生成的一棵50000个节点的树，其中40%的节点呈现链状，35%的节点呈现菊花图状，剩余25%的节点随机加入。
总结，基本上就是开了优化后，加上解绑和"\n"能解决大部分的问题。
当然某些毒瘤题目除外。
