BZOJ 1977 - [BeiJing2010组队]次小生成树 Tree
2016-08-10
题目地址
描述 小 C 最近学了很多最小生成树的算法,Prim 算法、Kurskal 算法、消圈算法等等。 正当小 C 洋洋得意之时,小 P 又来泼小 C 冷水了。小 P 说,让小 C 求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说: 如果最小生成树选择的边集是 E m E_m E m ......
BZOJ 3881 - [Coci2015]Divljak
2016-07-01
题目地址
描述 Alice 有 n n n 个字符串 s 1 , s 2 , ⋯ , s n s_1, s_2, \cdots, s_n s 1 , s 2 , ⋯ ,......
QTREE 7 - Query on a tree VII
2016-03-18
题目地址 终于刷完了!!
分析 链分治。大综合,前面的都完成了的话,这个应该不难。
代码 // Created by Sengxian on 3/17/16.
// Copyright (c) 2016年 Sengxian. All rights reserved.
// Spoj QTREE VII 链分治(巨坑之后的黎明)
#include &l......
QTREE 5 - Query on a tree V
2016-03-18
题目地址
分析 链分治,不过要注意这个题目由于是求最短路径,而且 没有 边权,所以不用担心走到上面的链之后又走下来,那样如果下面的链有答案的话,只会更长!
代码 // Created by Sengxian on 3/17/16.
// Copyright (c) 2016年 Sengxian. All rights reserved.
// Spoj ......
QTREE 6 - Query on a tree VI
2016-03-18
题目地址
分析 链分治,因为是求和,所以要去重,从什么地方爬上去的,就减什么地方的 m a x L maxL m a x L 。要想清楚,合并的时候什么值该加,什么值不该加。 还有转换颜色的时候,被转换的节点的堆要重新更新,一定不要再次遍历儿子,菊花图会被卡成翔,应该记录两个堆,一个记录同色的,一个记录不同色的,然后 swap......
QTREE 4 - Query on a tree IV
2016-03-18
题目地址
分析 这题是链分治了,某种程度上像最大子段和,也是分治的运用,见 qzc 论文。这题是做后面三题的基础,一定要想清楚! 我是论文
代码 // Created by Sengxian on 3/16/16.
// Copyright (c) 2016年 Sengxian. All rights reserved.
// Spoj QTREE ......
QTREE 3 - Query on a tree again!
2016-03-16
题目地址
分析 还是上树链剖分,线段树里面维护每个节点的颜色,由于每个节点到根节点最多经过 log n \log n lo g n 条轻边,所以我们把到根的路径记下来,然后反着向下找,一旦一个区间的和不为 0,说明有黑点,这时二分(要求点的深度尽量小)去找这个黑点即可,复杂度是 O ( n log 2 n ......
QTREE 1 - Query on a tree I
2016-03-16
题目地址 开始打 QTREE 系列。
描述 给你一个 n ( n ≤ 1 0 0 0 0 ) n(n\le 10000) n ( n ≤ 1 0 0 0 0 ) 个节点的树, 现在要你支持两种操作:
QUERY a b 询问 a a a 到 ......