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 到 ......