XUDJY

树

C++(2) CF(32) CSP(3) ICPC补(3) QT(1) 动态规划(3) 数据结构(3) 数论(1) 碎碎念(3) 算法基础(9) 题解(4)

/ 注册

全部文章 / 树（共9篇）

Cf #602 D2 - Optimal Subsequences （01线段树）

我好菜，佬们好厉害。比赛的时候正好是电路实验就错过了啊啊啊啊今天中午补题，大概一个小时A了三道，D2实在想不起来了看别人的代码都是拿线段树写的，（鬼知道我线段树多久没用过了啊啊啊）写到自闭叻。主要就是用线段树二分寻找数组中某位置 x ，满足1 ~ x ...

线段树思维

2019-11-25

0 657

K. Addition Robot（矩阵+线段树）

2019-2020 ICPC, Asia Jakarta Regional Contest 既然要交换AB，那就在线段树中把两种矩阵都存下来好了然后swap( c[ rt ][ 0 ]，c[ rt ][ 1 ] )。 int n,q; char s[MAXN];...

矩阵

2019-10-31

1 522

G. Performance Review(线段树)

2019-2020 ICPC, Asia Jakarta Regional Contest G. Performance Review 题意：第一行三个数n,m,q ，人数，（进行淘汰和替换的）操作次数，询问数（询问前还有一次操作更改操作，而且每次更改会影响到后面）。第二行n...

2019-10-30

0 646

D. Restore Permutation（线段树+思维）

题意：对应每个 i 给出一个数si，代表i之前比ai小的值的和，求原序列。链接：https://codeforces.com/contest/1208/problem/D 对着样例乱猜看出来最后一个0的位置就是1，进一步想到，把1出现的位置之后都减去1，然后从整个序列里再找最右...

思维

2019-10-07

0 554

树剖初识

经常听到大佬说树剖云云，大概学一下。树链剖分树剖通过将整棵树划分为多条重链，将其转换为线性结构，方便我们使用其他数据结构维护这个树的信息。概念：重儿子：对于每一个非叶子节点，它的儿子中子树节点数最大的儿子，为该节点的重儿子轻儿子：对于每...

树剖

2019-09-19

0 771

dfs序，欧拉序

POJ 3321 Apple Tree VJ链接：https://vjudge.net/problem/POJ-3321 先贴上以后补题解。。（咕咕咕一个教训就是树状数组一定要从一开始，一个while(x>=0)死循环了找半天，，，太久不用树状数组了。 ...

dfs序

2019-08-08

0 547

划分树初识

听老师讲课，越来越感觉自己学的太少了啊，，，还有太多东西没学，最近效率太低了。划分树和归并树相似，不过归并树是从有序到无序（）而划分树则是从无序到有序（红色部分代表进入左子树的数值）划分树中每个节点记录两个信息， struct node { ...

划分树

2019-08-08

0 688

线段树练习

昨天上课老师讲尽量把学过的知识点总结一下，，，以后尽量写写博客吧， Vases and Flowers 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4614 看到花瓶只有放花不放花这两种状态，应该很快就可以...

2019-08-02

0 560

Lca几种解决方式（代更）

倍增算法（doubly）初步学习了一下Lca(最小公共祖先)相关的倍增算法。（又称跳表法）可以在线求树中两点的最小公共祖先需要储存信息： // lca //MAXN节点数 int dis[MAXN];//节点到树根距离 //此数组在求两节点距离时使用di...

LCA

2019-07-23

0 747