信友队暑假营第二周总结
时光飞逝，岁月如梭。一转眼，我们已经在训练营里度过了14个日月。我也相比较下学到了很多的知识。下面开始我对这一周的的总结。
经典贪心
简介：
这个是一个非常常见的策略，也是比赛中最难分辨的一个策略（对我而言），其难点主要是在他不是一段代码，而是一个思想，是一个抽象的概念。一般上到比赛，你会发现其实很多题都很像贪心，但他的正解并不是。那我主要的思路其实就是用贪心模拟一遍样例，再用一个自己的样例再模拟一遍，就基本上可以肯定是否可以用贪心了。
贪心与动态规划的区别：
贪心的适用场景就是当局部最优可以保证全局最优时（说简单一点，就是我当前干的事情一起定是对我整件事情最有利的），而动态规划只是把大问题分解成小问题，一直分分分，分到问题小到可以直接求解，所以其实还是要枚举出所有情况的。
朴素贪心
简介：
比贪心更加多样化，考虑的也更多，同时可能会加上如动态规划，二分等其他算法来进一步提升算法效率。（具体为什么就要叫朴素贪心我也不知道）
二分答案
简介：
是一个算法效率比较快的搜索算法，其主要思想是在一个在有单调性的序列里找中间值，判断是比要找的数是在他的左区间还是右区间，然后，再在缩小的区间里重复刚刚的过程，一直到中间值就是那个数为止。
模板：
int l=1,r=n+1;//左边界，右边界
while(l<r)
{
int mid=(l+r+1)/2;//中间值
if(a[mid]>x)//如果发现比要找的数大
{
r=mid-1;//让右边界缩小
}
else
{
l=mid;//反之让左边界缩小
}
}
cout<<l;//输出（其实最后l=r，输出r也可以）
搜索
简介：
分为深度优先搜索（DFS），和广度优先搜索（BFS）两种。
DFS：
深度优先搜索，其主要思路就是一直搜索，直到碰到障碍或到达目的地，再返回。思想比较简单，代码也很好写，就是由于他不撞南墙不回头的策略让他的时间复杂度直线飙升，让我们只能选择另外一个搜索策略——BFS。
BFS：
广度优先搜索，又叫宽度优先搜索，其主要思路是分析每一个未被遍历的节点可以走到哪些其他节点，这样，第一个找到的目的地就一定是最优的，会比DFS强上很多。其实现方法主要是用栈，先把第一个节点入栈，再把第一个节点可以到的所有节点都入栈，再把第一个节点出栈，再分别把每一个可以到的节点入栈，就这样一直到找到目的地，结束。
DFS优化——剪枝：
说的很高大上，其实就是多加几个判断条件，使一些完全不需要执行的，没有用的遍历不执行，让执行的次数更少一点，类似于知道要撞墙了，就赶快回头，这样可以让时间复杂度低一点（真的很有用）。
通用优化——记忆化：
就是专门弄一个数组，来记录之前查找过的结果，这样以后在查询的时候，就可以直接返回结果了。适用范围是DFS,BFS都可以，但还是主要用在DFS上。
那么以上就是我这一周学到的知识，以及我对这些知识的理解，点个赞再走吧，球球了。
