OI程序优化指南

输入输出

1.cin/cout关闭同步流

cin 和 cout效率低的原因是，c++默认 cin`与stdin保持同步，cin会把要输出的东西先存入缓冲区，进而消耗时间。如果我们关闭了同步，cin/cout也会变得很快。

注意：关闭同步流后一定不要使用printf scanf，pus，getchar等其它输入输出流，会出错的！

关闭同步流代码

1
2
ios::sync_with_stdio(false),ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0)

2. 换行不要用endl

c++里，每次使用endl都会清空缓冲区，这会浪费很多时间，建议使用'\n'的方式。

解决方案

1
#define endl '\n'

3. 换用stdio

在某些评测机上，即使关闭了同步流，也没有printf和scanf快，所以还是养成C风格输入输出的好习惯吧！

1
2
printf("%d\n",a);
scanf("%d",&a);

4. 快读快写

在输入输出的领域里，快读快写才是王者！

以下是我常用的快读快写板子。

快读

1
2
3
4
5
6
7
8
9
10
11
inline int read(){
	int x=0,y=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') y=-1,c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^48),c=getchar();
	}
	return x*y;
}

快写

1
2
3
4
5
6
7
void write(int x){
	if(x<0) putchar('-'),x=-x,write(x);
	else{
		if(x>9)	qwrite(x/10);
		putchar(x%10+'0');
	}
}

编译器优化

5. 使用inline

inline叫做内联函数，在c++里有些函数经常调用且不复杂，在这种函数前加上inline，作用相当于宏定义。

如

1
2
3
inline int sum(int a,int b){
	return a+b;
}

相当于

1
#define sum((a),(b)) (a)+(b)

注意：对于一些复杂函数（尤其是递归函数），inline没有一点优化作用（编译器不会给你优化）

6. O2优化

这个绝对是耳熟能详的了，O2优化能减少运行时间，尤其是对STL的优化非常大。

1
#pragma GCC optimize(2)

把这行代码放到程序最前面即可。

7. 火车头优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)

8. 宏定义

宏定义就是在编译时把代码中的片段替换，如

1
#define main mian

就是把程序中所有的main换成mian。

宏定义一般用来缩短代码量，如

1
#define FR(i,l,r) for(int i=(l);i<=(r);i++)

如果有一个几重的for循环嵌套，用宏定义就会减少很多代码量。

宏定义有时用来偷懒，如

1
#define int long long

这行代码会把程序中所有int换成long long，但是也会把int main()换成long long main()

所以我们需要改动一下。

1
2
3
signed main(){
	return 0;
}

这样就不会CE了。

其它优化（不会归类了）

9. 使用register

register表示把变量放在寄存器里，一般用于变量经常使用的情况下（如循环变量）

实例

1
for(register int i=1;i<=n;i++)

如果程序里循环特别多，有时能优化三分之一的时间

10. 直接赋值

1
int a(1);

正常的int a=1是先定义变量a，再给a赋值1。而int a(1)这种写法是在定义变量时就把1放进变量里了，所以会快一些。

注意，这种写法只能在定义时使用。

11. 三目运算符

三目运算符通常比ifelse要快（我也不知道为什么），而且代码也短一些。

如

1
2
3
4
int max(int a,int b){
	if(a>b) return a;
	return b;
}

用三目运算符就会写成

1
2
3
int max(int a,int b){
    return a>b?a:b;
}

12. 不用库函数

众所周知，c++给的库函数都很慢，有时为了极限卡常就会自己写一些简单的库函数。

如取最大值

1
2
3
inline int myMax(int a,int b){
	return b&((a-b)>>31)|a&(~(a-b)>>31);
}

取模

1
2
3
inline int myMod(int a,int b){
	return a-(a/b)*b;
}

13. 位运算

关于乘除2的操作一般用左移右移代替。

如线段树中的

1
tr[x].sum=tr[x*2].sum+tr[x*2+1].sum;

可以写成

1
tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;

如线段树开四倍空间一般直接写成

1
node tr[N<<2];

14. 一些语法糖

以下的语法糖大多是c++11或c++14中出现的，请放心使用（ccf让用）

结构体赋值

假如有一个结构体

1
2
3
4
struct node{
	int a,b,c;
};
node d;

我们可以直接这样赋值

1
d={a,b,c};

auto妙用

auto可以自动推断类型，一些难写的stl容器的迭代器都可以用auto代替

1
for(auto it=v.begin();it!=v.end();it++);

比如很难写的set迭代器就可以这样用：

1
2
auto it=s.lower_bound(k);
cout<<*(--it);

甚至auto可以这样用

1
2
3
for(auto it:v) cout<<it<<endl;//直接迭代一个容器
//注意，这样写的it不能赋值，如果想赋值得这样写
//for(auto &it:v)

不是stl容器也可以这么用，甚至是

1
for(auto it:{&x,&y,&z}) cout<<*it<<" ";

大括号传参

从@qidirj那里听到的有趣语法。

如要取x,y,z三数中的最大值，正常是这样写的：

1
cout<<max(x,max(y,z));

在c++14后可以这样写

1
cout<<max({x,y,z});

很神奇……

#程序优化
OI程序优化指南
http://luhaoren.xyz/2023/08/02/OI程序优化指南/
作者
luhaoren
发布于
2023年8月2日
许可协议