高度由习惯堆积

分类 OI:NOIP 下的文章

February 17, 2019

NOIP2016 蚯蚓

题目题目链接大意是给你一些线段,每一次都取出最长的那一段,按比例分成两个线段,再放回去,同时其他的线段都增加一个长度。问你每次拿出来的那个线段长度是多少,后来$m$此操作后的序列是什么样的。数据范围:思路NOIP2016的题切分真的是很多。。先来看看如何优雅地切分。首先对于$m<=150000$的这些点,可以直接用优先队列跑。 65分!这里的思考点只有一个:对于每次所有线段都增加一个...
February 17, 2019

NOIP2015 运输计划

题目公元 2044 年,人类进入了宇宙纪元。L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,...

NOIP2012 疫情控制

题目H 国有 n 个城市,这 n 个城市用 n-1 条双向道路相互连通构成一棵树,1 号城市是首都, 也是树中的根节点。H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境 城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境 城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是, 首都是不能建立检查点的。现在...
February 17, 2019

NOIP2009 最优贸易

题目链接思路tarjan缩点法。对于一个强联通分块来说,内部形成了环,所以可以在其中的任意一点购入,任意一点售出,而其他的就需要考虑到达的顺序。我们可以记录每个强联通分块中的最小值,最大值。缩完点之后,原图就变成了DAG,便可以使用动态规划求解。注意题目中还有要求1,n这两个点必须要到达,所以要先用一遍bfs求1可以到达的点。在转移的顺序上,要注意每个点max,min值的更新,必须等到它的入...