搜索结果
查询Tags标签： depth，共有 71条记录-
CF1702G2 Passable Paths (hard version)
Passable Paths (hard version) 给出一棵大小为 \(n\) 的树，\(q\) 次询问，每次给出一大小为 \(m\) 的点集，判断是否存在一条链覆盖这些点，注意这条链可以经过其他点。\(n,\sum m \leq 2\times 10^5\) ，\(q \leq 10^5\)。SOLUTION1: 虚树 由于 \(q\) 次询问的 \(\sum …
2022/9/4 23:25:29 人评论 次浏览 -
【重要】LeetCode 662. 二叉树最大宽度
题目链接 注意事项 根据满二叉树的节点编号规则：若根节点编号为 u，则其左子节点编号为 u << 1，其右节点编号为 u << 1 | 1。 一个朴素的想法是：我们在 DFS过程中使用两个哈希表分别记录每层深度中的最小节点编号和最大节点编号，两者距离即是当前层的宽度…
2022/8/28 6:23:59 人评论 次浏览 -
图论-虚拟节点分层建图
图论-虚拟节点分层建图 Nya图最短路 题目链接:Virtual Judge Acwing题意: 题解:\(a,b\)连一个\(w\)的边,是正常操作,这里有一个重要操作是\(a\)层和\(a+1\)层能直接传送,如果这里使用笨笨的建图方式,那么时间复杂度就是\(O(n^2)\),时间复杂度太高,不太行.这里有一个聪明的…
2022/8/4 6:25:39 人评论 次浏览 -
LCA（树上倍增）
https://www.luogu.com.cn/problem/P3379链式前向星存边 fa[i][j] 代表从i结点向上找 2^i 代的父亲，（i=0代表真父亲） dfs从根结点开始fa[now][i] = fa[fa[now][i - 1]][i - 1];代表当前结点的第2^i代父节点是当前结点2^(i-1)父节点的2^(i-1)代父节点，然后再对其连接到…
2022/7/31 23:42:40 人评论 次浏览 -
centos7提示cannot create temp file for here-document: No space left on device解决方案
一、使用 df -h 命令查看，发现/根目录的剩余空间为0。总共系统盘容量才50G。 可见 /dev/mapper/centos-root 目录 也就是/根目录 空间已使用完毕 二、使用 cd / && du -h -x --max-depth=1查看哪个目录占用过高，对于过高目录中的内容适当删减文件 var目录占用过…
2022/7/14 5:20:33 人评论 次浏览 -
仓鼠找 sugar
仓鼠找 sugar LCA SCUACM2022集训前训练-图论 - Virtual Judge (vjudge.net)首先要观察出一个结论：若 a - b 的路径与 c - d 的路径相交，设 a, b 的 LCA 为 x; c, d 的 LCA 为 y 则有 x 在 c - d 路径上 或 y 在 a - b 路径上如何判断一个点是否在一条路径上： 可观察到…
2022/5/25 23:22:40 人评论 次浏览 -
「CTSC2018」暴力写挂
emmm感觉就是通道的弱化版，就是第一步要想到description 给两棵树，\(T\)和\(T\)，求对于所有\(x\),\(y\)，\(depth(x)+depth(y)-(depth(lca(x,y))+depth(lca(x,y)))\)的最大值。 solution 两个lca不好处理，考虑把第一个转化为距离。 即：\(\frac{1}{2} *(depth(x)+dept…
2022/4/29 23:43:54 人评论 次浏览 -
【递归/dp】Acwing1243.糖果(IDA*+步调函数/状态压缩+01背包)
题目题解 动态规划 用二进制表示每种味道尝了没有，如：一共有五种味道，吃了前三种——00111，吃了五种——11111 每包糖果都可以选或不选 dp(i,j) i代表前i包糖果, j代表所能到达的状态（吃了几种种味） 其实就是01背包问题 dp[i-1][j & (~w[i])]+1 意味着：选这包糖…
2022/4/19 23:13:44 人评论 次浏览 -
TencentOS_Tiny 任务栈使用率(检测任务栈最大使用深度)
目录TencentOS_Tiny 任务栈使用率API调用在CONFIG.h中使能在任务中调用源码分析任务创建时对任务栈进行了初始化检测任务栈最多使用字节数 TencentOS_Tiny 任务栈使用率 在使用rtos时需要给任务分配合适大小的任务栈，任务运行时所占用的任务栈大小由整个任务所使用的临时…
2022/4/15 7:14:11 人评论 次浏览 -
树上算法01-倍增LCA/Trie
树-相关算法 定义任意两个节点之间只有唯一一条路径的无向图\(n\)个节点，\(n - 1\)条边建树方法 链式前向星(提供边的信息) //存储 struct edge{int to;int pre; }e[ll]; //加边 void add(int x, int y){e[++cnt].to = y;e[cnt].pre = last[x];last[x] = cnt; } //遍历 f…
2022/3/30 20:19:38 人评论 次浏览 -
Acwing 170. 加成序列(迭代加深算法)
170. 加成序列 - AcWing题库 以1开头以n结尾，且每个数是前面任意两数之和的序列的最短长度 这里迭代加深的层数实际上就是序列的长度，由于求的是最短长度，正好就是迭代加深的目的（解在比较浅的层）在处理第u个数时，从前u-1个数找两数之和，由于序列是递增的，…
2022/2/20 14:26:35 人评论 次浏览 -
leetcode算法111.二叉树的最小深度
2022/2/20 12:28:00 人评论 次浏览 -
LeetCode 111. 二叉树的最小深度*
基本思想： 广度+dfs可破； 但是注意一下官方的自底向上的思想，不止一次出现过； 自己想了一种判断深度提前剪枝； 具体代码： 提前剪枝： /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* …
2022/2/10 23:48:35 人评论 次浏览 -
LCA-最近公共祖先 向上标记法、倍增法、Tarjan
LCA 向上标记法 时间复杂度 O(n∗m)O(n*m)O(n∗m) 如果两个结点不相同，就将较深的结点向上移动，直到移动到相同结点，那么该结点即为公共祖先结点。 代码 //预处理每个结点的深度，以及结点的父结点的编号 void dfs(int u, int father){depth[u]=depth[father]+1;fa[u]=…
2022/2/7 23:12:51 人评论 次浏览 -
寒假：Day25
Day25 最近公共祖先问题(LCA)1172. 祖孙询问 - AcWing题库 LCA模板题 #include<bits/stdc++.h> using namespace std; const int N = 40010, M = 2 * N;int n, m; int h[N], e[M], ne[M], idx; int depth[N], fa[N][16]; // depth存每个节点的深度，fa存倍增往前走2…
2022/2/2 23:44:46 人评论 次浏览
