门户网站直接登录系统,建站公司有哪些服务,外贸网站排名,门户网站制作哪专业一、回溯法
1.回溯法简介
回溯法一般使用 ** DFS(深度优先搜索) ** 实现#xff0c;DFS是一种遍历或搜索图、树或图像等数据结构的算法#xff0c;当然这个图、树未必要存储下来(隐式处理就是回溯法)#xff0c;常见的是通过某种关系构造出的搜索树#xff0c;搜索树一般…一、回溯法
1.回溯法简介
回溯法一般使用 ** DFS(深度优先搜索) ** 实现DFS是一种遍历或搜索图、树或图像等数据结构的算法当然这个图、树未必要存储下来(隐式处理就是回溯法)常见的是通过某种关系构造出的搜索树搜索树一般是排列型搜索树(总节点个数一般为n!级别)和子集型搜索树(总节点个数一般为2^n级别)。 排列型就是每次枚举选哪个子集型就是对于每一个元素选或不选(结果与顺序无关)DFS从起始节点开始沿着一条路径尽可能深入地搜索(一条路走到黑)直到无法继续为止然后回溯到前一个节点继续探索其他路径直到遍历完整个图或树。DFS使用栈或递归来管理节点的遍历顺序一般使用递归。 很多时候DFS和回溯法不必过度区分。
2.排列树图解 求一到三的全排列 如上图中遍历到底部变成了 123如果没有可以继续走的路就返回起点然后判断是否有其他路径可以走遍历完决策树中所有情况后就暴搜出了所有情况。
3.回溯法模板
这是一个排列型搜索树实际上的回溯法比较灵活需要根据题意要求来具体分析。 vis[]表示数字i是否使用过也经常被用于表示某个元素是否使用过。
al]存放结果当dep深度n1时说明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取模1n 10000 样例输入: 5000 样例输出: 976496506 如果直接采用递归来做时间复杂度将接近O(2^n)但是我们会发现有大部分的重复计算比如Fn2]在求F|n]的时候算过在求F|n-1]的时候又被算了一次而F[1]计算次数更多了但它们在重多的时候的结果是相同的所以可以采用记忆化(也叫带备忘录的搜索)。
#include bits/stdc.h
using namespace std;
using lllong 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过程中记录乘积因为乘得越多数字越大当乘积 mul1e6时直接返回(乘积很容易就超过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(1010);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;}
