搜索结果
查询Tags标签： 儿子，共有 9条记录-
Codeforces600E Lomsat gelral
Codeforces600E Lomsat gelral 题目链接 点我跳转 题目大意 一棵树，1号节点为根，每个结点都有一个颜色，第i个节点的颜色为ci。 如果一种颜色在以x为根的子树内出现次数最多（可以不唯一），称其在以x为根的子树中占主导地位。 你的任务是对于每一个i∈[1,n]，求出以i为…
2022/3/28 23:25:25 人评论 次浏览 -
笛卡尔树
笛卡尔树定义：笛卡尔树是一种二叉树，每一个结点由一个键值二元组 \((k,w)\) 构成。要求 \(k\) 满足二叉搜索树的性质，而 \(w\) 满足堆的性质。一个有趣的事实是，如果笛卡尔树的 \((k,w)\) 键值确定、并且 \(k\) 不相同， \(w\) 不相同，那么这个笛卡尔树的结构是唯一的…
2022/1/19 23:52:12 人评论 次浏览 -
笛卡尔树
笛卡尔树定义：笛卡尔树是一种二叉树，每一个结点由一个键值二元组 \((k,w)\) 构成。要求 \(k\) 满足二叉搜索树的性质，而 \(w\) 满足堆的性质。一个有趣的事实是，如果笛卡尔树的 \((k,w)\) 键值确定、并且 \(k\) 不相同， \(w\) 不相同，那么这个笛卡尔树的结构是唯一的…
2022/1/19 23:52:12 人评论 次浏览 -
Rmp(Mex) & Destiny & 楼房重建（线段树上二分）
Rmq Problem / mex 题面 解析 分块很容易想，不过这道题的需要靠脸卡常。 于是考虑维护一个可持久化值域线段树，树上维护每个值最后一次出现的位置，每个版本作时间维，即表示序列的前 \(i\) 个。 所以我们直接在询问区间的右端点的版本对应的线段树上找到最小的最后一次…
2021/8/17 23:06:08 人评论 次浏览 -
Rmp(Mex) & Destiny & 楼房重建（线段树上二分）
Rmq Problem / mex 题面 解析 分块很容易想，不过这道题的需要靠脸卡常。 于是考虑维护一个可持久化值域线段树，树上维护每个值最后一次出现的位置，每个版本作时间维，即表示序列的前 \(i\) 个。 所以我们直接在询问区间的右端点的版本对应的线段树上找到最小的最后一次…
2021/8/17 23:06:08 人评论 次浏览 -
洛谷P2458题解
题面 和这个题很像，但是本题有一个花费而那一题没有，所以我们要把 \(f\) 数组开大一维。 \(f_{i,j}\) 表示节点 \(i\) 为根的子树在 \(i\) 点是 \(j\) 状态下的最小花费。 状态可以参照我的题解。 那一个题解写得很含糊，这里再讲一遍。 分三种状态：让父亲覆盖自己； 自…
2021/8/14 6:05:45 人评论 次浏览 -
洛谷P2458题解
题面 和这个题很像，但是本题有一个花费而那一题没有，所以我们要把 \(f\) 数组开大一维。 \(f_{i,j}\) 表示节点 \(i\) 为根的子树在 \(i\) 点是 \(j\) 状态下的最小花费。 状态可以参照我的题解。 那一个题解写得很含糊，这里再讲一遍。 分三种状态：让父亲覆盖自己； 自…
2021/8/14 6:05:45 人评论 次浏览 -
浙大PTA 编程题 03-树2 List Leaves (25 分)（c++）
思路： 这道题的意思就是：按照层序来输出叶结点。因为是按照层序，所以遍历树中元素的方式就不同于树的同构了，因为遍历完左儿子1，不能遍历左儿子1的左儿子2，而是要遍历和左儿子1并列的右儿子1，这就需要我们记住左儿子1的父亲，才能找到右儿子1，这样用结构数组来编程…
2021/6/27 22:20:23 人评论 次浏览 -
算法：堆
堆的介绍 堆是一颗完全二叉树，通俗来讲就是除最后一行之外是满的，然后最后一行的节点都在最左边的树。下面就是一颗完全二叉树 而堆在完全二叉树的基础上又增加了一条性质 子节点总是不大于/小于比父亲节点 这样可得出堆顶是最小/大的，堆顶是最小值的堆称为小根堆，堆…
2021/5/4 1:25:11 人评论 次浏览
