「蓝桥杯整体概述」：

前两届蓝桥杯都是两道选择+八道程序设计题目了。分值是从小到大递增的（5+5+10+10+15+15+20+20+25+25），满分150分。

重庆相比于其他地区来说是算法弱省，因此拿到省奖的机会还是很大的。省三估计是35+就差不多了，省一也就是50+（个人估计值）。因为蓝桥杯是考完之后系统才会评判你的代码分数，而且不公开。

可以去做往届的题给自己估一下水平。

蓝桥杯考的算法，几届改动都不会太大，有人推荐的蓝桥杯备赛方案就是去反复刷往届的题。

「本文整体概述」：

本文总结了一些基本的算法、技巧和刷题网站。本质是帮助大家达到50分，拿个省一的样子。不能让大家从80分提到120分这种。

高手可以不看本文，看了也是浪费你时间。

学习算法

我这里会推荐一些我博客中有的文章，可以参考学习。大家也可以自己去BiliBili上找视频看。

看视频个人推荐去买ACWing的算法基础课和提高课来看（进阶课我也没看过，估计看完参加蓝桥杯都是洒洒水了）。

看文章个人推荐：我的博客和OI WiKI

掌握这些方法速成就是要知道：算法的作用（干什么用的），算法的模版（自己能用出来）。不过一般不考原题，建议掌握原理。

掌握好一点就要把原理搞清楚，最好要搞懂证明。这样别人修改题目你也能对应修改代码。

排序，这个在比赛中直接使用 sort() 就可以了，还要掌握结构体排序，自定义排序。不过有余力的同学还是可以学一下，因为归并排序核心的思想的分治，快速排序的核心思想是双指针，基数排序的核心思想有点像哈希、散列…学排序可以学这些思想。

可以看分类: 排序 | 秋白’s Blog (yongruizhang.cn)
二分查找，也叫折半查找，在编程比赛经常会遇到。
贪心算法，贪心算法一般就是找到最优解的方法，比较灵活。
DFS和BFS，搜索算法，几乎必考。

可以看分类: 搜索算法 | 秋白’s Blog (yongruizhang.cn)

注意理解剪枝的思想。
DP，几乎必考。DP题目难在状态的定义和状态转移方程的推导，可以先学习基础的背包问题，几种背包问题学完基本够用了。

可以看下这些文章：

动态规划入门 | 秋白’s Blog (yongruizhang.cn)

下面两个其实不完全，因为有时候我做了题觉得简单或者思想差不多就不会写笔记（更不会发博客了）

分类: 动态规划基本原理 | 秋白’s Blog (yongruizhang.cn)

分类: 动态规划算法题 | 秋白’s Blog (yongruizhang.cn)
计算几何，一般涉及较少，这是难就很难，简单就很简单。
图论、树论（树其实是一种特殊的图,有向无环图）。

零基础可看分类: 图论 | 秋白’s Blog (yongruizhang.cn)。根据日期从前往后学。
- 最短路——Dijkstra、SPFA、Bellman-Ford、Floyd。可以看文章：最短路算法 | 秋白’s Blog (yongruizhang.cn)
  
  这里至少要掌握Dijkstra、Floyd
- 树、图的遍历（二叉树（多叉树）的前、中、后序遍历、层序遍历）。可以看文章：二叉树基础 | 秋白’s Blog (yongruizhang.cn)
- 树状数组
- 最小生成树——Kruskal、Prime。生成树 | 秋白’s Blog (yongruizhang.cn)
数论，基本都会考。这个一般简单的都很简单，难的都很难，个人感觉第十五届可能会有一道压轴数论题（难）。

可以看文章：数论基础 | 秋白’s Blog (yongruizhang.cn)
- 最大公约数，最小公倍数，筛素数、快速幂（常用于求逆元）
高精度，这个其实不怎么考。

高精度基础 | 秋白’s Blog (yongruizhang.cn)

练习题：分类: 高精度 | 秋白’s Blog (yongruizhang.cn)
前缀和与差分，这个最近的省赛国赛都有考。

入门：前缀和与差分 | 秋白’s Blog (yongruizhang.cn)

算法题：分类: 前缀和与差分 | 秋白’s Blog (yongruizhang.cn)
栈和队列：最基本的数据结构，这个必须掌握，不然DFS和BFS怎么实现。

蓝桥杯这些届的出题给人感觉就是偏搜索和DP的比较多，所以搜索和DP一定要会。要会暴力。蓝桥杯也是暴力杯嘛

掌握一些技巧和函数

「函数」：

STL的常用容器：（其实不算函数，归到这类里了）

vector
set、unordered_set、mutliset
map、unordered_map、multimap
stack
queue
priority_queue

这些容器的创建、初始化、增加元素、删除元素、遍历元素、判断是否为空等操作要会。

字符串：string

它的常用函数要会：c_str()，find()，substr()，repalce()

