历年真题

2013年第四届蓝桥杯省赛真题C++ B组
2014年第五届蓝桥杯省赛真题C++ B组
2016年第七届蓝桥杯省赛真题C++ B组
2017年第八届蓝桥杯省赛真题C++ B组
2018年第九届蓝桥杯省赛真题C++ B组
2019年第十届蓝桥杯省赛真题C++ B组
2020年第十一届蓝桥杯省赛第二场（10月17日）真题C++ B组
2021年第十二届蓝桥杯省赛第一场（5月9日）真题C++ B组

算法思维

CC150给出算法题五种解法

1. 举例法：具体例子，到一般规则（公式符号化）
2. 模式匹配法：相似问题，到现有问题（经典的变体）
3. 简化推广法：从简化版，到复杂版（修改约束条件）
4. 简单构造法：从n=1开始（递归过递推）
5. 数据结构头脑风暴法：链表？数组？二叉树？堆？栈？队列？前缀和？树桩数组？区间树？

1. 模拟

1.1日期处理

2013-高斯日记、2020-跑步锻炼

1.1.1 解法一：win自带的计算器

1.1.2 解法二：Excel+手算

在用excel的时候计算1月1日到1月3日的天数应该是两天，但是左侧的的行数是3，记得到时候-1，视情况而定

1.1.3 解法三：代码实现

int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool is_leap(int year){
    return year%400==0||(year%4==0&&year%100!=0);
}
int get_days(int year,int month){
    if(month==2){
        return 28+is_leap(year);
    }else{
        return days[month];
    }
}

有时候直接求余2021年第一场的时间显示

1.2 全排列

用stl中的函数实现。

1. 有很多题他只要求1-9中数字，这时候把1-9中的数字全排列就可，在do中做一些操作即可

do{
	//按提议操作
}while(next_permutation(a,a+n))

2. 有些题用dfs搜索的题也可以用全排列距离出方案，14年六角填数那个题就是
3. 注意全排列是有顺序的

1.3 判断回文数

参考数字翻转

bool huiwen(int x){
    int y=x,num=0;
    while(y){
        num=num*10+y%10;
        y/=10;
    }
    if(num==x) return true;
    else return false;
}

1.4 取位数

类似数字翻转的代码。

void fanzhuan(int x){
    int y=x;
    while(y){
        int t=y%10;
        //对t进行一些操作判断(依据题意来看)
        y/=10;
    }
}

2. 数学 数论

2.1. 计数原理

2.1.1 阶乘

long long fact(int n){
    long long ans=1;
    for(int i=1;i<=n;i++){
        ans*=i;
    }
    return ans;
}

2.1.2 组合

long long C(int n,int m){
    if(m<n-m) m=n-m;
    long long ans=1;
    for(int i=m+1;i<=n;i++) ans*=i;
    for(int i=1;i<=n-m;i++) ans/=i;
    return ans;
}

2.1.3 杨辉三角求组合数

void Yanghui(int n){
    for(int i=0;i<=n;i++) C[i][0]=C[i][i]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            C[i][j]=C[i-1][j]+C[i-1][j-1];
        }
    }
}
//调用
Yanghui(n+max(a,b));//参数传下面的数字。

杨辉三角中第i 行第j 列的数字正是C i j 的结果！！！

2.2 质数

2.2.1 质数的判断

bool is_prime(int n){
    if(n<2) return false;
    for(int i=2;i<=n/i;i++){
        if(n%i==0) return false;
    }
    return true;
}

2.2.2 埃氏筛法打素数表

const int N=10000;
int primes[N],cnt;  //存放素数
bool st[N];     //判断x是否被删掉

void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]){     //如果没有被删掉的话对他处理
            primes[cnt++]=i;
            for(int j=i+i;j<=n;j+=i){
                st[j]=true;    //删掉j，注意这里是j
            }
        }
    }
}

2.2.3 线性筛法打素数表（常用）

