Meul

分类

11eyes的算法笔记(4) ACM(1) Atcoder(14) BFS(1) codeforces(38) DFS(2) dp(3) ICPC(1) sublime text 3(1) 容斥(1) 未归档(10) 模拟(1) 洛谷(2) 牛客(26) 牛客题霸(1) 题解(75)

/ 注册

TA的专栏 13篇文章 1人订阅

11eyes的每日一题

3篇文章 852人学习

11eyes的排位日记

10篇文章 946人学习

0篇文章 0人学习

全部文章（共7篇）

树的直径

之前写过一篇学军信友队趣味网络邀请赛 B.齐心抗疫，那篇文章中讲述了一种通过两次dfs就足以求得树的直径的方法，今天来学习另一种方法求树的直径——树形DP。定义树的直径：若树上两点u,vu,v间的最短路径最大，那么该路径的长度称为树的直径。（可以存在多条）区别两者的复杂度都是方法1：简洁方便...

树树的直径数据结构

2020-09-17

0 1110

K叉哈夫曼树

定义：哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。 K叉哈夫曼树：哈夫曼树的构造方法是贪心的每次选最小的几个节点构造。当的时候需要预处理一下，因为可能最后一步合并操作的点数不到K个节点，这样的话就不是最优的了。预处理方法：当时：加入个权重为0的虚拟节点。将个节点先合并为1个节...

二分 K叉哈夫曼树数据结构

2020-09-17

0 1108

NC19427 换个角度思考

Question 给定一个长为的数组，对其求次询问，每次求。 Solution 离线+树状数组这里该如何用树状数组表示是个问题，一开始我的想法是多开树状数组，显然必TLE，这里要结合离线。我们把输入的数组，存为形式，其中放值，放对应的位置。我们将输入的询问放入中，按照询问的从小到大排序。这样排序的好...

树状数组数据结构

2020-05-03

0 720

NC50940

题意输入奇数个数的时候输出此时输入的数的中位数。思路建立一个大根堆和一个小根堆。（构成一个对顶堆）序列中从小到大排在的整数存储在大根堆中。序列中从小到大排在的整数存储在小根堆中。若一个堆中元素过多，则将其堆顶元素插入到另一个堆中即可。中位数为堆中元素为奇数个数的堆的堆顶。 #inclu...

对顶堆堆数据结构

2020-04-17

0 579

NC14248

NC14248 题意给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同思路 DFS 树数据结构这道题和CF1339D十分相像，有兴趣的可以做一下。把题意转化为给你一颗n个结点的树，树上所有的边权值为1，求树...

DFS 树数据结构

2020-04-14

2 774

NC13886

NC13886 题意给你一颗n(偶数）结点的树，将其分为n/2对，求所有对数相连的路径之和最小为多少？思路 DFS 数据结构既然是图论那就先画图吧左图由于以2号结点为根节点的子树结点数(包括其自身)为3（奇数），那么显然这棵树上一定有个节点要从树外找一个节点相连，那么必须要经过2号结点与其父节点...

DFS 数据结构

2020-04-02

0 493

NC82B

NC82B 题意给你一个长为n的序列a和一个常数k有m次询问，每次查询一个区间内所有数最少分成多少个连续段，使得每段的和都 <= k如果这一次查询无解，输出"" 思路预处理前缀和 ST表分两种情况考虑：输出"" ，这种情况，用ans数组维护是否范围内存在的情况。输出范围内所有数最...

ST表数据结构

2020-03-31

3 794