竞赛中常见的影响速度的几点

在很多情况下，题目有思路但是会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
2
3
4
5
6
7
int main() {
 char s[20];
 cin >> s;
 int n;
 scanf(s, &n);
 cout << n << endl;
}

endl

endl在使用时不仅仅是换行，还会清空缓冲区，速度上可能比”\n”换行慢了10倍。

所以大家完全可以加上

1
#define endl "\n"

03/02优化

如果代码中有stl的话，请一定加上下面这段代码，开启O3优化。

1
#pragma GCC optimize(3)

原理的话举例如下所示

1
2
3
4
5
6
7
int main()
{
    int sum=0;
    for(int i=0;i<=1000;i++)
        sum+=i;
    return sum;
}

编译器在编译时就帮你算出了一些值。

可以简单的理解为，开了优化，编译器就会延长编译的时间来进行优化，使得程序的运行时间尽可能的短。

vector的push_back()

vector的push_back()虽然是均摊的O(1),但是当数据量大的时候会很慢。所以如果需要使用的话。可以

1
2
3
4
5
6
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，还有随机读取的能力。但是常数会大一点。

unordered_map/set

如果只是使用一个映射关系的话，不需要有序的话，可以尝试unordered_map，基本上快一倍

inline/register

这个东西在开启了O3优化后基本上编译器都帮你干了，所以在此不再说明

const int mod

不加const的话，取模会慢很多，但是开O3后，编译器会帮你手动优化

结构体线段树

有两种写线段树的方法，一种是数组，另一种是包在结构体里面

1
2
3
4
5
struct node{
int sum,lz;
}tree[MAXN<<2];
int sum[MAXN<<2];
int lz[MAXN<<2];

存图的方式

经过测试，vector和链式前向星的速度

vector跑了0.0488s，链式前向星跑了0.0224s，明显是链式前向星快一些