E - 双向广搜（POJ1915 Knight Moves）:

Background
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?
The Problem
Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.
For people not familiar with chess, the possible knight moves are shown in Figure 1.

INPUT:The input begins with the number n of scenarios on a single line by itself.
Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, ..., l-1}*{0, ..., l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario.

OUTPUT:For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line.

3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1

5 28 0

#include<iostream>
#include<queue>
#include <utility>
#include<iomanip>
using namespace std;int stepS[305][305];  //记录从起点开始走的步数
int stepE[305][305];  //记录从终点开始走的步数
int d[305][305];  //记录各个点的访问状态，0表示尚未访问，1表示已被从起点出发的点访问，-1终点
int conS=1,conE=1;  //记录处于同一层，即步数相同的点的个数，初始时只有起点终点各一个
int l, sx, sy, ex, ey,ans;
typedef pair<int, int>p; p ps ,pe;  //用pair模板存储二维坐标
queue<p>queS, queE;  //分设两个队列从起点和终点搜索
int dx[8] = { 1,1,-1,-1,2,2,-2,-2 };
int dy[8] = { 2,-2,2,-2,1,-1,1,-1 };  //表示走一步的八种方式int ope(p pa,int k) {int flag=0;for (int i = 0; i < 8; i++) {  //列举八种走法int nx = pa.first + dx[i], ny = pa.second + dy[i];if (nx >= 0 && nx < l && ny >= 0 && ny < l && d[nx][ny] == 0){//在棋盘内且尚未访问d[nx][ny] = k;if (k == 1) { stepS[nx][ny] = stepS[pa.first][pa.second] + 1; queS.push(p(nx, ny)); conS++;  //记录步数相同的位置的个数 }else { stepE[nx][ny] = stepE[pa.first][pa.second] + 1; queE.push(p(nx, ny)); conE++; }}                                              //在棋盘内且已被另一端访问else if (nx >= 0 && nx < l && ny >= 0 && ny < l && d[nx][ny] == -k) {if (k == 1)stepS[nx][ny] = stepS[pa.first][pa.second] + 1;else stepE[nx][ny] = stepE[pa.first][pa.second] + 1;flag = stepS[nx][ny] + stepE[nx][ny];  //两端到该点步数相加即为最终答案break;}}return flag;  //两端未相遇时flag恒为0
}int bfs() {ps.first = sx; ps.second = sy;pe.first = ex; pe.second = ey;queS.push(ps);queE.push(pe);d[ps.first][ps.second] = 1;d[pe.first][pe.second] = -1;while (queS.size()|| queE.size()) {  //两个搜索队列均为空，搜索结束while(queS.size()&&(conS--)) {  //队列不为空，对所有最短步数相同的点进一步宽度搜索ps = queS.front(); queS.pop();ans=ope(ps,1); //1代表是从起点出发的，-1代表该点从终点出发if (ans)return ans;  //如有结果返回结果}while(queE.size()&&(conE--)) {  //队列不为空，对所有最短步数相同的点进一步宽度搜索 pe = queE.front(); queE.pop();ans = ope(pe,-1);if (ans)return ans;  //如有结果返回结果}}return 0;  //搜索完毕仍无结果，说明起点到不了终点，返回0
}
int main() {int n;cin >> n;while (n--) {cin >> l >> sx >> sy >> ex >> ey;if (sx == ex && sy == ey)cout << 0 << endl;  //起点终点相同的情况特判else {cout << bfs() << endl;for (int i = 0; i < l; i++)     //数据有多组,手动初始化for (int j = 0; j < l; j++) {stepS[i][j] = stepE[i][j]= d[i][j] = 0;}while (queS.size())queS.pop();while (queE.size())queE.pop();}}}

---

 F - dfs剪枝（POJ1011 Sticks）:George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

INPUT:The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

The output should contains the smallest possible length of original sticks, one per line.

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

6
5

#include<iostream>
#include<algorithm>
using namespace std;
int sum, total,n,l;  //n棒子总数，sum棒子总长，拼成每根长度为l的长棒可以有total根
int a[65],d[65];  //a[]记录每根棒子的长度，d[]记录访问状态bool cmp(int a, int b) {  //降序排序的比较函数return a > b;  
}//nl记录当前已凑成的长棒长度
bool dfs(int s, int nl, int pos) {  //s记录当前已凑成的长棒数，pos记录访问下标if (s == total - 1)return 1;  //剪枝，若只剩最后一根长棒，剩下的棒子自动合并，不用再凑int former = -1;  //记录访问的前一根棒子的长度，初始值-1for (int i = pos; i < n; i++) {if (d[i] == 1 || a[i] == former)continue;  //剪枝，已经搜索过的棒长直接跳过d[i] = 1;  //访问下标为i的棒子if (nl + a[i] < l) {if (dfs(s, nl + a[i], i))return 1;else former = a[i];  //记录失败教训，此时访问棒子没有结果}else if(nl+a[i]==l){if (dfs(s + 1, 0, 0))return 1;  //棒子数加1，从头开始访问else former = a[i];  //记录失败教训，此时访问棒子没有结果}d[i] = 0;  //对下标为i的棒子搜索失败后回溯，记录为不访问if (nl == 0)break;  //剪枝，以下标为i的棒子构建新棒子时（因为数组降序，这应该是目前可return 0;               //用的最长的棒子），若该棒子组合失败，说明当前组合方式不能将所有
}                           //棒子都用上，跳出循环，返回失败int main() {while (cin >> n && n != 0) {sum = 0; bool flag = 0;for (int i = 0; i < n; i++) {cin >> a[i]; sum += a[i];  //输入每根棒子长度，得到总长}sort(a, a + n, cmp); //剪枝，对棒长数组降序排序再从头处理，优先处理长棒需要考虑的少for (int i = a[0]; i <= sum/2; i++) { //考虑到分成两根等长长棒为止 total = sum / i; l = i;if (sum%i==0 && dfs(0,0,0)){  //剪枝，如果长棒长度肯定是总长的因数cout << i << endl;flag = 1;break;}}if (flag==0)cout << sum << endl; //特判，所有棒子合成一根长棒for (int i = 0; i < n; i++)d[i] = 0;  //初始化访问状态数组；}
}

---

G - 迭代加深搜索练习（POJ2248 Addition Chain）:    An addition chain for n is an integer sequence <a0, a1,a2,…,am> with the following four properties:

          1.a0 = 1;
          2.am = n;
          3.a0 < a1 < a2 < … < am-1 < am;
          4.For each k (1 <= k <= m) there exist two (not necessarily different) integers i and j (0 <= i, j <= k-1) with ak = ai + aj;
       You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequence, any one is acceptable.

       For example, <1, 2, 3, 5> and <1, 2, 4, 5> are both valid solutions when you are asked for an addition chain for 5.

INPUT:The input will contain one or more test cases. Each test case consists of one line containing one integer n (1 <= n <= 100). Input is terminated by a value of zero (0) for n.

OUTPUT:For each test case, print one line containing the required integer sequence. Separate the numbers by one blank.

5 7 12 15 77 0

1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77

#include<iostream>
using namespace std;
int deep, n, tmp;  //deep记录搜索深度，n记录输入
int finish, ans[100] = { 1 };  //finish记录是否找到，ans[]记录答案void dfs(int cur ,int deep) {  //cur记录当前深度，deep为搜索深度if (cur == deep) {  //搜索到目标深度时，如果答案等于n，搜索结束if (ans[cur] == n) {finish = 1; return;}}for (int i = 0; i <= cur; i++) {  //搜索过程，将每一个a[i]与自身及自身之后的所有数匹配for (int j = i; j <= cur; j++) { //新数字要比当前最大数大才会有更大的数字出现，且要if (ans[i] + ans[j] > ans[cur] && ans[i] + ans[j] <= n) {  //小于nint sum = ans[i] + ans[j];for (int k = cur + 1; k < deep; k++)sum <<= 1; //*模拟新数到深度deep前一直自乘2后的结果，这将是到deep所能产if (sum < n)   //生最大数字，因为新数肯定是当前序列中最大数,如果它若干轮后达continue;  //不到n,答案肯定错误，直接跳过。ans[cur + 1] = ans[i] + ans[j]; dfs(cur + 1, deep);  //深度+1，继续搜索；if (finish)  //搜索成功，直接返回return;}}}
}int main() {while (cin >> n && n != 0) {deep = 0; tmp = n; finish = 0;while (tmp >>= 1)deep++; //相当于用1 2 4 8...的极端情况对deep摸底，思想与(*)处一致while (finish == 0)dfs(0, deep++);  //迭代加深搜索直到搜索成功for (int i = 0; i < deep; i++) {  //输出答案cout << ans[i];if (i != deep - 1)cout << " ";}cout << endl;}
}

---

H - 折半搜索（洛谷4799 [CEOI2015 Day2] 世界冰球锦标赛）:

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同

INPUT:

第一行，两个正整数 N 和 M(1≤N≤40,1≤M≤)(1≤N≤40,1≤M≤)，表示比赛的个数和 Bobek 那家徒四壁的财产。 

第二行，N 个以空格分隔的正整数，均不超过 ，代表每场比赛门票的价格。

OUTPUT: 输出一行，表示方案的个数。由于 N十分大，注意：答案 ≤

5 1000 100 1500 500 500 1000

8

八种方案分别是：

• 一场都不看，溜了溜了
• 价格 100 的比赛
• 第一场价格 500 的比赛
• 第二场价格 500 的比赛
• 价格 100 的比赛和第一场价格 500 的比赛
• 价格 100 的比赛和第二场价格 500 的比赛
• 两场价格 500 的比赛
• 价格 1000 的比赛

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll ans = 0,cnt=0;  //ans记录总共可行的方案数量，cnt记录前半区间的所有可行方案
ll n, m;
ll f[1 << 21]; //f[]记录前半区间的所有可行方案的花费
ll mon[45];  //mon[]记录每场球赛的费用bool cmp(int a, int b) {  //排序函数return a > b;
}
void dfs1(ll b,ll cos) {  //对前半区间深度优先搜索，b记录开始位置，cos记录费用if (cos > m)return;  //费用超出，搜索结束if (b >= n / 2) {  //到达前半区间末尾且费用合理，记录费用，cnt加1f[cnt] = cos;cnt++;return;}dfs1(b + 1, cos);  //对于下标为b+1的球赛，讨论看和不看两种情况。dfs1(b + 1, cos + mon[b]);
}
void dfs2(ll b, ll cos) {  //对后半区间深度优先搜索，b记录开始位置，cos记录费用if (cos > m)return;if (b >= n) {  //对于后半区间每个可行的cos，ans为前半区间中花费小于等于（m-cos）的方案数ans += upper_bound(f, f + cnt, m - cos) - f; //的总和，即花费拼起来小于总金额m的方return;                                      //案数的总和}dfs2(b + 1, cos);dfs2(b + 1, cos + mon[b]);
}int main(){cin >> n >> m;for (int i = 0; i < n; i++)cin >> mon[i];  //输入每场球赛的金额sort(mon, mon + n, cmp);     //对金额降序排序，剪枝，减少搜索次数dfs1(0, 0);                                sort(f, f + cnt);  //对所有可行方案升序排序，便于后面操作           dfs2(n/2, 0);cout << ans << endl;
}

