DFS
How many ways（记忆化dfs）
Problem Description 这是一个简单的生存游戏，你控制一个机器人从一个棋盘的起始点(1,1)走到棋盘的终点(n,m)。游戏的规则描述如下： 1.机器人一开始在棋盘的起始点并有起始点所标有的能量。 2.机器人只能向右或者向下走，并且每走一步消耗一单位能量。 3.机器人不能在原地停留。 ......
hdu:Oil Deposits（dfs连通图）
Problem Description The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large re ......
hdu:手机的诱惑（dfs+剪枝）
Problem Description 张晨乐在一个古老的迷宫中发现了一个手机，这个手机深深地吸引了他。 然而，当他拾起手机，迷宫开始摇晃，张晨乐能感觉到地面下沉。他意识到：这个手机只是一个诱饵！于是，他不顾一切地试图冲出这个迷宫。 迷宫是一个大小为N*M的矩形，有一扇门，一开始，门是关闭的，并在第 ......
LeetCode题库77.组合——dfs典型解法，递归+回溯+剪枝
class Solution: def combine(self, n: int, k: int): nums=[x+1 for x in range(n)] res,ans=[],[] def dfs(nums:list[int]): if len(ans)==k: ans_copy=ans.co ......
【LeetCode回溯算法#12】二叉树的直径，树形dp的前置内容（使用dfs）
### 二叉树的直径 给你一棵二叉树的根节点，返回该树的 **直径** 。 二叉树的 **直径** 是指树中任意两个节点之间最长路径的 **长度** 。这条路径可能经过也可能不经过根节点 `root` 。 两节点之间路径的 **长度** 由它们之间边数表示。 **示例 1：** ``` 输入：roo ......
在有状态更新的dfs中一定要先更新状态，不然没有更新就查看下一个点了，会有多余运行
例题 P5318 【深基18.例3】查找文献 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) #include<bits/stdc++.h> #include<vector> #include<queue> #define rep(i,a,b) for (int i=a; i<=b ......
DFS 序求 LCA
## 写在前面 学习于 [skip2004](https://www.cnblogs.com/skip2004/p/12240164.html) 和 [Alex-Wei](https://www.cnblogs.com/alex-wei/p/DFN_LCA.html) 的博客。 DFS 序吊打欧拉序 ......
dfs序线段树
# dfs序线段树 [1.树上操作](https://www.ybtoj.com.cn/contest/541/problem/6) ### 思路 遍历一整棵树，记录一下节点 $u$ 的所对应的子树的节点数 $siz_u$ 以及 $dfs$ 序 $dfn_u$ 根据整棵树的 $dfs$ 序，我们可以 ......
DFS
#include<bits/stdc++.h>using namespace std;int a[5][5]={{0,1,1,0,0},{1,0,1,1,1},{1,1,0,0,0},{0,1,0,0,1},{0,1,0,1,0}};int vis[1001]={0};void dfs(int x) ......
DFS 深搜
第一部分 深度优先搜索算法(以下简称DFS)是一种用于遍历（或搜索）树（或图）的算法。 我们构造这样一个图（如图1），并通过C++实现DFS 算法过程 1.从根节点开始 2.放入一个节点（起始时放入的为根节点） 3.如果这个节点是第一次出现，则放入堆栈中 4.判断该节点的子节点是否搜索完成， a.如 ......
「题解注释」CF1707C DFS Trees
[题解 CF1707C【DFS Trees】 - rui_er 的博客 - 洛谷博客 (luogu.com.cn)](https://www.luogu.com.cn/blog/ak-ioi/solution-cf1707c) 耗时：一个小时 代码注释： ```cpp // Problem: C. ......
Hadoop----hdfs dfs常用命令的使用
-mkdir 创建目录 hdfs dfs -mkdir [-p] < paths> -ls 查看目录下内容，包括文件名，权限，所有者，大小和修改时间 hdfs dfs -ls [-R] < args> -put 将本地文件或目录上传到HDFS中的路径 hdfs dfs -put < localsrc ......
20230723牛客round4D题：给出一个大数的所有约数，通过dfs用质因子反向构造约数
# 两个正整数a，b，请问a∗b有哪些因子 #1≤a,b≤1e9 # 求因子的数量并给出所有因子 ### 本题无脑的暴力显然不能过，但用set存数，加上考虑到a*b的所有约数其实就是a的所有约数和b的所有约数分别相乘(核心） # 补充常识：int范围内数的约数个数最多为1600，2e9数的约数个数最 ......
dfs 序
~~看起来是 dfs 序，其实是数据结构。~~ 什么是 dfs 序？就是从根节点出发的 dfs 访问顺序。dfs 序主要用于树。 先给出一棵树： ```cpp 4 1 2 1 3 2 4 2 5 ``` 然后我们从 $1$ 号点出发求出 dfs 序：`1 2 4 5 3`。我们惊奇地发现对于所有子树 ......
luogu P4592 [TJOI2018] 异或 题解【可持久化01trie+LCA+dfs序】
[TOC] # 题目链接 [P4592 [TJOI2018] 异或](https://www.luogu.com.cn/problem/P4592) # 解题思路 读完题目首先发现很像最大异或和问题 但是在树上操作 一开始想到树剖 但是树剖有两个 $\log$ ~~但是树剖常数小~~ 考虑`dfs` ......
搜索（DFS和BFS）
深搜是我最早学的算法，当然现在还没有信手拈来就是了。。。 为了更好地学树和图，只能回来刷搜索了。。。。。我已经搜了一天了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊（疯癫） 首先是今天去刷的八皇后问题，特别经典的搜索题，我记得我有一天深夜学算法就看了这个八皇后问题，其实深搜和广搜没有什么模板，就是纯暴力然 ......
【题解】[ABC312G] Avoid Straight Line（容斥，树上统计，dfs）
# 【题解】[ABC312G] Avoid Straight Line ## 题目链接 [[ABC312G] Avoid Straight Line](https://atcoder.jp/contests/abc312/tasks/abc312_g) ## 题意概述 给定一棵 $n$ 个节点的树， ......
P1219 八皇后 Checker Challenge(深度搜索dfs经典问题+回溯)
题目连接：P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 典型的深度优先搜索的问题 》先付代码再来跟新 java组代码 package PTACZW; import java.util.Scanner; ......
leetcode1448好节点深刻理解DFS+BFS
DFS 没有返回值 max在递归时要慎重用引用，因为在回溯时可能不能改变max； 因为节点的值可能有负数，所以最大值从根节点开始，根节点一定是好节点。 int goodNum=0; void dfs(TreNode* root,int max){ if(!root)return ; if(root- ......
英杰们的蛋糕塔（dfs）（难）
题解： 这道题的关键是找到状态转移方程，从最底层（n）开始，计算上面全部（n, n - 1, n - 2 …… 1）层的总表面积和总体积，从而来确定使表面积最小的S 1 #include <bits/stdc++.h> 2 using namespace std; 3 #define S(r) (( ......
组合的输出 dfs
#include<bits/stdc++.h> using namespace std; int a[101]; int m,n; void s(int k){ int i; if(k>m){ for(i=1;i<=m;i++){ cout<<setw(3)<<a[i]; } cout<<endl; ......
搜索（DFS/BFS）
### 广度优先搜索（BFS） - #### 基本要点： - 利用队列（先进先出） - 一层一层搜索 - 适合于连通块的搜索 - 任何的BFS都可以转化为对树的广搜 - #### 基本流程： - 选择搜索的起点，起点入队，起点标记为已访问 - 队列非空时，循环出队，每次出队将与出队元素连通的且未访问 ......
冷门科技 —— DFS 序求 LCA
- Update on 2023.7.17：该技巧目前已知的最早来源：[skip2004](https://www.cnblogs.com/skip2004/p/12240164.html)。 - Update on 2023.7.17：比较时，取时间戳较小的结点也是正确的，不用记录深度。 DFS ......
dfs优化剪枝
题目链接：D - Peaceful Teams (atcoder.jp) 先看数据范围，肯定是搜索相关 首先想到从第1个人， 第0个队开始的搜索顺序 ，因为这属于内部顺序，所以每次搜索要回溯状态，注意要进行大量剪枝 #include<bits/stdc++.h> using namespace st ......
abc310d <dfs暴搜-分组方案数 / bitmask表示集合+dp>
### 题目 [D - Peaceful Teams](https://atcoder.jp/contests/abc310/tasks/abc310_d) **参考:** https://www.cnblogs.com/legendstane/p/freee-programming-contest ......
BFS和DFS基础
# BFS和DFS基础 ## 搜索简介 搜索是"暴力法"算法的具体实现，是一种吧所有可能的情况都罗列出来，然后逐一检查，从中找到答案的方法。 ### 一般步骤 1. 找到所有可能的数据，并且永数据结构表示和存储。 2. 优化：尽量多的排除不符合条件的数据，以减少搜索空间。 3. 用某个算法快速检索这 ......
击杀黄金蛋糕人马（dfs + 记忆化搜索）（难）
题解： 这段代码实现了一个递归的记忆化搜索算法，用于解决一个求最大蛋糕面积下限的问题。下面解释一下其递归思路： 定义状态 设 ways[w][h][m] 表示当前蛋糕的宽度为 w，高度为 h，已经切了 m 刀时，最大蛋糕面积的下限。 状态转移 对于当前的蛋糕，可以选择竖着切一刀或者横着切一刀。竖着切 ......
Codeforces Round 881 (Div. 3) D - Apple Tree（dfs）
https://codeforces.com/contest/1843/problem/D ``` 题目大意： 一颗树中，每次给定两个结点，每个结点都可以移动到孩子结点，最后可以到达叶子结点， 问我们这两个结点最终移到叶子结点有多少种组合？ （其实就是让求以这两个节点为根的子树的叶子结点个数的乘积） ......
abc070d <简单树上dfs>
[D - Transit Tree Path](https://atcoder.jp/contests/abc070/tasks/abc070_d) ``` // https://atcoder.jp/contests/abc070/tasks/abc070_d // #include #inclu ......