1、哈希算法实例详解
1. 什么是哈希
Hash，一般翻译做散列、杂凑，或音译为哈希，是一个典型的利用空间换取时间的算法，把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。
如有一个学生信息表：学生的学号为：年纪+学院号+班级号+顺序排序号【如：19(年级)+002(2号学院)+01(一班)+17(17号)---190020117】类似于一个这样的信息，当我们需要找到这个学号为【190020117】的学生，在不适用哈希的时候，我们通常是使用一个顺序遍历的方式在数据中进行查询大类，再查询子类得到，这样的作法很明显不够快 ，需要O(n)左右的时间花费，对于大型的数据规模而言这显然不行，而哈希的做法是，根据一定的规律(比如说年纪不存在过老和过小的情况，以此将【190020117】进行压缩成一个简短的数据如：【192117】)并且将这个数据直接作用于内存的地址，届时我们查询【190020117】只需要进行一次压缩并访问【192117】这个地址即可，而这个压缩的方法（函数），就可以称之为哈希函数。
一般的对于哈希函数需要考虑如下内容:
a) 计算散列地址所需要的时间（即hash函数本身不要太复杂）
b) 关键字的长度
c) 表长(不宜过长或过短，避免内存浪费和算力消耗)
d) 关键字分布是否均匀，是否有规律可循
e) 设计的hash函数在满足以上条件的情况下尽量减少冲突
2.哈希与哈希表
在理解了哈希的思维之后，我们要了解什么是哈希表，哈希表顾名思义就是经过哈希函数进行转换后的一张表，通过访问哈希表，我们可以快速查询哈希表，从而得出所需要得到的数据，构建哈希表的核心就是要考虑哈希函数的冲突处理（即经过数据压缩之后可能存在多数据同一个地址，需要利用算法将冲突的数据分别存储）。
冲突处理的方法有很多，最简单的有+1法，即地址数直接+1，当两个数据都需要存储进【2019】时，可以考虑将其中的一个存进【2020】
此外还有，开放定址法，链式地址发，公共溢出法，再散列法，质数法等等，各方法面对不同的数据特征有不同的效果。
3.哈希的思维
Hash算法是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。所以Hash算法被广泛地应用在互联网应用中。
比如，利用哈希的思维在O(1)的复杂度情况下任意查询1000以内所有的质数（在创建是否是质数的时候并不是O(1)的复杂度），注意本样例只是演示思维，面对本需求可以有更好的空间利用方式（本写法比较浪费空间，仅供了解）。
#include<iostream>
using namespace std;const int maxn=1002;
int arr[maxn]={0};//判断是否是质数
bool is_pri(int n){for(int i=n-1;i>=2;i--){if(n%i==0) return false;}return true;
}void create(){for(int i=3;i<=maxn;i++){if(is_pri(i)){arr[i]=1;}}
}int main(){create();int input;while(cin>>input){if(arr[input]){cout<<input<<" 是质数"<<endl;}else{cout<<input<<" 不是质数"<<endl;}}return 0;
}
2、动态规划DP算法详解
1.简介
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
动态规划也是学习算法的同学最为头疼的一个重要算法，其类型宽泛让人无从下手，又极其的烧脑很难理解，事实上，动态规划是算法学习者的一个重要的门槛，也是一个瓶颈，掌握方法很重要，本节虽然不提供任何的具体代码，但希望简介以及介绍曲线的方式让读者能够更好的掌握。
2.思想
动态规划的基本思想是：问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。
比如说著名的斐波那契定理a[i]=a[i-1]+a[i-2]，就是一个特别好的理解方式，为什么直接写公式的算法（自底向上，从1开始递增）效率就是比递归（自顶向下，从n开始向下）的要好？
让我们来熟悉一下动态规划的特点：
a) 把原始问题划分成一系列子问题；
b) 求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间
c) 自底向上地计算。
d) 整体问题最优解取决于子问题的最优解（状态转移方程）（将子问题称为状态，最终状态的求解归结为其他状态的求解）
很简单，因为递归的方式return f(n-1)+f(n-2)会产生一些重复计算，当计算f(5)+f(4)中，f(5)其实又包含了一次f(4)，而动态规划的出现，就是为了减少这样的重复计算，通过确认一个个的状态以及到达下一个状态的【状态转移方程】，来表现，一般而言，我们使用数学语言直接表示【状态转移方程】。
3. 分类
动态规划可以分为如下四大类，可以依次进行学习：
线性动规，区域动规，树形动规，背包动规。
4. 学习方法
一切的开始，都必须要勤记笔记，在最初的学习中，比如最大不下降子序列这题目，我们可以更具题意将题目要求，总结题目意思，发现是否选取这个序列数是一个状态，这个状态分为两种情况：选取，不选取，我们可以在草稿纸上面讲每一个状态利用一个二叉树画出来，然后推到出正确的方案，这是第一步，接着我们讲二叉树中的每一个数据提出，尝试着利用动态规划的思维，将这课树的状态转移方程提出，最后根据这个状态转移方程，写出最终的答案。
在熟悉相关类型的题目达到一定的程度的时候，自然得心应手。
5. 相关例题
可以直接从dotcpp网站标签中搜索动态规划即可，动态规划拥有海量的题目，非常适合深入理解和练习。
例题：
| 1255 | 蓝桥杯算法提高-能量项链 |
|---|---|
| 1436 | 蓝桥杯2014年第五届真题-地宫取宝 |
| 1557 | 蓝桥杯算法提高VIP-聪明的美食家 |
3、贪心算法实例详解
1.简介
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
2.思想
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件，直到把所有数据枚举完。
贪心算法的思想如下：
a)建立数学模型来描述问题；
b)把求解的问题分成若干个子问题；
c)对每一子问题求解，得到子问题的局部最优解；
d)把子问题的解局部最优解合成原来解问题的一个解。
与动态规划不同的是，贪心算法得到的是一个局部最优解（即有可能不是最理想的），而动态规划算法得到的是一个全局最优解（即必须是整体而言最理想的），一个有趣的事情是，动态规划中的01背包问题就是一个典型的贪心算法问题。
3.学习方法
由浅入深，不妨先将动态规划中的01背包问题弄熟悉，再来学习贪心算法的基础思维，其实在很多时候自己并未发觉自己已经是在使用贪心了，当你基本掌握了一些贪心的概念的时候，可以做一些诸如装箱问题，切割问题，区域分配问题的题目，巩固自己的知识。
4.相关例题
有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法，最小生成树算法和最短路径算法，甚至是一些暴力求解题目，都是使用了贪心的这种思维。
可以直接从dotcpp网站标签中搜索贪心即可，贪心算法在很多题目中均或多或少有一些思维的应用，因此题目涵盖非常广阔，非常适合逐步练习。
例题：
| 1197 | 发工资咯 |
|---|---|
| 1453 | 蓝桥杯历届试题-翻硬币 |
| 1462 | 蓝桥杯基础练习VIP-Huffuman树 |
4、博弈算法实例详解
1.简介博弈
博弈/博弈论，又称为对策论（Game Theory）、赛局理论等，既是现代数学的一个新分支，也是运筹学的一个重要学科。博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法，博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。
总而言之，博弈，就是两方（或者多方）在为了某一种目标进行的竞争。
在生活中，博弈无处不在，国与国之间的交锋就是一种博弈，在游戏中你与对手的有来有回也是一种博弈，面对老板提出加工资的需求又也是一种博弈，在博弈中，选择去做什么非常重要，这也是十分有研究价值的，一个有趣的题外话：从1994年诺贝尔经济学奖授予3位博弈论专家开始，共有7届的诺贝尔经济学奖与博弈论的研究有关。
2.思想
博弈问题的特点
a) 博弈模型为两人轮流决策的非合作博弈。即两人轮流进行决策，并且两人都使用最优策略来获取胜利
b) 博弈是有限的。即无论两人怎样决策，都会在有限步后决出胜负
c) 公平博弈。即两人进行决策所遵循的规则相同
3. 学习方法
关于博弈论，最理想的学习方式还当属熟悉模型，几种常用的博弈论模型有：巴什博弈，威佐夫博弈，斐波那契博弈，尼姆博弈，通过理解模型以及他们模型可能产生的变种，面对各种题目也只是“换汤不换药”的思维。
在基本了解各类模型之后，我们可以开始学习“博弈树”和“决策树”这类算法，以及其他一些启发式算法，这与人工智能的思维很接近，此时算法难度已经直线上升，在经过这个瓶颈之后，等待你的是一片星辰大海。
4.经典例题
直接搜索题目标签“博弈论”即可找到题目，目前的题目属于比较入门的题，大家可以扩展去思考和处理。