DFS算法及应用（一）+https://developer.aliyun.com/article/1544412?spm=a2c6h.13148508.setting.19.1fa24f0eaie4S4
回溯
回溯：回溯就是DFS的一种，在搜索探索过程中寻找问题的解，当发现不满足求解条件时，就回溯返回，尝试其他路径。
回溯强调走过的路要打标记，一搬在DFS基础上加一些剪枝策略。
回溯模板求排列
- 排列要求数字不重复，每次选择的数字需要打标记，既vis数组。
- 每次成功时打印path路径。
- 打标记，记路径，然后下一层，回到上一层，清除标记。
def dfs(depth): if depth == n: # 以前还需要判断，但是通过回溯，直接打印就行了 print(path) return for i in range(1, n + 1): if vis[i]: continue vis[i] = True path.append(i) dfs(depth + 1) vis[i] = False # 返回到上一个，即返回到最后一层，因为的depth+1是溢出的一层了 path.pop(-1) n = int(input()) vis = [False] * (n + 1) # 如果是3个数,就是:[][][][] 0这个数不在排列内(索引代表数字) path = [] dfs(0)
VIS数组的索引代表这个数字，值代表这个数有没有被选取，每次通过for循环选择数字，如果该数之前没有，则将其标记并append到path路径中，最后在dfs下边写出回退时的操作（去除标记、弹出path）
回溯模板求子集
- 给定n个数字，求子集。
- 可以针对每个数字，做出选择：选不选。
def dfs(depth): if depth == n: print(path) return path.append(a[depth]) dfs(depth + 1) path.pop(-1) # 执行完递归后依次在此逐个倒退执行 dfs(depth + 1) n = int(input()) a = list(map(int, input().split())) path = [] dfs(0)
崇拜圈
班里N个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己)。在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的右手边。求满足条件的圈最大多少人?
输入第一行，一个整数N(3
def dfs(x, length): vis[x] = length if vis[a[x]] != 0: global ans ans = max(ans, length - vis[a[x]] + 1) else: dfs(a[x], length + 1) n = int(input()) a = [0] + list(map(int, input().split())) vis = [0] * (n + 1) ans = 0 for i in range(1, n + 1): if vis[i] == 0: dfs(i, 1) print(ans)
a列表代表的索引为i的小朋友崇拜的人是几号，同样用vis代表索引为i的小朋友走几步才到。
剪枝
- 在搜索过程中，如果需要完全遍历所有情况可能需要很多时间。
- 在搜索到某种状态时，根据当前状态判断出后续无解，则该状态无需继续深入搜索。
- 例如:给定N个正整数，求出有多少个子集之和小于等于K。在搜索过程中当前选择的数字和已经超过K则不需要继续搜索。
数字排队
数字王国开学了，它们也和我们人类一样有开学前的军训，现在一共有n名学生，每个学生有自己的一个名字a(数字王国里的名字就是一个正整数，注意学生们可能出现重名的情况)，此时叛逆教官来看了之后感觉十分别扭，决定将学生重新分队。排队规则为:将学生分成若干队，每队里面至少—个学生，且每队里面学生的名字不能出现倍数关系(注意名字相同也算是倍数关系)。现在请你帮忙算算最少可以分成几队?
例:有4名学生(2,3,4,4)，最少可以分成(2,3)、(4)、(4)共3队。
输入格式：
第一行包含一个正整数n，表示学生数量。
第二行包含n个由空格隔开的整数，第i个整数表示第i个学生的名字a。
def check(x, group): for y in group: if x % y == 0 or y % x == 0: return False return True def dfs(depth): global ans if len(Groups) > ans: return if depth == n: global ans ans = min(ans, len(Groups)) return for every_group in Groups: if check(a[depth], every_group): every_group.append(a[depth]) dfs(depth + 1) every_group.pop() Groups.append([a[depth]]) dfs(depth + 1) Groups.pop() n = int(input()) a = list(map(int, input().split())) Groups = [] # 构建一个初始的数组和初始的答案 ans = n dfs(0) print(ans)
N边形
假设一个n边形n条边为a1,a2,a3,…- ,an，定义该n边形的值u=ax ag x a3x··× an。
定义两个n边形不同是指至少有—条边的长度在一个n边形中有使用而另一个n边形没有用到，如n边形(3,4,5,6)和(3,5,4,6)是两个相同的n边形，(3,4,5,6)和(4,5,6,7)是两个不相同的n边形。现在有t和n，表示t个询问并且询问的是n边形，每个询问给定一个区间[l,7]，问有多少个n边形(要求该n边形自己的n条边的长度互不相同)的值在该区间范围内。
输入格式：
第—行包含两个正整数t、n，表示有t个询问，询问的是n边形。
接下来t行，每行有两个空格隔开的正整数l、r，表示询问区间[l,r]。
def dfs(depth, last_val, tot, mul): if depth == n: if tot > 2 * path[-1]: # 因为每条边递增 ans[mul] += 1 return for i in range(last_val + 1, 100000): if mul * (i ** (n - depth)) <= 100000: path.append(i) dfs(depth + 1, i + 1, tot + i, mul * i) path.pop() else: break ans = [] * 1000001 t, n = map(int, input().split()) path = [] dfs(0, 0, 0, 1) for i in range(100001): ans[i] += ans[i - 1] # 求前缀和 for _ in range(t): l, r = map(int, input().split()) print(ans[r] - ans[l-1])
