Tree
CF1381D The Majestic Brown Tree Snake
原题链接 膜拜 APJ 大神。 某人说这个题让他联想到“詹天佑”了。 考虑将图画成——给定链在最上方,不在给出链上的点都相当于挂在这条链上某个点上的树。 有两种情况:一种情况是进入一颗树,在其中完成调头,然后原路返回;还有一种情况是进入一颗树,然后出去的时候走向进来的反方向,然后再倒着回去。 第一种 ......
PAT 1099 Build A Binary Search Tree
1099 Build A Binary Search Tree 30分 题目描述:告诉了BST的结点下标关系、结点值,求BST的层次遍历序列。 vector<int> in; // 保存中序序列 int Tree[105][2]; // 保存结点与左右孩子结点之间的下标 map<int,vector ......
vue 项目使用element ui 中tree组件 check-strictly 用法
属性 check-strictly: 在显示复选框的情况下,是否严格遵循父子互相关联的做法,默c认为 false。 默认false,父子关联。 点击父节点,其下子节点全部统一跟随父节点变化,点击子节点,子节点部分勾选时,父节点处于半选状态。 设置为true,严格遵循父子不互相关联。 就是点击全选的话 ......
cf1446C. Xor Tree
https://codeforces.com/problemset/problem/1446/C 断断续续想了挺久的,还发现看错题了。 首先一个显然的结论是不会成环,证明显然。 突破口在于从高位往低位考虑,我们按照最高一位的值分成两类,一类是这一位为0,另一类为1,那么显然在我们不进行任何操作的时候 ......
MySQL系列:索引(B+Tree树、构建过程、回表、基本操作、执行计划、应用)
介绍 https://dev.mysql.com/doc/refman/5.7/en/optimization-indexes.html 作用 优化查询 算法 索引的算法包括 BTree Hash RTree FullText GIS B+Tree结构 BTree查找算法图 B+Tree查找算法图( ......
Educational Codeforces Round 67 (Rated for Div. 2) E. Tree Painting
题目链接 Tree Painting 题面翻译 给定一棵 \(n\) 个点的树 初始全是白点 要求你做 \(n\) 步操作,每一次选定一个与一个黑点相隔一条边的白点,将它染成黑点,然后获得该白点被染色前所在的白色联通块大小的权值。 第一次操作可以任意选点。 求可获得的最大权值 思路 假如说,第一次我 ......
A Tour Through TREE_RCU's Expedited Grace Periods (翻译)
原文:https://www.kernel.org/doc/html/latest/RCU/Design/Expedited-Grace-Periods/Expedited-Grace-Periods.html A Tour Through TREE_RCU's Expedited Grace Pe ......
A Tour Through TREE_RCU's Grace-Period Memory Ordering (翻译)
原文: https://docs.kernel.org/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html August 8, 2017 This article was contributed by Paul E. McKenney I ......
G. wxhtzdy ORO Tree
G. wxhtzdy ORO Tree After (finally) qualifying for the IOI 2023, wxhtzdy was very happy, so he decided to do what most competitive programmers do: try ......
cf1709E. XOR Tree(启发式合并入门)
cf1709E. XOR Tree 贪心是显然的,关键是如何合并两棵子树的信息,可以采用启发式合并。 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<vecto ......
Binary Tree Level Order Traversal
Source Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). Example Given binary tree ......
算法学习笔记(34): CMD Tree
对于 CMD Tree 的理解 原文:# 一种轻量级平衡树 这,EXSGT,感觉很像支持分裂 WBLT,但是相对来说思路很简单。 首先,在原文中说了: 能以均摊 \(\Theta(\log n)\) 复杂度完成一系列区间问题 但是没说的是,这些区间一定是固定的(没有增加的情况) 也就是说,更多的是处 ......
CF1039D You Are Given a Tree
CF1039D You Are Given a Tree 更好的阅读体验 一种神奇套路:对答案根分,根分的依据是链的长度和答案大致是一个成反比的关系。 考虑确定了 \(k\) 怎么做。因为一个点只能在一条链里,所以 dfs 的时候如果能拼成一条链就一定会拼成一条链,不然就把贡献传给父亲继续尝试。 对 ......
k-D Tree小记
k-D Tree 是一种能够 高效处理 \(k\) 维空间信息 的数据结构。 建树 k-D Tree 具有二叉搜索树的形态,二叉搜索树上的每个结点都对应 \(k\) 维空间内的一个点。其每个子树中的点都在一个 \(k\) 维的超长方体内,这个超长方体内的所有点也都在这个子树中。 假设我们已经知道了 ......
CF1891F A Growing Tree
给定一棵以 \(1\) 为根的有根树,支持以下两种操作共 \(q\) 次: 加入一个点; 子树内点权加。 \(q \le 5 \times 10^5\)。 最傻逼的一集,怎么会有这么简单的 d2f。 不难发现每个点存在的时间区间构成时间轴上的一段后缀,于是我们可以将所有操作离线下来,先把完整的树建出 ......
CF1891F A Growing Tree
CF1891F A Growing Tree 更好的阅读体验 有点诈骗。好多人都写的 LCT,但是这题其实连树剖都不需要。提供一个简单的单 \(\log\) 小常数做法。 动态加点是假的,可以离线下来得到最后树的结构,记一下 dfn 序。 一个操作对一个点有可能贡献当且仅当操作在加点之后进行。 所以 ......
数据结构之树(Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树))
赫夫曼树概述 HuffmanTree因翻译不同导致其有多个名字:赫夫曼树、霍夫曼树、哈夫曼树 赫夫曼树又称最优二叉树,是一种带权路径长度 最短的二叉树。 所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。 树的路径长度 ......
Element Plus el-tree懒加载默认选中
百度上试了很多方法,设置default-expanded-keys不生效,最后使用了下面的方法,亲测有效 const loadNode = async (node: Node, resolve: (data: AreaType[]) => void) => { if (node.level 0) { ......
PAT甲级:1174 Left-View of Binary Tree
题目:1174 Left-View of Binary Tree 25分 题解:层次遍历输出每一行最左边的元素。(最开始以为输出部分节点的左子树...想不到思路) using namespace std; #include <iostream> #include <vector> #include ......
CF762F Tree nesting
来一点更清楚的、实现方面的东西。 做法同 这篇,他的实现很优美但略微繁琐了些。 枚举 \(T\) 的形态,发现这个匹配不过是把每个 \(T\) 中当前点的儿子塞进一个 \(S\) 中当前点的儿子内。于是 \(f_{u, v}\) 表示 \(S\) 中 \(u\) 匹配 \(T\) 中 \(v\) 且 ......
CF375E Red and Black Tree
看错题看成只能交换相邻节点颜色了/fn 每次操作交换两个节点颜色,可以转化为统计最终合法颜色序列相比开始,最少有多少个红点变成黑点。 可以考虑一个类似树形 dp 的过程,对于每个节点我们钦定下它会被哪个节点“笼罩”,同时由于黑点数量有限,我们还需要记录下子树内已经用了多少个黑点。 设“笼罩”节点 \ ......
A Tour Through TREE_RCU's Data Structures (翻译)
原文:https://www.kernel.org/doc/html/latest/RCU/Design/Data-Structures/Data-Structures.html December 18, 2016 This article was contributed by Paul E. Mc ......
CF868E Policeman and a Tree
感觉,好自然啊! 想法 dp,想办法分解这个博弈的过程。发现警察会从一片叶子到另一片叶子,在叶子抓住小偷时所有小偷可以全树乱走。因此 dp:\(f_{u, i}\) 表示警察位于 \(u\),全树剩余 \(i\) 个小偷时的答案。 因为两边都绝对理性,小偷在警察离开叶子后不会移动并位于多片叶子上。考 ......
题解 QTREE7 - Query on a tree VII
题目描述 一棵树,每个点初始有个点权和颜色。 0 u :询问所有 \(u,v\) 路径上的最大点权,要满足 \(u,v\) 路径上所有点的颜色都相同。 1 u :反转 \(u\) 的颜色。 2 u w :把 \(u\) 的点权改成 \(w\) 。 \(color_i\in[0,1]\),\(w_i\ ......
CF1572F Stations 题解-Segment Tree Beats
20231025 CF1572F Stations 题解-Segment Tree Beats 吉司机线段树好题!!!CF3400。 传送门 Statement 有 \(n\) 个广播站,第 \(i\) 个广播站高度为 \(h_i\),范围为 \(w_i\)。初始 \(h_i=0,w_i=i\)。广 ......
CF1467E Distinctive Roots in a Tree
突然发现深究一些树上问题还是挺有意思的哈。 显然对于同一种权值的任意两个结点,其两端的部分都是不合法的。 维护两个标记表示子树内均不合法与子树外均不合法即可。但相同权值的点对数量是 \(O(n^2)\) 的,我们要优化这个过程。 发现很多点对都是无用的。DFS 下去,遇到一个 \(x\) 权值的结点 ......
sift+flann(kd-tree)+RANSAC 进行图像匹配
python 3.7.11 opencv3.4.2.16 import numpy as np import cv2 from matplotlib import pyplot as plt def img_match_first(src,dst): # sift特征提取 sift = cv2.xf ......
数据结构与算法 | 二叉树(Binary Tree)
"二叉树"(Binary Tree)这个名称的由来是因为二叉树的每个节点最多有两个子节点,一个左子节点和一个右子节点。其中,“二叉”指的是两个,因此“二叉树”表示每个节点最多可以分支成两个子节点。 ......
CF1003E Tree Constructing
很trivial的构造题 首先上来判掉一些显然无解的情况,然后考虑既然最后直径长为\(d\)那么不妨先搞一条长度为\(d\)的链来 考虑在链上接一些点使得直径不会变长,对于链上的某个点,它最多能接上的链的长度就是它到两个端点距离的最小值 不妨设计递归函数求解,设solve(x,dis,lim)表示在 ......
CF723F st-Spanning Tree
小清新贪心+分类讨论,因为边的数组开小了WA了好久…… 首先我们贪心地选出不包含\(s,t\)的边,用这些边尽量地将除了\(s,t\)外的\(n-2\)个点连通 接下来考虑每个连通块,由于题目保证图初始连通,因此只有三种情况,即要么其中仅有和\(s\)相连的边;仅有和\(t\)相连的边;或者同时有向 ......