【STL】二分查找函数(算法)—binary_search
【题解】采药的最短路径
【题目描述】
少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。
下图 显示了一个迷阵的样例及李逍遥找到仙药的路线。
【输入描述】
第1行输入两个非零整数 M 和 N ，两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。
接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:
1) ‘@’：少年李逍遥所在的位置；
2) ‘.’：可以安全通行的方格；
3) ‘#’：有怪物的方格；
4) ‘*’：仙药所在位置。
【输出描述】
求李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。
【样例输入】
8 8 .@##...# #....#.# #.#.##.. ..#.###. #.#...#. ..###.#. ...#.*.. .#...###
【样例输出】
10
【题解】小X玩游戏
【题目描述】
小X喜欢玩游戏。
这天，小X觉得传统的游戏都玩腻了，自己随手在草稿纸上画了一行N个格子作为棋盘， 制定了如下规则：格子从左到右依次编号为1到N，玩家初始位于格子1，初始前进方向为向右，游戏共进行M轮，第i轮玩家前进Ai格，若玩家到达格子N则改变前进方向为向左，若玩家到达格子1则改变前进方向为向右。
小X想知道玩家最后会停在哪个格子，但这个游戏太漫长了，他已经玩得快睡着了，希望你帮帮他。
【输入描述】
第一行包含用一个空格隔开的两个整数N,M。
接下来M行，第i行包含一个整数Ai。
【输出描述】
第一行包含一个整数，表示玩家最后停留的格子编号。
【样例输入】
3 2 2 3
【样例输出】
2
【提示】
样例说明
玩家的路线为 1->2->3->2->1->2。
【数据范围】
对于30%的数据，N=2，M≤10，Ai=1。
对于60%的数据，N≤1000，M≤1000，Ai≤1000。
对于 100%的数据，2≤N≤100000，1≤M≤100000，1≤Ai≤1000000000。
【题解】最短路径问题
【题目描述】
平面上有n个点（n≤100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。
若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
【输入描述】
共n+m+3行，其中:
第一行为整数n。
第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。
第n+2行为一个整数m，表示图中连线的个数。
此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。
最后一行：两个整数s和t，分别表示源点和目标点。
【输出描述】
一行，一个实数（保留两位小数），表示从s到t的最短路径长度。
【样例输入】
5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5
【样例输出】
3.41
C++中的宏
C++中的溢出
STL入门——容器3：map
深搜剪枝技巧
一、什么是剪枝
首先应当明确的是，“剪枝”的含义是什么。我们知道，搜索的进程可以看作是从树根出发，遍历一棵倒置的树——搜索树的过程。而所谓剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是坚强搜索树中的某些“枝条”，故称剪枝。
我们在编写搜索程序的时候，一般都要考虑剪枝。显而易见，应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留。设计好的剪枝判断方法，往往能够使程序的运行时间大大缩短；否则，可能适得其反。
二、剪枝的原则
1.正确性：
我们知道，剪枝方法之所以能够优化程序的执行效率，正如前文所述，是因为它能够“剪去”搜索树中的一些“枝条”。然而，如果在剪枝的时候，将“长有”我们所需要的解的枝条也剪掉了，那么，一切优化也就失去了意义。所以，对剪枝的第一个要求就是正确性，即必须保证不丢失正确的结果，这是剪枝优化的前提。
2.准确性：
在保证正确性的基础上 ，对剪枝判断的第二个要求就是准确性，即能够尽可能多地剪去不能通向正确的枝条。剪枝方法只有在具有了较高的准确性的时候，才能真正收到优化的效果。
3.高效性：
一般来说，设计好剪枝判断方法之后，我们对搜索树的每个枝条都要执行一次判断操作。然而，由于是利用出解的“必要条件”进行判断，所以，必然是有很多不含正解的枝条没有被剪枝。这些情况下的剪枝判断操作，对于程序的
效率提高无疑是具有副作用的。为了尽量减少剪枝判断的副作用，我们除了要下功夫改善判断的准确性之外，经常还需要提高判断操作本身的时间效率。
然而这就带来了一个矛盾：我们为了加强优化效果，就必须提高剪枝判断的准确性，因此，常常不得不提高判断操作的复杂度，也就同时降低了剪枝判断的时间效率；但是，如果剪枝判断的时间消耗过多，就有可能降低、甚至完全抵消
提高判断准确性所能带来的优化效果，这恐怕会得不偿失。很多情况下，能否较好地解决这个矛盾，往往成为搜索算法优化的关键。
综上所述:我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。
三、深度优先搜索的优化技巧
1.优化搜索顺序
在一些搜索问题中，搜索树的各个层次、各个分支之间的顺序不是固定的。不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。
2.排除等效冗余
在搜索过程中，如果我们能够判断从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索。
3.可行性剪枝
在搜索过程中，及时对当前状态进行检查，如果发现分支已经无法到达递归边界就及时回溯。这就好比我们在道路上行走时，远远看到前方是一个死胡同，就应该立即折返，走到路的尽头再返回。
某些题目条件的范围限制是一个区间，此时可行性剪枝也被称为上下界。
4.最优性剪枝
在最优化问题的搜索过程中，如果当前花费的代价已经超过当前搜到的最优解，那么取多么优秀的策略到达递归边接，都不可能更新答案，此时可以停止对当前分支的搜索回溯。
5.记忆化
可以记录每个状态的搜索结果，在重复遍历一个状态时直接搜索并返回。这好比我们进行深度优先遍历时，标记一个节点是否已经被访问过。
四、例题
【问题描述】
将整数n分成k份，且每份不能为空，问有多少种不同的分法？当n=7，k=3时，下面三种分法是被认为是相同的：1，1，5；
1，5，1；5，1，1。
【输入格式】
输入文件只有一行，为两个整数n和k。（6<n<=200， 2<=k<=6）
【输出格式】
输出文件仅有一行，为一个整数，即不同的分法数。
【样例输入】
7 3
【样例输出】
4
【样例解释】
四种分法为：1，1，5；1，2，4；1，3，3；2，2，3；
【数据规模】
对100%的数据，6<=n<=200, 2<=k<=6