(蓝桥杯C/C++)——搜索

一、回溯法

1.回溯法简介

回溯法一般使用 ** DFS(深度优先搜索) ** 实现，DFS是一种遍历或搜索图、树或图像等数据结构的算法，当然这个图、树未必要存储下来(隐式处理就是回溯法)，常见的是通过某种关系构造出的搜索树，搜索树一般是排列型搜索树(总节点个数一般为n!级别)和子集型搜索树(总节点个数一般为2^n级别)。
排列型就是每次枚举选哪个，子集型就是对于每一个元素选或不选(结果与顺序无关)DFS从起始节点开始，沿着一条路径尽可能深入地搜索(一条路走到黑)，直到无法继续为止，然后回溯到前一个节点，继续探索其他路径，直到遍历完整个图或树。DFS使用栈或递归来管理节点的遍历顺序，一般使用递归。
很多时候DFS和回溯法不必过度区分。

2.排列树图解

== 求一到三的全排列 ==

如上图中，遍历到底部变成了 123，如果没有可以继续走的路，就返回起点，然后判断是否有其他路径可以走，遍历完决策树中所有情况后，就暴搜出了所有情况。

3.回溯法模板

这是一个排列型搜索树，实际上的回溯法比较灵活，需要根据题意要求来具体分析。
vis[]表示数字i是否使用过，也经常被用于表示某个元素是否使用过。

al]存放结果，当dep深度=n+1时说明n层都已经算完了，直接输出结果。

子集型搜索树模板结构类似，就是在往下走时候只有两条边，表示“选或不选当前这个元素”

//求1~n的全排列
int a[N];
bool vis[N];
void dfs(int dep)
{
   if(dep == n+ 1)
    {
       for(int i = l;i <= n; ++ i)
        cout << a[i]<< ' ';
        cout <<'\n';
        return;
     }
    for(int i = 1;i <= n; ++ i)
    {
    //排除不合法的路径
    if(vis[i])continue;
    //修改状态
      vis[i] = true;
      a[dep] = i;
    //下一层
     dfs(dep + 1);
     //恢复现场
      vis[i] = false;
       //a[dep] = 0 可以省略
       }
  }

二、记忆化搜素

1.记忆化介绍

就是将搜索过程中会重复计算且结果相同的部分保存下来，作为一个状态，下次访问到这个状态时直接将这个子搜索的结果返回，而不需要再重新算一遍。
通常会使用数组或map来进行记忆化，下标一般和dfs的参数表对应。
注意使用记忆化需要保证重复计算的结果是相同的，否则可能产生数据失真。

2.斐波那契数列

例题:设F[1]=1,F[2]=1,F[n]=F[n-1]+ F[n-2]，求F[n]，结果对1e9+ 7取模1<=n <= 10000
样例输入:
5000
样例输出:
976496506
如果直接采用递归来做，时间复杂度将接近O(2^n)，但是我们会发现有大部分的重复计算，比如Fn2]在求F|n]的时候算过，在求F|n-1]的时候又被算了一次，而F[1]计算次数更多了，但它们在重多的时候的结果是相同的，所以可以采用记忆化(也叫带备忘录的搜索)。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll p = 1e9 + 7;
const int inf = 1e9, N = 1e5 + 3;
ll dp[N];
ll f(int n)
{
    if(n<= 2)return 1;
    if(dp[n]!= -1)return dp[n];
    return dp[n]= (f(n - 1)+ f(n - 2))% p;
}
int main()
{
memset(dp, -1,sizeof dp);
int n;
cin >> n;
cout <<f(n)<< '\n';
return 0;
}

三、剪枝

1.剪枝介绍

其实就是将搜索过程当中一些不必要的部分直接剔除掉，因为搜索过程构成了一棵树，剔除不必要的部分，就像是在树上将树枝剪掉，故名剪枝。剪枝是回溯法的一种重要优化手段，方法往往先写一个暴力搜索，然后找到某些特殊的数学关系，或者逻辑关系，通过它们的约束让搜索树尽可能浅而小，从而达到降低时间复杂度的目的。
一般来说，剪枝的复杂度难以计算。

2.代码例题-特殊的三角形

假设一个三角形三条边为 a、b、c。定文该三角形的值p= axbx c。现在有(个间问，每个词问给定一个区问,，同有多少个三条边都不相等的三角形的值，在该区同范围内。
== 解题思路 ==
不妨规定我们构造出的3元组是递增的，那么在搜索过程中我们就可以通过计算得到当前这个位置的上限(剪枝的关键)dfs过程中记录乘积，因为乘得越多数字越大，当乘积
mul>1e6时直接返回(乘积很容易就超过1e5，数字较大时层数就两三层)。
同时还能记录一下n-1条边的长度和sum，最后一条边必须小Fsum。
最后用前缀和快速进行区间查询。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
int cnt [N], prefix[N];
void dfs(int dep, int st, int mul, int sum)
{
   //剪枝
    if(mul > 1e6)
    return;
    if(dep =4)
    {
       cnt[mul] ++;
       return;
     }
     int up = pow(1e6 / mul, 1.0 / (4 - dep)) + 3;
     for(int i = st + 1;i < (dep == 3 ? sum : up);++i)
     {
        dfs(dep + 1,i, mul + i, sum + i);
      }
 }
 int main()
 {
   dfs(1，0，1，0);
    for(int i = 1; i <= 1e6; ++i)
    prefix[i - 1]+ cnt[i];
    int q;cin >> q;
    while (q --)
    {
      int l,r;
      cin >> l >>  r;
      cout << prefix[r]- prefix[i - 1] << '\n';
      }
      return 0;
 }