如果您喜欢我的创作，可以赞助我。您的支持将帮助我继续创作更多优质内容，感谢您的慷慨支持！

考前注意事项

1、DevCpp添加c++11支持

点击 工具 - 编译选项 中添加：

1
-std=c++11

2、万能头文件

1
#include <bits/stdc++.h>

万能头文件的缺陷：y1 变量

<bits/stdc++.h>引入了<cmath>， 在<cmath>中用过了y1变量。

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;

// 错误示例
int y1;

int main() {
    scanf("%d", &y1);
    printf("%d", y1);
    return 0;
}

3、cin / cout 加速

1
2
3
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

📢 注意：加速命令后cin cout 不要同时和 scanf 和 printf 一起使用

4、数组范围

  1. 一维int数组最大开到 1e7
  2. C++ 1s 的时间复杂度控制到 1e8 ~ 1e9
    1. 枚举两个for嵌套，每个for最多可以运行 10000 次
    2. 枚举三个for嵌套，每个for最多可以运行 464 次
  3. int 型变量最大记为 2e9 , long long 最大记为 1e18 ，OI 赛制不开long long见祖宗

5、暴力蹭分

OI 赛制，可以先想暴力，再去想算法去优化时间/空间

  1. for循环直接枚举、数组或者答案（线性考虑二分）
  2. 枚举排列组合的方案
  3. 要找规律，可以直接写程序去找
  4. 打表：可以在本地一直跑，跑出答案直接写到数组里，交程序时候直接读出数组中计算好的答案即可。

6、根据数据范围反推算法时间复杂度

由数据范围反推算法复杂度以及算法内容 - AcWing

蓝桥杯板子

1、STL库

C++ STL总结 (wyqz.top)

2、试除法判定质数

1
2
3
4
5
6
7
bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0)
            return false;
    return true;
}

3、线性质数筛

1
2
3
4
5
6
7
8
9
10
11
12
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

4、快速幂

求 x^y mod p，时间复杂度 O(logk)。

1
2
3
4
5
6
7
8
9
10
11
// x: 底数	y: 指数 	p: MOD
LL quickPower(LL x, LL y, LL p) {
    LL res = 1;
    x = x % p;
    while (y) {
        if (y & 1) res = (res * x) % p;
        y >>= 1;
        x = (x * x) % p;
    }
    return res;
}

5、Sort() 排序方法

从大到小排序：

1
2
int arr[5] = {5, 3, 1, 2, 4};
sort(arr, arr + 5, greater<>());	// 5 4 3 2 1

vector排序：

1
2
vector<int> vec = {5, 3, 1, 2, 4};
sort(vec.begin(), vec.end(), greater<>()); // 5 4 3 2 1

cmp() 自定义排序函数：

1
2
3
4
5
6
7
8
bool cmp(int x, int y) {
    return x > y;
}

int main() {
    int arr[5] = {5, 3, 1, 2, 4};
    sort(arr, arr + 5, cmp);    // 5 4 3 2 1 
}

6、进制转换

将十进制数转换为指定进制的字符串

1
2
3
4
5
6
7
8
9
string convertToBase(int num, int base) {
    string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string result = "";
    while (num > 0) {
        result = digits[num % base] + result;
        num /= base;
    }
    return result;
}

将指定进制的字符串转换为十进制数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int convertFromBase(string numStr, int base) {
    string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int result = 0;
    for (int i = 0; i < numStr.length(); i++) {
        int d = digits.find(numStr[i]);
        result += d * pow(base, numStr.length() - 1 - i);
    }
    return result;
}

int n2ten(string numStr, int b) {
    string temp = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int ans = 0;
    for(int i = 0; i < numStr.length(); i++) {
        ans *= b;
        ans += temp.find(numStr[i]);
    }
    return ans;
}

7、并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i++) p[i] = i;

// 合并a和b所在的两个集合：
p[find(a)] = find(b);