高度由习惯堆积

分类 OJ:洛谷 下的文章

BZOJ2574 Store-Keeper

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

POI2006 ZAB-Frogs

题目一群青蛙正在摧毁Byteotia所有的庄稼. 一个叫Byteasar的农夫决定使用一种放在田里的奇特的"scarefrogs"来吓跑他们, 所有的青蛙在跳跃过程中都尽量使自己离他们越远越好, 即是让自己离最近的scarefrog越远越好. Byteasar的田是块矩形的土地. 青蛙们跳跃的方向平行于坐标轴并且每次跳跃的距离为1. 一条跳跃路线的scarefrogs-距离为路径上所有点距离...
February 17, 2019

Luogu1120 小木棍

title: Luogu1120 小木棍题目乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过5050。现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。思路这题据说有九种剪枝,我只香到想出了8种。剪枝1:可行的答案显然应该整除木棒的长度和。(显然)剪枝2:根据奇偶性 最终要得到...
February 15, 2019

洛谷P2014 选课(先序遍历优化树形背包)

题目在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有N门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程a是课程b的先修课即只有学完了课程a,才能学习课程b)。一个学生要从这些课程里选择M门课程学习,问他能获得的最大学分是多少?思路各种课程之间的关系显然是树形结构,显然可以用背...