BBC
蓝桥杯知识点与算法简介
纯属小白 望各位ACM，OI大佬不要嘲笑,以下是这半个月的学习安排和计划，重中之重的方法在于搜索和回溯的应用，搜索包括DFS、BFS，更难一点的就是DFS记忆化搜索，至于回溯最好去了解一下八皇后问题，这样可以对于回溯了解的更加深刻
1.贪心算法
2.动态规划
3.递推递归
4.搜索
5.分治算法
6.枚举算法
7.BFS算法
8.DFS算法
9.图论
10.数论
11.其他题型积累 to do lists: //待办
1.贪心算法
- 基本思想
1）贪婪算法（贪心算法）是指在对问题进行求解时，在每一步选择中都采取最好或者最优（即最有利）的选择，从而希望能够导致结果是最好或者最优的算法。
2）贪婪算法所得到的结果不一定是最优的结果（有时候会是最优解），但是都是相对近似（接近）最优解的结果。
- 局限性
贪心算法失效的很大一个原因在于它明显的局限性：它几乎只考虑局部最优解。 所谓局部最优，就是只考虑当前的最大利益，既不向前多看一步，也不向后多看一步，导致每次都只用当前阶段的最优解。 因此在绝大多数情况下，贪心算法不能得到整体最优解，但它的解是最优解的一个很好近似。
- 练习题
3.1 最大比例： 2016蓝桥杯省赛贪心算法题目 利用vector的erase和unique去重，然后使用贪心找到最小的公倍数之比
3.2 付账问题： 2018蓝桥杯省赛贪心算法题目 非常典型的贪心，每一次都是取当前情况的最优解 题目要求输出n位小数： iomanip cout<<fixed<<setprecision(n)<<>>>>
3.3 日志统计 双指针 贪心 2018蓝桥杯省赛贪心算法题目 学习了map的使用，key为int，value为vector
注意空格 end不存储数据 使用引用避免大量空间占用 使用迭代器依次访问 还是得用iterator，因为key的值并不连续 iter双指针 iter->first iter->second 分别控制key和value（vector） 3.4 训练士兵 2018蓝桥杯省赛贪心算法题目 这道题非常好，学到了很多，第一个是pair如何使用，以及对应的场景，关于剪枝，全部都变等于全都不变（！），第二个是使用数学公式代替一些小的循环（累加）操作
1
2
3
4pair<int,int> a[100000];
for(int i=0;i<n;i++){
cin>>a[i].first>>a[i].second;
}
2.动态规划
动态规划中最重要的是找到状态转移方程！！！
DP全称是dynamic programming，这里programming不是编程，是一个表格保存之前的结果。 DP 是一种编程思想，主要用于解决最优解类型的问题。 其思路是为了求解当前的问题的最优解，使用子问题的最优解，然后综合处理，最终得到原问题的最优解。 但是也不是说任何最优解问题都可以DP，使用dp的问题一般满足下面的两个特征： （1）最优子结构，就是指问题可以通过子问题最优解得到；体现为找出所有的子问题最优解，然后取其中的最优； （2）重叠子问题，就是子问题是会重复的。而不是一直产生新的子问题（比如分治类型的问题）。 一般而言，满足上述两个条件的最优解问题都可以会使用DP来解决。
有两种思路，一种是自顶向下，就是直接从原问题入手，不断利用子问题来求解，这种写法是一个递归地形式，但是需要加入备忘录，就是说利用一个数组存已经算出的子问题的结果，下次遇到直接返回。这个思路叫做memoization，备忘录。是一种空间换时间的做法，因为某些子问题会被调用到很多次，如果使用memo，那么时间上会很高效。比如求斐波那契数列，几乎每一个求解都会用到f(2)这样的子问题，如果事先存好，那么时间复杂度会下降很多。还有一点，memo不是为dp而生的，它也是一种思想或者技巧，在递归或者dfs中可以使用，如果要求时间复杂度可以考虑使用memo。第二种是自底向上，这种不需要递归，就是不断地计算出小问题的解，然后后面的问题就可以利用小问题的解得到
练习题
-3.1 包子凑数2018蓝桥杯省赛动态规划题目
核心数学原理：Schur定理 舒尔定理 对于一组互质的正整数 \(a_1, a_2, \ldots, a_n\)（即 \(\gcd(a_1, a_2, \ldots, a_n) = 1\)），Schur定理保证： - 存在有限的最大不可表示的正整数 \(G(a_1, \ldots, a_n)\) - 所有大于 \(G\) 的正整数都可以表示为这些数的非负整数线性组合
上限的确定 并不一定要求数学的绝对严谨，我对这个问题的纠结导致了最后没拿满分 (6 10 15) 我的这个是偏数学的方法，更像是一种暴力 最后的速度确实也很慢 更加优雅的是利用dp[i] = dp[i]+dp[i-x]+dp[i-y]+dp[i-z]的思路
ps:做好代码备份 找自己的历史代码的样子很狼狈幸好bbc有提交记录
- 3.2 对局匹配（经典题型：打家劫舍）2017国赛
做这道题目的发现 动态规划的核心应该是如何寻找到子问题的表达式（吗？）自己目前动态规划的理解 以及stl的使用实在是太糟糕了 现在加急补上
分段分段 找状态转移方程 vector初始化没设置长度就是push_back 设置了长度直接当数组用；
7.BFS
将队首结点可拓展的点入队，如果没有可拓展的点，将队首结点出队。重复以上步骤，直到到达目标位置或者队列为空 —— bfs先找到的一定是最短的。但是如果是加权边的话这样就会出问题了
使用栈的思维解决问题，但是不必要使用此数据结构，可以自己实现
7.1 经典——走迷宫 queue 1
2
3
4
5q.push(value);//创建一个空队列，存储int类型
q.pop();
int front = q.front();//返回第一个
int back = q.back();
int size = q.size();
8.DFS
10.数学
进制转换
平面几何
组合数学
质数判断
快速幂
2017国赛小数第n位
实际上要求的值是a10^(n+2)/b \(n\)=\(10^9\) 但是要解决溢出问题 我们会注意到
当我们计算取余时，只会消除掉整数部分，而小数部分会保留在取余的结果中，所以我的思路是求得（a10^(n-1)）%b的值，然后再1000/b,就是最后的答案
又因为(ab)%p=(a%p*b%p)%p （整数域）
收获很多，但是这种题第一次遇到我肯定不会最大公因数 and 最小公倍数
11.其他题型积累
- 基本知识点
- 排序算法
1
2
3
4
5#include <algorithm> // 包含 std::sort
int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
// 默认升序排序
std::sort(arr, arr + n); - 初始化不要偷懒
数据类型的选择 float double long long long
正确的数据结构才是解题的关键
1
2
3vector<int> a(n); // 初始化大小为n的vector
sort(a.begin(), a.end()); // 排序
arr.erase(arr.unique(arr.begin(), arr.end()), arr.end()); // 去重常见数据类型的范围
| 数据类型 | 大小（字节） | 表示范围（近似） | 备注 |
|---|---|---|---|
char |
1 | -128 ~ 127 或 0 ~ 255 | 字符型/字节型 |
short |
2 | -32,768 ~ 32,767 | 短整型 |
int |
4 | -2.1×10⁹ ~ 2.1×10⁹ | 默认整型 |
long |
4/8 | 同int或-9.2×10¹⁸ ~ 9.2×10¹⁸ | Windows:4, Linux/Mac:8 |
long long |
8 | -9.2×10¹⁸ ~ 9.2×10¹⁸ | 64位整型 |
float |
4 | 约6-7位有效数字 | 单精度浮点 |
double |
8 | 约15-16位有效数字 | 双精度浮点 |
long double |
16 | 约18-19位有效数字 | 扩展精度浮点 |
- 去重,剪枝 提前结束循环 ， 设置预先条件
最大公因数 >求两个数的最大公约数 a>b 则有关系 gcd(a,b)=gcd(b,a%b) 欧几里得算法
时间问题
1
2
3
4
5
6
7
8
9
10from datetime import *
a=date(1949,10,1)
b=date(2012,10,1)
cnt=0
while a<=b:
if a.weekday()==6 and a.day==1 and a.month==10:
cnt+=1
a+=timedelta(1)
print(cnt)二分搜索法
20 个圆和 20 条直线最多能把平面分成多少个部分？
m个圆可以把平面分成 \(m^2 - m + 2\)
n条直线可以把平面分成 \(n^2/2 + n/2 + 1\)
递推的时候有点坑的是 最后f(m,1)=f(m,0)+2m 没有常数项
这里不能想当然 因为 包含了初始圆这个条件、
5.卡特兰数//国赛题
6.字符串处理
string 变长 1
2
3
4
5string a;
a.resize(a_len);
for(int i=0;i<a_len;i++){
a[i]='0';
}