[OI] 卡常宝典

FastLower

卡常宝典

注：全文中的排序规则按效率从高到低，

部分资料来源于网络。

一、I/O 优化

1.输入：

fread > read> cin.tie(0) > scanf =cin.ios::sync_with_stdio(0)> cin

2.输出：

fputs > puts > cout.tie(0) ≈ printf > cout

\n > endl

二、常量与宏定义

1.规范性：

C++11及以后规定：

只读 -> const

常量 -> constexpr

2.效率：

define > 常量 > 只读量 ≈ 普通变量

三、数据类型

int > short > long long

float > double

bitset > bool

四、三目运算符 ＞ switch-case> if-else

注：对比条件数目大于3时switch更优，并且对比条件数目越多时switch的优势越为明显。

五、位运算（更快）

1.   取模 → &

2.   乘 → <<

3.   除 → >>

4.   != → ^

5.   swap(a,b) → a^=b

六、提高缓存命中率（内存接近）

说人话就是令指针走的“步数”少一些，比如：

++a[1], ++a[2] > ++a[1],++a[100001]

显然，我们不可能告诉机器硬件是否需要清空并重新填充内存。

但我们可以尽可能减少访问缓存器外的元素。

比如在一段很长的循环中，只用为数不多的变量。

这样一来，就达到了提高命中率的目的。

七、自加自减

++i > i++，特别是在STL中，优势肉眼可见。

八、size()与empty()

1.   size() 用于普通队列更快。

2.   empty() 用于优先队列更快。

九、循环展开

这个比较神奇。

比如说一个程序，原本时间复杂度是O(n^2)，

但是如果你用一些高科技（如循环展开）也许能够跑完3*10^4 的数据！

例如：

for(int i=1;i<=n;i++)
{
        sum+=i;
}

未优化，耗时0.0000279秒。

for(int i=1;i<=n;i+=2)
{
        sum+=i;
        sum+=i+1;
}

初步优化，耗时0.0000159秒，将近快了一倍。

for(int i=1;i<=n;i+=2)
{
        sum1+=i;
        sum2+=i+1;
}
sum=sum1+sum2;

再次优化，耗时0.0000073秒，将近又快了一倍。

十、O1 O2 O3优化（简称：吸氧）

口诀：

臭氧氧气氧原子，

一口吸死评测机。

#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")