搜索 update on 2023/1/15 $(%25/%100)$
Tips：一定一定不要小瞧搜索，搜索也是可以出黑题的
零、前言
想必大家都会搜索吧(默认大家都会)，既然会那我就不讲了吧
今天肯定不讲$dfs,bfs$那些及其简单的搜索，我们讲点其他的。
一、迭代加深搜索
在爆搜的时候，搜索规模是随着搜索深度指数增加的。
为了更快地搜索到最优解，可以想到要让搜索的深度尽可能小，就会用$bfs$减少时间复杂度，但是往往$bfs$不适用于爆搜，或者需要过多的空间。
这是就要请出我们的主角迭代加深搜索了，迭代加深搜索即限定搜索深度$D$进行$dfs$，搜索完深度$D$以内的所有节点后再增大$D$重新搜索直到找到答案。
是不是有点懵，啊对，我一开始也有一点懵，举个栗子就不懵了:
P1763 埃及分数
在主函数从小到大一次枚举最少分数个数，即上文$D$，在$dfs$里判断是否合法若合法输出最小的$D$，否则继续枚举。
int x , y , sz = 1;//sz为最少分数个数，即上文D
int p[] , ans[];
bool flag;//合法为1，不合法为0
int gcd(int x , int y){}
void dfs(int step , int pre){
//step表示当前选到了第几个分数，pre表示前一个分数的分母
if(step > sz){
__________;//更新ans数组
flag = 1;
return;
}
int up = (sz - step + 1) * y * 1. / x;
int down = ceil(y * 1. / x);
//此处up,down的取值下文再解释
for(int i = max(down , pre + 1); i <= up; i++){
p[step] = i;
__________;//修改x,y值
dfs(step + 1 , i);
x = tx , y = ty;//回溯
}
}
int main(){
cin >> x >> y;
int tx = x , ty = y;
while(!flag){
__________;//初始化代码不给了
dfs(1 , 0);
sz++;
}
for(int i = 1; i < sz; i++) cout << ans[i] << " ";
return 0;
}
$tips$:此代码为伪代码，需要稍加更改才可$AC$
下面所说的非常非常关键
$up = (sz - step + 1) * y * 1. / x\quad①$
$down = ceil(y * 1. / x)\quad②$
为了方便理解上述代码中的$up$和$down$，首先我们来化一个式子:
$\frac{x}{y}\ge\frac{1}{a}$
$\frac{y}{x}\le a$
在$①$式中$sz-step+1$表示还有几个数未选完，$y * 1. / x$表示上述的$a$，乘起来就是$a$的最大值
在$②$式中$y * 1. / x$也是上述$a$，向上取整一下就为$a$的最小值了
所以这道题结束了，是不是很简单？其实我也觉得他不是很难，应该评不上紫题难度，最多也只有蓝题那种难度，不能再高了。