Category Archives: 分治

HDU 4670 Cube number on a tree (树分治)

给出一棵树,书上每个点有点权,这些点权都是有1~k个已给的质数构成的。树上的一条路径的权值定义为路径经过的点权 …

CodeForces 293E Close Vertices (树分治,treap)

计算上树满足条件的点对u和v:u到v的边数 <= l,u到v的边权和 <= w 分治,对当前rt为 …

HDU 4918 Query on the subtree (树分治,BIT)

给出一棵树,两种操作:1. u x 将点u的权值改成x;2. u d 计算距离点u不超过d的点的权值和 先不考 …

HDU 5111 Alexandra and Two Trees (树链剖分,主席树)

给出两棵树,计算第一棵树链条[u1, v1] 和 第二棵树链条[u2, v2]的顶点颜色交集的大小。保证同一颗 …

HDU 5936 Difference (暴力,tow points)

输入k和x,计算有多少y满足条件。 不妨分析,是可以发现y最多只会有10位数字,那么 考虑将位折半,分别计算前 …

Codeforces 716E Digit Tree (树分治,数论)

一棵树,定义f(u, v)表示u到v的路径经过的边数字构成的数字,例如u – v经过的边权2,3, …

HDU 5808 Price List Strike Back (分治,dp)

有n个物品,每个物品都一个价值vi,并且要买到这个物品需要走di的距离,现在给出询问[li, ri], ci, …

Codeforces Round #362 (Div. 1)

A – Lorenzo Von Matterhorn 给出n个点的树(n <=1e18),i …

HYSBZ 1492 货币兑换Cash (cdq分治)

题目特别复杂,化简后的题意:有n天,每天的A股和B股能换成ai和bi的人民币,求一个最大的fi使得fi / b …

HYSBZ 3110 K大数查询 (cdq分治)

有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入 …