当数据量到1e7的时候运行时间是埃氏的一半

const int N=10000;
int primes[N],cnt;  //存放素数
bool st[N];     //判断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;
        }
    }
}

2.2.4 分解质因数

一个大于1的正整数n可以分解质因数：

unordered_map<int,int> map;
void divide(int n) {
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            int c = 0;
            while (n % i == 0) {
                c++;
                n /= i;
            }
            
            map[i] += c;
        }
    }

	// 还要加上大于根号n的素因子
    if (n >= 2) map[n]++;
}

分解质因数的输出

    unordered_map<int,int>::iterator it;
    for(it=map.begin();it!=map.end();it++){
    cout<<it->first<<" "<<it->second<<endl;
    }

2.3 约数

2.3.1 最大公约数 gcd

简单递归

int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}

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

2.3.2 求约数

试除法求约数

vector<int> get_divisors(int n){
    vector<int> res;
    for(int i=1;i<=n/i;i++){
        if(n%i==0){
            res.push_back(i);
            if(i!=n/i) res.push_back(n/i);
        }
    }
    sort(res.begin(),res.end());
    return res;
}

2.3.2.1 求约数法2

有时候枚举答案的时候，如果需要枚举的数字正好是需要找的到数的因子，可以先把因子数组找出来，如找三个数乘积是2021041820210418（16位数字）的时候，如果从1开始遍历的话肯定是跑不出来的，所以最好先找出这个数的因子。

int a[5000],len;
void find_divisor(int n){
	for(int i=1;i<=n/i;i++){
		if(n%i==0){
			a[len++]=i;
			if(i!=n/i){
				a[len++]=n/i;
			}
		}
	}
}

2.3.3 约数个数

约数个数定理
一个大于1的正整数n可以分解质因数：
则n的正约数的个数就是：

套用因子分解模板

#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int,int> map;
void divide(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            int c=0;
            while(n%i==0){
                c++;
                n/=i;
            }
            map[i]+=c;
        }
    }
    if(n>1) map[n]++;
}
int main()
{
    divide(8);
    unordered_map<int,int>::iterator it;
    long long res=1,mod=1e9+7;
    for(it=map.begin();it!=map.end();it++){
        res=res*(it->second+1)%mod;
    }
    cout<<res<<endl;
} // namespace std;

2.3.4 约数之和

约数和定理

f(n)=(p1^0 + p1^1 + p1^2 +… p1^a1) (p2^0 + p2^1 + p2^2+…p2 ^ a2) … (pk ^0 + pk ^ 1 + pk ^ 2 +…pk^ak）

套用因子分解模板

#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int,int> map;
void divide(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            int c=0;
            while(n%i==0){
                c++;
                n/=i;
            }
            map[i]+=c;
        }
    }
    if(n>1) map[n]++;
}
int main()
{
    divide(8);
    unordered_map<int,int>::iterator it;
    long long res=1,mod=1e9+7;
    for(it=map.begin();it!=map.end();it++){
        int p=it->first,a=it->second;
        long long t=1;
        while(a--) t=(t*p+1)%mod;
        res=res*t%mod;
    }
    cout<<res<<endl;
} // namespace std;

3. 数据结构

3.1 图的构建

3.1.1 邻接矩阵

#include<iostream>
using namespace std;
int G[50][50];
int m,a,b;
int main()
{
	cin>>m;
	for(int i=0;i<m;i++){
		cin>>a>>b;
		G[a][b]=1;
	}
	for(int i=1;i<=m;i++){
		int sum=0;
		for(int j=1;j<=m;j++){
			if(G[i][j]==1){
				sum++;
			}
		}
		cout<<i<<"和"<<sum<<"条边相连"<<endl;
	}
	return 0;
} // namespace std;

输入&输出

3.1.2 邻接表

