蓝桥杯备赛：考前注意事项

考前注意事项

1、DevCpp添加c++11支持

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

-std=c++11

2、万能头文件

#include <bits/stdc++.h>

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

在<cmath>中用过了y1变量。

#include <bits/stdc++.h>
using namespace std;

// 错误示例
int y1;

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

3、cin / cout 加速

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

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

4、数组范围

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

5、暴力蹭分

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

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

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

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

蓝桥杯板子

1、STL库

C++ STL总结 (wyqz.top)

2、试除法判定质数

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、线性质数筛

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、快速幂

求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p) {
    int res = 1 % p, t = m;
    while (k) {
        if (k & 1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

5、Sort() 排序方法

从大到小排序：

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

vector排序：

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

cmp() 自定义排序函数：

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、进制转换

string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

// 将十进制数转换为指定进制的字符串
string convertToBase(int num, int base) {
    string result = "";
    while (num > 0) {
        result = digits[num % base] + result;
        num /= base;
    }
    return result;
}

// 将指定进制的字符串转换为十进制数
int convertFromBase(string numStr, int base) {
    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;
}