高度由习惯堆积

分类 题型:图论 下的文章

BZOJ2574 Store-Keeper

题目题目地址思路仔细分析一下会发现,其实此题的状态数并不多,只有$100*100*4$种,人的移动是不需要的,也就是说,我们只需要知道当箱子在某一个位置时,人能不能从箱子的一个侧面走向另一个侧面。转化成图论模型也就是说,当一个无向图断掉一个点之后,判断两个点的连通性。这就让人想到了COCI2006/2007 Final的题,这是那道题的一个子问题。首先用$Tarjan$将$dfs$树建立出来...

POI2001 跳舞蝇的教练

题目Byteland一直以奇妙的跳舞蝇而闻名于世。驯养的苍蝇能和着音乐的节奏精确地做每一次飞跃。通常,训练者会在桌上放一排硬币,这些硬币的排列并不按照特定的顺序。每枚硬币上都有一行题字:i→j,i是这枚硬币的编号,j是站在硬币i上的苍蝇下一步应该飞往的硬币编号。训练者在每个硬币上放一只苍蝇,然后开始放音乐。那些苍蝇就跟着音乐的节拍开始跳舞,在每一拍中苍蝇都会直接跳到编号为j的硬币上。在舞蹈中...
February 17, 2019

NOIP2009 最优贸易

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

JOI2014Final 飞天鼠

题目フクロモモンガの JOI 君が住んでいる森にはユーカリの木が N 本生えており,それらの木には 1 から Nの番号がついている.木 i の高さは Hi メートルである.JOI 君が相互に直接飛び移ることのできる木の組が M 組あり,各組の木の間を飛び移るためにかかる時間が定まっている.JOI 君が木の間を飛び移っている間は,地面からの高さが 1 秒あたり 1 メートル下がる.すなわち,J...