要会：字符串转int，字符串转char[]，int转字符串

「技巧和注意事项」：

定义一半可以定义在main函数外，全局定义。这样在调用函数的时候会方便一些。尤其是二位数组的传参数很容易错，不如放在全局变量位置
开long long。蓝桥杯的内存其实是开得很大的，基本可以无脑开long long。很多时候结果也会是爆int的，自己不会算就无脑开。

读写最好关闭同步（吸氧其实基本没必要），（给个我的基本模版）

#include <bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f

using namespace std;

typedef long long ll;

int main() {
	cin.tie(nullptr) -> ios::sync_with_stdio(false);

	return 0;
}

根据数据范围猜算法。这个要求你必须掌握每个算法的时间复杂度，不然你猜出来时间复杂度了也不知道用哪个算法。
一些更快的方法：（不过蓝桥杯其实不太在意这点加速）
1. if ... else if ... 比 if ... if ... 快。.. ? .. : .. 比if ... else if ... 快
2. 位运算比乘法快
3. ++i比i++快
多注意思考边界情况，也叫特判。就是题目中会不会出现某种特殊情况，和整体结论不一样的。

快速复习（要点回忆）

看评论区了解数据规模（一秒计算多少次判断算法时间复杂度等），\n比endl快
闰年判断，闰年条件：n%400 == 0 || (n%4 == 0 && n%100 != 0)。闰年的2月有29天。

保留小数，保留两位举例：

1
2
3

cout << fixed << setprecision(2) << a; // iomanip

printf("%.2f", a);

string与int

int num = 123;
string snum = std::to_string(num);

string str = "666";
int num = atoi(str.c_str());

KMP

int strStr(string s, string p) { // s为匹配串，p为模式串。找到第一个匹配的下标
    int n = s.size(), m = p.size();
    if(m == 0) return 0;
    vector<int> next(m);
    //预处理next数组
    for(int i = 1, j = 0; i < m; i++){
        while(j and p[i] != p[j]) j = next[j - 1];
        if(p[i] == p[j]) j++;
        next[i] = j;
    }
    //匹配过程
    for(int i = 0, j = 0; i < n; i++){
        while(j and s[i] != p[j]) j = next[j - 1];
        if(s[i] == p[j]) j++;
        if(j == m)
            return i - m + 1;
    }
    return -1;
}

输入一整行

1
2
3

string s;
getline(cin, s, '\n');
cout << s;

数论

最大公约数：

1
2
3

int gcd(int a, int b) {
	return b? gcd(b, a%b): a;
}

最小公倍数：a*b/gcd(a, b)

快速幂，求$a^b \mod p$

ll qmi(int a, int b, int p) {
    ll res = 1;
    for (; k; k >>= 1){
        if (k&1) res = res * a % p;
        a = a * a % p;
    }
    return res;
}

快速幂求逆元：求$a \mod p$的乘法逆元，当$a\%p = 0$时无逆元，否则就是求$a^{p-2}$

分解质因数：

即求：$N=p_1^{\alpha_1} + p_2^{\alpha_2} + \cdots + p_k^{\alpha_k}$ 的 $p-\alpha$对

void divide(int n) {
    for (int i = 2; i <= n/i; ++i)
        if (n%i == 0) {
            int s = 0;
            while (n%i == 0) {
                n /= i;
                s++;
            }
            cout << i << " " << s << endl;
        }
    
    if (n > 1) cout << n << " 1\n";
}

线性筛质数

int primes[N]; // 存质数
int cnt = 0; // 质数个数
void get_prime(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;
        }
    }
}

约数个数：

由算数基本定理：$N=p_1^{\alpha_1} + p_2^{\alpha_2} + \cdots + p_k^{\alpha_k}$，可以得出，约数个数为$(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)$。

unordered_map<int, int> primes; // {底数（质数）， 指数}
ll res = 0; // 约数个数
int mod = 1e9+7;
void divide(int n) {
    for (int i = 2; i <= n/i; ++i) {
        while (n%i == 0) {
            n /= i;
            primes[i] ++;
        }
    }
    if (n > 1) n ++;
}

for (auto prime: primes)
    res = res*(primes.second+1)%mod;

约数之和：

由算数基本定理：$N=p_1^{\alpha_1} + p_2^{\alpha_2} + \cdots + p_k^{\alpha_k}$，可以得出，约数之和为$(p_1^0+p_1^1+\cdots+p_1^{\alpha_1})\cdots(p_k^0+p_k^1+\cdots+p_k^{\alpha_k})$。

unordered_map<int, int> primes; // {底数（质数）， 指数}
ll res = 1; // 约数之和
int mod = 1e9+7;
void divide(int n) {
    for (int i = 2; i <= n; ++i)
        while (n%i == 0) {
            n /= i;
            primes[i] ++;
        }

    if (n > 1) primes[n] ++;
}

