ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共5篇）

P3938 斐波那契

思路脑子还真的是好东西，自己太笨了容易发现父亲节点和儿子节点的关系儿子节点大于父亲节点儿子节点和父亲节点之差为斐波那契数，且斐波那契数为小于儿子节点的最大的一个 1e12中有60左右的斐波那契数，打出表来查找就好了，深度不超过60 代码 #include <iostream>...

lca 数学数论

2018-10-30

0 458

P4556 [Vani有约会]雨天的尾巴

目录思路优化过程中的问题/疑问错误代码思路每个节点维护一课线段树(当然是动态开点) 线段树的作用是统计这个节点有多少种粮食型号，以及最多的粮食型号然后树上差分，u和v点 +1，lca(u,v)和f[lca(u...

线段树线段树合并数据结构 ST表 lca 差分

2018-12-10

0 464

luogu P2633 Count on a tree

思路强制在线--主席树以1为root建主席树 (就是在树上建树，差不多) rt[i]就是1到i的路径上的一棵树的root 其实我感觉，主席树之间的运算差不多于加减类似lca的运算 root(1到x)+root(1到y)-root(lca）-root(fa[lca]) 查询他们的第k小就OK ...

数据结构-主席树 lca

2018-12-12

0 462

CF1062E Company

CF1062E Company 链接 cf luogu 题目大意给定一颗树，有若干个询问，每个询问给出 l，r，要求编号为 ll~rr 的点任意删去一个之后剩余点的 LCA 深度最大，输出删去点的编号和 LCA 的最大深度思路一堆点的lca就是dfs序列的最大和最小的lca 因为只...

lca 数据结构-主席树线段树

2019-04-28

0 521

P4211 [LNOI2014]LCA LCT

P4211 [LNOI2014]LCA 链接 loj luogu 思路多次询问\(\sum\limits_{l \leq i \leq r}dep[LCA(i,z)]\) 可以转化成l到r上的点到根的路径+1 最后求一下1到z的路径和就是所求区间\([l,r]\)是可以差分的离线直接求...

LCT lca

2019-06-02

0 606