---

算法Tips：

1.双向广度优先搜索：

       对于给定了起始状态和终止状态，且正逆搜索哦均能够实现的情况，将起始状态和终止状态同时作为起点进行BFS，相对于单向BFS可以减少相当一部分搜索量，相对于扩展结点较多，且目标结点又处在深处的情况有很好的优化效果。

       实现：我们将起点和终点同时加入队列进行 BFS，对于起点和终点扩展出的点我们打上不同标记，当一个点即将打上第二个标记的时候说明双向搜索相遇，输出步数之和即可。

2.剪枝：

    （1）.搜索顺序优化：不同的搜索顺序，将会产生不同规模的搜索树 组合每一个等长木棒的时候，优先从长的开始搜索，能减少搜索状态量。

    （2）.数论优化：组合出来的等长木棒的长度，一定是所有木棒总长度的约数，因此我们枚举约数搜索检验即可。

    （3）.可行性剪枝：如果第一根都无法用上，一定是失败的。最后一根等长不必搜，因为加起来一定为总长度。

    （4）.排除等效冗余：记录上一次搜到的地方，不要从第一根重新开始搜，保证每个等长木棒构成是从长到短搜索的。避免重复搜索同一个长度的木棒。

    （5）......

3.迭代加深搜索：

       DFS 最大的缺陷在于每个搜索分支深入过深，当答案在比较浅的位置 的时候花费了过多的时间在无效搜索分支中。迭代加深搜索首先深度优先搜索 k 层，若没有找到可行解，再深度优 先搜索 k+1 层，直到找到可行解为止。由于深度是从小到大逐渐增大的，所以当搜索到结果时可以保证搜索 深度是最小的。迭代加深本质上是通过枚举的手段为 DFS 增加了一个深度条件剪枝.

4.折半搜索：