卡常技巧

本文最后更新于：2023年4月26日 晚上

分数可能是不支持的，所以用了另一种方法表示

卡时间

预处理指令和编译

O2

请注意， O2 有时会使代码出现错误。

O2 是最常见的一种优化，基本来说有两种使用方式，第一种是在编译时加上-O2选项，例如编译a.cpp时，使用 O2 。

1
g++ a.cpp -o a.exe -O2

即可。

第二种方法是在预处理指令中添加 O2 ，即在代码首行添加如下指令：

1
#pragma GCC optimize(2)

火车头

火车头也是 C++ 中一种比较常见的优化方式，基本应用于离线评测。

火车头比较长，就不一个一个解释了，直接放代码。

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

位运算

关于位运算，如果想了解得更详细，可以看一下https://www.luogu.com.cn/blog/2021wuyueyang/qian-tan-wei-yun-suan1和https://www.luogu.com.cn/blog/2021wuyueyang/qian-tan-wei-yun-suan2

定义

位运算就是直接对整数在内存中的二进制位进行操作。

对乘法、除法的加速

首先了解a>>x等价于 \(a/(2^{x})\) 和a<<x等价于 \(a \times 2^{x}\) 。

于是我们可以在一些除法、乘法计算量比较大的题目中使用位运算加速。

例如以下题目：

给你 $ n (n ^{5}) $ 个数，进行 $ m (m ^{3}) $ 次操作，每次操作会让每个数乘上 \(2^{x}\) ， \(x\) 输入 ，保证不会溢出。

相信大多数 OIer 都能写出以下代码：

1
2
3
4
5
6
7
8
9
for(int i=1;i<=m;++i) {
    scanf("%d",&x);
    int p=pow(2,x);//pow是快速幂
    for(int j=1;j<=n;++j) {
        a[j]*=x;
        printf("%d ",a[j]);
    }
    printf("\n");
}

但是这种算法效率不佳，于是我们可以做一些优化，如下：

1
2
3
4
5
6
7
8
for(int i=1;i<=m;++i) {
    scanf("%d",&x);
    for(int j=1;j<=n;++j) {
        a[j]<<=x;
        printf("%d ",a[j]);
    }
    printf("\n");
}

其效率远远高于前一种算法，同时可以使代码简洁一些。

数据类型

这也是一种很常见的优化。

众所周知， long long 的运算效率是 int 的 \(1/2\) ，所以在可以不用 long long 的时候就不用 long long 。

比如在一道中间过程计算都是 int ，但输出结果是 long long 的题目中，我们可以在最后结果的计算时再使用 long long ，注意1ll*。

IO 效率

普通快读快写

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
bool _u(char c) {
    return ((c<='9' && c>='0') || c=='-');
}

template <typename T> void read(T &a) {
    a=0;
    T flg=1;
    char c;
    while(!_u(c=getchar())) ;
    if(c=='-') flg=-1,c=getchar();
    a=c-'0';
    while((c=getchar())!='-' && _u(c)) a=a*10+c-'0';a*=flg;
}

template <typename T> void write(T a) {
    char s[45]={};
    int cnt=0;
    if(a<0) putchar('-'),a=-a;
    if(a==0) {
        putchar('0');
        return ;
    }
    while(a) s[++cnt]=a%10+48,a/=10;
    while(cnt) putchar(s[cnt--]);
}

手写带 template 的快读快写有一个优势，就是可以输入输出 __int128 。

fread

这种一般不建议使用，借鉴了一位大佬的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int BUF_SIZE=1<<15;
char buf[BUF_SIZE],*p1=buf,*p2=buf;
char duf[BUF_SIZE],*q1=duf;
static int sum,fl,sk[20],pos;
static char c;
namespace ae86{
    inline char gc(){return(p1==p2&&(p2=(p1=buf)+fread(buf,1,BUF_SIZE,stdin),p1==p2)?EOF:*p1++);}
    inline void pc(char c){q1-duf==BUF_SIZE?fwrite(duf,1,BUF_SIZE,stdout),q1=duf,*q1++=c:*q1++=c;}
    inline int rd(){
        sum=0,fl=1;c=gc();
        while(c<'0' || c>'9'){if(c=='-')fl=-1;c=gc();}
        while(c>='0' && c<='9'){sum=sum*10+c-'0';c=gc();}
        return sum*fl;
    }  
    inline void wt(int x){
        q1=duf;pos=1;
        if(x<0){pc('-');x=-x;}
        do{sk[pos++]=x%10;x/=10;}
        while(x);
        while(--pos)pc(sk[pos]+'0');
        fwrite(duf,1,q1-duf,stdout);
    }
}using namespace ae86;

卡空间

bitset

bool 类型是 C++ 中占用空间最小的数据类型，它只能表示 true 或 false ，但是占用空间仍然是 \(1\) 字节，有没有更好的储存方法呢？

这时， bitset 就出现了。

bitset 可以用一个字节表示 \(8\) 个 true 或 false ，但只能和 bitset 进行位运算 ， fread 里面貌似应用了 bitset 。

关于 bitset 的更多内容这里不细讲，可以参考 OI-wiki 的 bitset

算法
#常数优化
卡常技巧
https://blog.shuger.ml/constant/
作者
_Shu
发布于
2022年8月24日
许可协议