Category Archives: 数据结构

ACdream 1103 瑶瑶正式成为CEO (树链剖分,费用流)

一颗n个点的有向边树,这个基础上添加了m条有向边,变成一个DAG。每条边都有ai, bi, ci, di,di …

HDU 5992 Finding Hotels (kd-tree)

平面n个点,每个点有一个权值,若干询问计算距离(x, y)最近并且权值<=c的点的个数。 将询问和点根据 …

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]的顶点颜色交集的大小。保证同一颗 …

CodeForces 477D Dreamoon and Binary (dp,后缀数组)

给出一个目标二进制串,初始是n=0(十进制),有两种操作:1.n = n + 1;2.在之前输出的二进制串末尾 …

CodeForces 484E Sign on Fence (二分,主席树)

给出一个由n块木板构成的栅栏,每块木板的高度hi,有m个询问,l, r, w,计算第l块到第r块栅栏之间能放长 …

CodeForces 480E Parking Lot (线段树,dp)

一个N * M的矩阵,里面有.和X,给出若干询问,询问将(x, y)位置变成X,求剩下部分的矩阵由.构成的最大 …

HDU 4117 GRE Words (AC自动机,dp,线段树)

给出n个字符串,以及格子的权值,按照顺序取出若干个字符串,要去前一个字符串是后一个字符串的子串。计算最大权值和 …

UVALive 6495 (AC自动机,高斯消元)

一个硬币,正面用T表示反面用H表示,现在两个人各自猜了一个长度是L的序列,序列每个元素表示正面还是反面,现在硬 …