高度由习惯堆积

分类 算法:树形dp 下的文章

August 20, 2019

[国家集训队] Crash 的文明世界

题目题目链接Pre$$ m^n=\sum_{i=0}^{m}{\begin{Bmatrix}n\\i\end{Bmatrix}}C_m^i*i!\\ $$Part1$$ ans_x=\sum_{i=0}^{n}dis(i,x)^k\\ =\sum_{i=0}^{n}\sum_{j=0}^{dis(i,x)}{\begin{Bmatrix}k\\j\end{Bmatrix}} C_{dis(i...

POI2001 跳舞蝇的教练

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

NOIP2012 疫情控制

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

NOI2006 网络收费

题目网络已经成为当今世界不可或缺的一部分。每天都有数以亿计的人使用网络进行学习、科研、娱乐等活动。然而,不可忽视的一点就是网络本身有着庞大的运行费用。所以,向使用网络的人进行适当的收费是必须的,也是合理的。MY 市NS中学就有着这样一个教育网络。网络中的用户一共有$2N$个,编号依次为$1,2,3,⋯,2N$。这些用户之间是用路由点和网线组成的。用户、路由点与网线共同构成一个满二叉树结构。树...
February 17, 2019

HDU4411 Arrest

题目有n个城市,构成一棵树。现在有一些罪犯越狱,需要安排警察抓捕。罪犯的位置不确定。 求安排最少的警察,一定能抓到任何可能下的罪犯。只有警察和罪犯在同一点上就能抓住,无论在城市中,还是在路上。警察可以守在某个点,或者移动!罪犯也可能不动,或者移动!思路换句话而言,对于每一个路口,一定要有一个警察堵住,剩下的警察前去抓捕罪犯,或者一个警察顺着这个路口抓捕到所有的罪犯。感性的来看,对于一个分叉来...