ACM

HDU 5113 Black And White(dfs+剪枝)

HDU 5113 Black And White(dfs+剪枝)
题目意思很好懂,给你一个矩阵,然后给你刚好矩阵这么大小的颜色,颜色有很多种,加起来肯定等于矩阵大小。问能否放置颜色使得相邻颜色之间没有相同的颜色。明显的dfs题,但是直接dfs铁定超时,所以就得剪枝,比赛的时候想到了剪一半数量,但是觉得不够就没试,然后发现剪一半能过。。。剪一半,每次dfs之前循环一遍所有颜色数目,剩下的格子数量除以2向上取整数,每个颜色都得小于这个数,不然肯定会有相邻相同的颜色。... 继续阅读 »
ACM

BZOJ 3211 花神游历各国(线段树)

BZOJ 3211 花神游历各国(线段树)
题意:就是中文,都能看懂。看到区间很大,肯定得上线段树。不过这里直接上线段树肯定还是TLE,所以得用一种类似于剪枝的方法,当一个数多次开根号之后肯定是1了,所以一旦为1就不要往下更新?题目地址:http://www.lydsy.com/JudgeOnline/problem.php?id=3211代码:Memory: 7552 KBTime: 1976 MSLanguage:&... 继续阅读 »
ACM

集训1|HDU1010-Tempter of the Bone

集训1|HDU1010-Tempter of the Bone
        DFS。有一条狗走迷宫,需要在时间T内走出迷宫。N,M为迷宫的大小。直接DFS会超时,得剪枝,神奇的剪枝之后就不会TLE了,而且不同的剪枝优化的时间效率是不一样的,我主要参考了两个,虽然效率都不是很高,但是容易理解吧。       &... 继续阅读 »