for (auto prime: primes) {
    int p = prime.first, a = prime.second;
    ll tp = 1;
    while (a--) tp = (tp*p+1)%mod;
    res = res * tp %mod;
}

欧拉函数

1～N中与N互质的个数被称为欧拉函数，记为$\varPhi(N)$。

若在算数基本定理中，$N=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m}$,则：

$\varPhi(N) = N\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}\cdots\frac{p_m-1}{p_m} = N(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_m})$$，\varPhi(1) = 1$

int res = x; // x为n，即待求数
for (int i = 2; i <= x/i; ++i) {
    if (x%i == 0) {
        res = res / i * (i-1);
        while (x%i == 0) x /= i;
    }
}
if (x > 1) res = res / x * (x-1);

cout << res << endl;

n进制转10进制

int n2ten(string num, int n) { // num为n进制数，n为进制
    int ans = 0;
    for (int i = 0; i < s.size(); ++i)
        ans = ans*n + s[i]-'0';
   	return ans;
}

n大于10时还要判断字母。

10进制转n进制

string a; // a为转换后的n进制数
void ten2n(int num, int n) { // num为10进制数，n为进制
    while (num) {
        a = a + (char)(num%2+'0'); // 大于10注意判断字符
        num /= n;
    }
    reverse(a.begin(), a.end());
}

常用STL

string

size()      //返回大小
empty()     //判断是否为空
clear()     //清空
substr(起始下标，子串长度)   //返回指定长度子串
find()      //查找字符第一次出现的位置，如果没有出现过则返回string::npos (-1)
//非成员函数
stoi()    //将字符串转化成int类型，传入string类型字符串
atoi()    //将字符串转化为int类型，传入char类型字符串

vector

size()        //返回元素个数
empty()       //判空
clear()      //清空
push_back()   //在尾部添加一个元素
pop_back()    //删除最后一个元素
begin()/end()   //首迭代、尾迭代
front()/back()  //返回第一个/最后一个元素

queue/priority_queue

size()    //返回队列中元素的个数
empty()   //判空
push()    //在末尾加入一个元素
pop()     //删除第一个元素
front()/back()   //返回第一个/最后一个元素

priority_queue

size()    //返回优先队列中元素的个数
empty()   //判空
push()    //加入一个元素
pop()     //删除堆顶元素
top()     //返回堆顶元素
默认定义为大根堆
//定义成小根堆方法：
priority_queue<int,vector<int>,greater<int>> q;

stack

size()     //返回栈元素个数
empty()    //判空
push()    //入栈
pop()    //出栈
top()    //返回栈顶元素

set、multiset、unordered_set

set去重，multiset不去重，unordered_set的元素不能为typedef的均默认升序排序
size()   //返回集合中元素个数
empty()  //判空
clear()  //清空所有元素
insert()  //在集合中插入元素
find()    //查找一个数，如果找到则返回该数第一次出现位置的迭代器，否则返回尾迭代
count()    //返回某个值元素的个数

map、multimap、unordered_map也一样

algorithm

// sort
sort(a.begin(), a.end()); // a为容器
sort(a, a+n); // a为数组

bool cmp(int a, int b) {
    return a < b;
}
sort(a.begin(), a.end(), cmp); // 自定义排序
max()
min()
swap()
reverse(a.begin(), a.end());
reverse(a, a+n);
int c = unique(a.begin(), a.end()) - a; // 去重前先排序，c为去重后长度
int c = unique(a, a+n) - a;

高精度

注意，传入参数都是低位在左，除了高精度除低精度的返回结果时高位在左以外，都是低位在左。

高精度加法

// c = a + b
vector<int> add(vector<int>& a, vector<int>& b) {
    if (a.size() < b.size()) return add(b, a);
    
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); ++i) {
        t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t%10);
        t /= 10;
    }
    if (t) c.push_back(t);
    return c;
}

高精度减法

// c = a - b
vecto<int> sub(vector<int>& a, vector<int>& b) {
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); ++i) {
        t = a[i] - t;
        if (i < b.size()) t -= b[i];
        c.push_back((t+10)%10);
        if (t < 0) t = 1;
        else t = 0;
    }
    
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}

高精度乘低精度

// c = a * b
vecto<int> mul(vector<int>& a, int b) {
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size() || t; ++i) {
        if (i < a.size()) t += a[i]*b;
        c.push_back(t%10);
        t /= 10;
    }
    
    while (c.size() > 1 && c.back == 0) c.pop_back();
    return c;
}

高精度除低精度

// a / b = c...r
vector<int> div(vector<int>& a, int b, int& r) {
    vector<int> c;
    r = 0;
    for (int i = a.size()-1; i >= 0; --i) {
        r = r*10 + a[i];
        c.push_back(r/b);
        r %= b;
    }
    reverse(c.begin(), c.end());
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    return c;
}