关于『卡常』
更快、更高、更强——更团结。
fa
s
t
e
r
,
h
i
g
h
e
r
,
s
t
r
o
n
g
e
r
a
n
d
t
o
g
e
t
h
e
r
.
\tt faster,higher,stronger \ and \ together.
f
a
s
t
e
r
,
h
i
g
h
e
r
,
s
t
r
o
n
g
e
r
a
n
d
t
o
g
e
t
h
e
r
.
怎样更快？
在程序设计中，往往会寻求代码的运行速度。
当你面对
T
L
E
\tt TLE
T
L
E
的残酷现实却不愿承认自己的算法有问题时，卡常是一个很好的办法。
卡常又称卡常数、底层常数优化，是
O
I
\tt OI
O
I
中一种针对程序基本操作进行空间或时间上优化的行为。
1.快读 & 快写
总所周知，字符输入输出比标准输入输出快的很。
快读和快写就是运用了这个原理。
快写模板（循环）：
template <typename T>
void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while(!isdigit(ch)) { //isdigit在<cctype>中
if (ch == '-') {
f = -1;
}
ch = getchar();
}
while(isdigit(ch)) {
x = x * 10 + (ch - 48);
ch = getchar();
}
x *= f;
return;
}
用法：
read(x); //输入并赋值
快写（递归）：
template <typename T>
void write(T x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
return;
}
用法：
write(x); //输出
2.位运算
能用位运算就用。
在乘除运算上，最好用左移和右移代替。
2 * 2
可写成
2 << 1
,
2 * 10
可写成
(2 << 1) + (2 << 3)
。
90 / 2
可写成
90 >> 1
,
128 / 16
可写成
128 >> 4
。
小知识：
|
位运算符号 |
位运算关键字版符号 |
|---|---|
|
|
| ` | ` |
|
|
|
|
|
|
| ` | =` |
|
|
位运算的其他应用：
1）代替模运算
17 % 2
可写成
17 & 1
，
45 % 4
可写成
45 & 3
,
986 % 16
可写成
986 & 15
。
2）快速幂
快速幂模板：
int qk_pow(int x, int n){
if(n == 0) {
return 1;
}
int t = 1;
while(n) {
if(n & 1) { //用&代替%
t *= x;
}
n >>= 1; //用>>代替*
x *= x;
}
return t;
}
3）Swap函数
void Swap(int &a, int &b) {
a ^= b ^= a ^= b;
return;
}
这个代码很妙，可以细细品味。
3.inline
在声明函数之前写上
i
n
l
i
n
e
\tt inline
i
n
l
i
n
e
，可以加快一下函数调用，但只能用于一些操作简单、调用频繁的函数。涉及递归，大号的循环等很复杂的函数，编译器会自动忽略
i
n
l
i
n
e
\tt inline
i
n
l
i
n
e
。
如快读函数可写成：
template <typename T>
inline void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while(!isdigit(ch)) {
if (ch == '-') {
f = -1;
}
ch = getchar();
}
while(isdigit(ch)) {
x = x * 10 + (ch - 48);
ch = getchar();
}
x *= f;
return;
}
但有时
i
n
l
i
n
e
\tt inline
i
n
l
i
n
e
会被忽略。
4.寄存器
假如你要拿个钥匙，一个在你裤兜里，一个在你车上，你拿哪一个？
就近原则。
从距离上来说，内存条相较于寄存器来说离
C
P
U
\tt CPU
C
P
U
更远。
在时间相等的情况下，时间与路程成正比。
从工作原理上来说，寄存器的工作原理比内存简单的多。
综上，寄存器与内存之间具有差异，但差异不大。因此利用寄存器来提高访问速度往往运用与经常被访问的变量。
例如：
for(register int i = 1; i <= 1000000000; i ++)
register
关键字表示将变量
i
存于寄存器中。代码中变量
i
将被访问
1000000000
\tt 1000000000
1
0
0
0
0
0
0
0
0
0
次，每一次访问都节省若干时间，乘上
1000000000
\tt 1000000000
1
0
0
0
0
0
0
0
0
0
便不可忽略。在这个代码中优化后会快
1.5
sec
→
1.7
sec
\tt 1.5 \sec \to 1.7 \sec
1
.
5
sec
→
1
.
7
sec
。
5.三目运算符
i
f
e
l
s
e
\tt if \ else
i
f
e
l
s
e
的汇编代码：
而三目运算符的汇编代码：
相较于
i
f
e
l
s
e
\tt if \ else
i
f
e
l
s
e
语句，三目运算符的汇编指令更短。
在少量的运行中，二者的区别微乎其微。
但运行次数庞大时， 三目运算符的优势便显现出来。
如
M
i
n
\tt Min
M
i
n
函数
int Min(int a, int b) {
return a > b ? a : b;
}
问号前是判断条件，如为真则执行冒号前的语句，否则执行冒号后的语句。
6.常数的声明
尽量将常数声明成常量。
如：
const int mod = 100000007;
比
int mod = 100000007;
要快。
7.#pragma 指令
经常提到
O
2
\tt O2
O
2
这一说法，它的实现为：
#pragma GCC optimize(2)
当然还有
O
1
、
O
3
、
O
s
\tt O1、O3、Os
O
1
、
O
3
、
O
s
。
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(s)
还有一堆：
#pragma GCC optimize(3)
#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")
重点：开个O2就行了，欲速则不达。（指令集开多了会有负面作用）
8.一些奇奇怪怪的卡常小知识
后置 ++ 需要保存临时变量以返回之前的值，在 STL 中非常慢。事实上，int 的后置 ++ 在实测中也比前置 ++ 慢 0.5 倍左右。
逗号比分号要快（神奇）。
b
o
o
l
\tt bool
b
o
o
l
很慢，尽量开
i
n
t
\tt int
i
n
t
（疑惑）。
一些卡常在正规比赛中
禁用
。
“行了，你已经是世界上最快的
男人
OI
\tt OI
O
I
选手了。”