#include<iostream>
#include<vector>
using namespace std;
vector<int> v[50];
int m,a,b;
int main()
{
	cin>>m;
	for(int i=0;i<m;i++){
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i=1;i<=m;i++){
		cout<<i<<":";
		int v_size=v[i].size();
		for(int j=0;j<v_size;j++){
			cout<<v[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
} // namespace std;

输入&输出

3.2 并查集

#include <iostream>
using namespace std;
int fa[20001];
void init(int n){
    for(int i=1;i<=n;i++) fa[i]=i;
}
int find(int x){
    if(x==fa[x]) return x;
    else{
        fa[x]=find(fa[x]);      //父节点设为根节点
        return fa[x];           //  返回父节点 
    }
}
void unionn(int i,int j){
    int i_fa=find(i);   //找到i的祖先
    int j_fa=find(j);   //找到j的祖先
    fa[i_fa]=j_fa;      //i的祖先指向j的祖先，其实j的祖先先指向i的祖先
}
int main()
{
    int n,m,x,y,q;
    cin>>n;
    init(n);
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        unionn(x,y);
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>x>>y;
        if(find(x)==find(y)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
} // namespace std;

4. 搜索 BFS DFS

4.1 DFS

例题
1. 【DFS专题训练】一维坐标的移动
2. 【DFS专题训练】 蒜头君开公司
3. 【DFS专题训练】王子救公主
4. 【DFS专题训练】马的覆盖点
5. 【DFS专题训练】家谱
6. 【DFS专题训练】最大蛋糕数。题型：求最大连通块数
7. 【DFS专题训练】迷宫解的方案数
8. 【DFS专题训练】踏青 题型：连通块问题

4.2 BFS

【广度优先搜索BFS】总结
【DFS专题训练】一维坐标的移动

5. 常用库函数algorithm

5.1. sort()函数用法

• sort函数不需要数组接收，而且是在原数组上进行更改。如果不清楚原数组长度，必要的时候要进行单独计算。

sort(a,a+n);//sort(数组名+开始下标，数组名+结束下标,函数名）

• 可以在第三个参数传入定义大小比较多函数，或者重载“小于号”运算符。

int a[MAX_SIZE];
bool cmp(int a,int b){
	return a>b;
}
sort(a+1,a+1+n,cmp);

5.2. to_string()转化为字符串

将数字常量转换为字符串
在头文件string中

5.3. reverse() 翻转

• 翻转一个vector:
  reverse(a.begin(),a,end());
• 翻转一个数组，元素存放在1～n
  reverse(a+1,a+1+n);

5.4. unique()去重

第一点：在unique之前必须保证去重数组有序，也就是得sort一下。
第二点：unique并不会生成一个新的数组，而是将原数组多余的部分“移”到了数组之后，同时unique本身还会返回一个指针，指向去重之后的最后一位。
第三点：该函数常用于离散化，利用迭代器（或指针）的减法，可计算出去重后元素的个数。

• 把一个vector去重：
  int length = unique(a.begin(),a,end()) - a.begin();
• 把一个数组去重，元素存放在下标1~n:
  int length = unique(a+1,a+1+n)-(a+1);

5.5. lower_bound/upper_bound()二分

• lower_bound 的第三个参数传入一个元素x，在两个迭代器（指针）指定的部分上执行二分查找，返回指向第一个大于等于x的元素的位置的迭代器（指针）
• upper_bound的用法和lower_bound大致相同，唯一的区别是查找第一个大于x的元素。
• 两个迭代器（指针）指定的部分应该是提前排好序的。
• 在有序int数组（元素存放在1～n）中查找大于等于x的最小整数的下标
  int index = lower_bound(a+1,a+1+n,x)-a;

6.STL

6.1 vector, 变长数组，倍增的思想

size()  返回元素个数
empty()  返回是否为空
clear()  清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序

6.2 pair<int, int>

first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

6.3 string，字符串

size()/length()  返回字符串长度
empty()
clear()
substr(起始下标，(子串长度))  返回子串
c_str()  返回字符串所在字符数组的起始地址

6.4 queue, 队列

size()
empty()
push()  向队尾插入一个元素
front()  返回队头元素
back()  返回队尾元素
pop()  弹出队头元素

6.5 priority_queue, 优先队列，默认是大根堆

size()
empty()
push()  插入一个元素
top()  返回堆顶元素
pop()  弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

6.6 stack, 栈

size()
empty()
push()  向栈顶插入一个元素
top()  返回栈顶元素
pop()  弹出栈顶元素

6.7 set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列

size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)

set/multiset
    insert()  插入一个数
    find()  查找一个数
    count()  返回某一个数的个数
    erase()
        (1) 输入是一个数x，删除所有x   O(k + logn)
        (2) 输入一个迭代器，删除这个迭代器
    lower_bound()/upper_bound()
        lower_bound(x)  返回大于等于x的最小的数的迭代器
        upper_bound(x)  返回大于x的最小的数的迭代器
map/multimap
    insert()  插入的数是一个pair
    erase()  输入的参数是pair或者迭代器
    find()
    []  注意multimap不支持此操作。 时间复杂度是 O(logn)
    lower_bound()/upper_bound()

6.8 unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表

和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--

7. 基本算法

7.1 二分法

int l=0,r=n-1;
        while(l<r){
            int mid=(l+r)>>1;
            if(q[mid]>=x) r=mid;
            else l=mid+1;
        }

int l=0,r=n-1;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(q[mid]<=x) l=mid;
                else r=mid-1;
            }
cout<<l<<endl;

7.2 差分

差分原理
前缀和与差分
差分的应用：

1. 快速处理区间加减操作 (差分)
   b[n]=a[n]-a[n-1]

给定区间[l ,r ]，让我们把a数组中的[ l, r]区间中的每一个数都加上c.
转化为b[l]+=c并且b[r]-=c

2. 可以计算出数列各项的前缀和数组sum各项的值（前缀和）

输出原序列中从第l个数到第r个数的和
ans=sum[r]-sum[l-1]

7.3 倍增（待补充）

8. 动态规划

8.1 线性DP

8.1.1 01背包问题

#include <iostream> 
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

精简版

#include <iostream>
#include <algorithm> 
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

8.1.2 完全背包问题

#include <iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k*v[i]<=j;k++){
                f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
} // namespace std;

精简版

#include <iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
} // namespace std;

