搜索例题
今天，孙培轩老师（没听说过），来给我们上了一节公开催眠课，结果看起来跟上次周镇东讲的一样繁琐，没想到就是个纸老虎，讲的是普及组的知识，非常简单喵
由于普通搜索是基础组难度，过于简单，所以这里直讲一道经典例题——小猫爬山喵
对于每只小猫，可以有两类选择喵
- 进入其它已经有猫咪的缆车喵
- 再每一个缆车，去这个缆车
那么，我们可以用一个for 循环枚举每一个已有的缆车，看看能不能进去，可以则进去继续搜索喵，注意后面还需要特别的判断新开一个缆车的情况喵
那么，搜索思路就很清晰了喵，对于每个参数num和cnt，分别表示现在在给第num只猫分配缆车，现在有cnt个已经卖了的缆车喵
接着就枚举每一个已有的缆车，看看猫咪能不能挤进去，能就试一试喵
枚举完后不要忘记，还要考虑新买一个缆车的情况喵
还有，这题需要加上一个剪枝，就是如果现在的费用超过了之前的最小总费用，那么这个方法一定很坏坏~~喵
code喵
（res是用来记录缆车的喵）
void dfs(int num, int cnt){
if(num > n){
ans = min(ans, cnt);
return;
}
if(cnt >= ans) return;
for(int i = 1 ; i <= cnt ; i++){
if(res[i] + c[num] <= w){
res[i] += c[num];
dfs(num + 1, cnt);
res[i] -= c[num];
}
}
res[cnt + 1] += c[num];
dfs(num + 1, cnt + 1);
res[cnt + 1] -= c[num];
}
好了，本题讲解结束，我接下来会控制自己尽量不说“喵”的，喵
折半搜索
折半搜索，和二分查找用着共同的思想
顾名思义，折半搜索，就是把给定的物质折成前后长度相同的两半分别搜索，常用于解决状态空间较大的问题，如组合优化、排列组合等问题。
折半搜索的运用场景
- 子集和问题
- 组合问题
- 排列问题
- 分治类问题
- 状态空间较大的搜索问题
算法特点
- 折半思想体现：
- 将问题分解为两部分处理
- 通过剪枝减少搜索空间
- 排序后可以提前终止不必要的搜索路径
- DFS特点：
- 递归实现
- 需要回溯
- 深度优先探索
- 优化技巧：
- 排序输入数据以便剪枝
- 记录已访问状态避免重复计算
- 提前终止不可能的分支
复杂度分析
- 时间复杂度：通常为 O(2^n) 量级，但通过折半剪枝可以大幅减少实际计算量
- 空间复杂度：O(n) - 取决于递归深度
这种DFS折半搜索技术在算法竞赛和面试中经常出现，特别是在需要穷举所有可能解但又需要高效剪枝的场景中非常有用。
例题讲解
如果数据范围小一点，可以用暴搜和背包过
但是可惜，数据范围特大，背包会MLE，暴搜会TLE
我们可以在暴搜的基础上优化成折半搜索，从而减少时间复杂度，避免时间超限
其实并没有那么难，就是把前后两段分成连个dfs来做，随后随便用一个upper_bound优化即可
code
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 50;
int n, t;
int a[N];
int res;
vector <int> v, v2;
void dfs(int num, int cnt) {
if (num > n / 2) {
v.push_back(cnt);
return;
}
dfs(num + 1, cnt + a[num]);
dfs(num + 1, cnt);
}
void dfs2(int num, int cnt) {
if (num > n) {
int sum = upper_bound(v.begin(), v.end(), t - cnt) - v.begin() - 1;
if (v[sum] + cnt <= t) res = max(res, v[sum] + cnt);
return;
}
dfs2(num + 1, cnt + a[num]);
dfs2(num + 1, cnt);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> t;
for (int i = 1 ; i <= n ; i++) {
cin >> a[i];
}
dfs(1, 0);
sort(v.begin(), v.end());
dfs2(n / 2 + 1, 0);
cout << res << endl;
return 0;
}
也是模板题，和上一题代码没什么区别，只是在记录答案是是res += sum + 1
code
void dfs(int num, int cnt) {
if (num > n / 2) {
v.push_back(cnt);
return;
}
dfs(num + 1, cnt + a[num]);
dfs(num + 1, cnt);
}
void dfs2(int num, int cnt) {
if (num > n) {
int sum = upper_bound(v.begin(), v.end(), t - cnt) - v.begin() - 1;
if (v[sum] + cnt <= t) res += sum + 1;
return;
}
dfs2(num + 1, cnt + a[num]);
dfs2(num + 1, cnt);
}
还是模板题，只是包含了亿点点思维，我们要加的和就是对1~n的高斯求和的值除以 2 ，注意，这里最后得到的值要除以二，因为他是两段子序列，比如1 2 3 4，按理来说答案是1，但是实际输出了2，这是因为只有一个分割就是在把2和3分在一起、1和4分在一起，但是他会检测到这两个子序列，所以要用总和除以二
还有，答案的加法又变成了res += sum
最后注意一点，题目有特殊数据点，可能这 n个数根本没法分割成相同的两端（即所有数的和不是2的倍数），搜索就会出错，要特殊处理
code
void dfs(int num, int cnt) {
if (num > n / 2) {
v.push_back(cnt);
return;
}
dfs(num + 1, cnt + a[num]);
dfs(num + 1, cnt);
}
void dfs2(int num, int cnt) {
if (num > n) {
int sum = upper_bound(v.begin(), v.end(), t - cnt) - lower_bound(v.begin(), v.end(), t - cnt);
res += sum;
return;
}
dfs2(num + 1, cnt + a[num]);
dfs2(num + 1, cnt);
}
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1 ; i <= n ; i++) {
a[i] = i;
t += i;
}
if (t % 2 == 1) {
cout << 0;
return 0;
}
t /= 2;
dfs(1, 0);
sort(v.begin(), v.end());
dfs2(n / 2 + 1, 0);
cout << res / 2 << endl;