夏荷浅梦

未归档

读书笔记(1) 题解(6)

/ 注册

全部文章 / 未归档（共30篇）

洛谷P3038 牧草种植Grass Planting

思路：首先，这道题的翻译是有问题的(起码现在是)，查询的时候应该是查询某一条路径的权值，而不是某条边(坑死我了)。与平常树链剖分题目不同的是，这道题目维护的是边权，而不是点权，那怎么办呢？好像有点棘手诶，这是一种非常经典的题型，我们可以发现，一个点最多只有一个父亲！！！那，我们显然就可以用这...

洛谷树链剖分线段树

2018-12-31

0 448

洛谷P4113 [HEOI2012]采花

题目描述萧薰儿是古国的公主，平时的一大爱好是采花。今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。花园足够大，容纳了n朵花，花有c种颜色（用整数1-c表示），且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴！同时，她有一癖好，她不允...

洛谷线段树树状数组

2018-12-31

0 732

洛谷P3258 [JLOI2014]松鼠的新家

题目描述松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有\(n-1\)根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去\(a_1\)，再去...

洛谷树链剖分线段树

2018-12-31

0 450

洛谷P1607 [USACO09FEB]庙会班车Fair Shuttle

题目描述逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市，约翰准备让奶牛们在集市上以车代步。但是，约翰木有钱，他租来的班车只能在集市上沿直线跑一次，而且只能停靠\(N(1 ≤N≤200...

贪心线段树洛谷

2019-01-05

0 484

洛谷 P3128 [USACO15DEC]最大流Max Flow

题目描述 \(FJ\)给他的牛棚的\(N(2≤N≤50,000)\)个隔间之间安装了\(N-1\)根管道，隔间编号从\(1\)到\(N\)。所有隔间都被管道连通了。 \(FJ\)有\(K(1≤K≤100,000)\)条运输牛奶的路线，第\(i\)条路线从隔间\(s_i\)运输到隔间\(t_i\)...

树链剖分线段树洛谷

2019-01-05

0 593

CF438D The Child and Sequence

题意大意给定数列，区间查询和，区间取模，单点修改。 \(n\),\(m\)小于\(10^5\) 题目描述 At the children's day, the child came to Picks's house, and messed his house up. Picks was a...

CF 树链剖分线段树

2019-01-05

0 516

洛谷P2146 [NOI2015]软件包管理器

题目描述 \(Linux\)用户和\(OSX\)用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。\(Debian/Ubuntu\...

洛谷树链剖分线段树

2019-01-05

0 418

SP375 QTREE - Query on a tree

题意大意给定\(n\)个点的树，边按输入顺序编号为\(1,2,...n-1\)，要求作以下操作： CHANGE \(i\) \(t_i\) 将第\(i\)条边权值改为\(t_i\)，QUERY \(a\) \(b\) 询问从\(a\)点到\(b\)点路径上的最大边权有多组测试数据，每组数据以...

线段树树链剖分 SPOJ

2019-01-05

0 501

SP2713 GSS4 - Can you answer these queries IV

题目大意 \(n\) 个数，和在\(10^{18}\)范围内。也就是\(\sum~a_i~\leq~10^{18}\) 现在有两种操作 0 x y 把区间[x,y]内的每个数开方，下取整 1 x y 询问区间[x,y]的每个数的和格式：有多组数据，数据以EOF结束，对于每组数据，输...

线段树 SPOJ

2019-01-06

0 490

洛谷 P2982 [USACO10FEB]慢下来Slowing down

题目描述 Every day each of Farmer John's N (1 <= N <= 100,000) cows conveniently numbered 1..N move from the barn to her private pasture. The pastur...

洛谷线段树 dfs序

2019-03-21

0 461