. 零碎知识点✌🏻

.1 控制格式输出

1. 类似2022/03/21控制输出

    printf("%04d%02d%02d",year,month,day);

输出没有取地址符，因为不常用总是忘。

printf的格式控制的完整格式：
% - .n l或h 格式字符
下面对组成格式说明的各项加以说明：
①%：表示格式说明的起始符号，不可缺少。
②-：有-表示左对齐输出，如省略表示右对齐输出。
③0：有0表示指定空位填0,如省略表示指定空位不填。
④m.n：m指域宽，即对应的输出项在输出设备上所占的字符数。N指精度。用于说明输出的实型数的小数位数。为指定n时，隐含的精度为n=6位。
⑤l或h:l对整型指long型，对实型指double型。h用于将整型的格式字符修正为short型。

d格式：用来输出十进制整数。有以下几种用法：
%d：按整型数据的实际长度输出。
%md：m为指定的输出字段的宽度。如果数据的位数小于m，则左端补以空格，若大于m，则按实际位数输出。
%ld：输出长整型数据。

.2 定义pair

如果数据类型只有一种的话用pair很方便，调用里面的数据的时候调用属性first和second即可。
pair类型的使用相当的繁琐，如果定义多个相同的pair类型对象，可以使用typedef简化声明：

typedef pair<int,int> PII;
set<PII> s;

参考2021年第一场蓝桥杯B组 直线那题。
pair用法

.3 头文件bitset 进制转换

cout<<bitset<8>(10)<<endl;

.4 头文件cstring

字符串处理的函数