期末复习之深搜

1.张三丰的传人

描述
张三丰凭借太极拳成为一代宗师；然而岁月不饶人，他希望找到传人，在有生之年将太极拳传于弟子发扬光大。然而，张三丰的太极拳有一个特点，学的时间越长，忘记的越多。一个弟子学习时间为T，那么他只可以学习到总功力的1/T。假设张三丰计划用S的时间，他可以培养N个弟子，虽然可能每个弟子都无法完全学会，但是只要这N个弟子的总功力之和为1，张三丰就可以将S的时间，分配给这N个弟子，来完成自己的心愿；如果给定S之后，对于任何的N，都无法找到一种有效的分配方案，张三丰只能含恨而终。在这里，S，N和T均必须为正整数。

你的任务是：给定整数S，帮助张三丰找出一个整数N，以及一个分配方案。例如：S为10时，你帮助张三丰找到3个弟子，传授他们武功的时间分别为{2，4，4}；S为2时，你无论如何无法找到这样一个方案，张三丰只能含恨而终。

输入
第一行是一个正整数m，表示测试数据的组数。
每组测试数据只有一行，一个正整数S( 1<=s<65536)，表示张三丰计划传授太极拳的总时间。
输出
对每组测试数据：如果你可以帮助张三丰找到这样一组方案，首先输出正整数N，然后输出N个数分别代表分配给这N个弟子各自的时间，数据之间用空格隔开；如果你无法找到这样的分配方案，输出-1.
样例输入
3
1
2
10
样例输出
1 1
-1
3 2 4 4
提示
注意：这样的方案可能有多组，你只需要输出任何一组；另外，本题目中浮点数的精度控制在1e-6.
思路：1.可行性剪枝
2.输出时由小到大，因此int i = x; i <= left; ++i这样美剧，缩小搜索范围
3.sum是double类型就过了，float会TLE。why？？？

#include <iostream>
#include <vector>using namespace std;int s;
bool flag = 0;
vector<int>memo;
double sum = 0;
void dfs(int left, int x){if(abs(sum - 1) <= 1e-6 && left == 0){cout << memo.size();for(int i = 0; i < memo.size(); ++i)cout << ' ' << memo[i];cout << endl;flag = 1;return;}if(sum > 1 || left <= 1)return;if(sum + 1.0/left > 1.0 + 1e-6)return;for(int i = x; i <= left; ++i){memo.push_back(i);sum += 1.0/i;dfs(left - i, i);if(flag == 1)return;sum -= 1.0/i;memo.pop_back();}
}
int main()
{int T = 0;cin >> T;while(T--){flag = 0;cin >> s;if(s == 1){cout << 1 <<' '<< 1 << endl;continue;}dfs(s, 2);if(!flag)cout << -1 << endl;memo.clear();sum = 0;}return 0;
}

2.忍者道具

描述
忍者道具有很多种，苦无，飞镖，震爆弹。L君热衷于收集忍者道具，现在他有N个道具，每个道具的重量分别是C1、C2…CN。现在他想把这N个道具装到载重量为W的工具包里，请问他最少需要多少个工具包？

输入
第一行包含两个用空格隔开的整数，N和W。
接下来N行每行一个整数，其中第i+1行的整数表示第i个道具的重量Ci。

输出
输出一个整数，最少需要多少个工具包。
样例输入
5 1996
1
2
1994
12
29
样例输出
2
提示
对于100%的数据，1<=N<=18，1<=Ci<=W<=10^8。

#include <iostream>
#include <algorithm>
using namespace std;
int n, w;
int item[20];
int ans = 21;
int cab[20];
void dfs(int cnt, int now){if (cnt >= ans) return;if (now == n){ans = min(ans, cnt);}for(int i = 1; i <= cnt; i++){if (cab[i] + item[now] <= w){cab[i] += item[now];dfs(cnt, now + 1);cab[i] -= item[now];}}cab[cnt+1] = item[now];dfs(cnt+1, now+1);cab[cnt+1] = 0;
}
int main()
{cin >> n >> w;for(int i = 0 ;i < n; ++i)cin >> item[i];sort(item, item+n, greater<int>());dfs(0, 0);cout << ans << endl;return 0;
}

3.课程表

描述
现在你总共有n门课需要选，记为0到n-1。在选修某些课程之前需要一些先修课程。例如，想要学习课程0，你需要先完成课程1，我们用一个匹配来表示他们：[0, 1]。给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？

输入
多组数据。每组数据第一行是n和m，n表示有n门课程，m表示有m组依赖关系，接下来的m行是依赖关系的具体信息a b，表示第a门课程依赖第b门课程。

0<=n <=1000，0 <= m <= 4000

两组数据之间可能有空行
输出
对每组数据，能完成输出 True，不能完成输出 False
样例输入
2 1
1 0

2 2
1 0
0 1
样例输出
True
False
提示
示例2解释： 总共有2门课程。学习课程1之前，你需要先完成课程0；并且学习课程0之前，你还应先完成课程1。这是不可能的。
思路见注释

#include <iostream>
#include <vector>using namespace std;
using namespace std;
int m,n;
int visited[1005] = {};
vector<int>q[1005] = {};
bool dfs(int i) {if (visited[i] == -1)//要修return false;if (visited[i] == 1)//已修return true;int len = (int)q[i].size();visited[i] = -1;//这步非常关键，如果后面的搜到前面的，是个矛盾的圈，这里的-1就起到了停止搜索的作用for (int k = 0; k < len; k++) {if (!dfs(q[i][k]))return false;}visited[i] = 1;return true;
}
int main()
{while(cin >> n >> m){bool flag = 1;memset(visited, 0, sizeof(visited));for(int i = 0; i < n; ++i){q[i].clear();}for(int i = 0; i < m; ++i){int a,b;cin >> a >> b;q[a].push_back(b);}for(int i = 0; i < n; ++i){if(!dfs(i)){cout << "False" << endl;flag = 0;break;}}if(flag)cout << "True" << endl;}return 0;
}