ACM

HDU 5113 Black And White(dfs+剪枝)

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

HYSBZ-1053反质数(搜索)

HYSBZ-1053反质数(搜索)
这个题真是太神奇了,搜索题。首先,打表肯定不行,这么大的数了。然后看了题解,用到了分解质因素的方法。我们可以举例来说明一下。比如12:从树根到叶子节点的乘积都是12的约数,所以12共有6个约数。再者,任何一个数都可以分解成一个由质数相乘组成的数,如:x = 2^x1*3^x2*5^x3......由反质数的性质,有x1>x2>x3>....搜索的意图就很明显了,从2的指数开始搜索... 继续阅读 »
ACM

HDU-1044 Collect More Jewels

HDU-1044 Collect More Jewels
题意:有一个人在地牢里面,现在他得知地牢要GG了,他要在规定的时间内逃出去,但是地牢里面还有很多珠宝,每个珠宝价值不一样,他在出逃的时候想获得最大的价值并且逃出去(如果能逃出去的话)。BFS+DFS同时使用的题,用的数组特别多容易乱。大概就是先用bfs找出起点,宝石,终点这些点之间的距离保存在数组里面,然后用dfs找最大价值的最短路径。题目地址:http://acm.hdu.edu.cn/show... 继续阅读 »
ACM

HDU-1045 Fire Net

HDU-1045 Fire Net
题意:给你一个地图,然后地图上会放置一些炮台,这些炮台会往四个方向发射无穷远,保证多个炮台之间不能被打到,求最大放置的炮台数。其实就是类似于炸弹人游戏一样,不过这里是射程无穷远而已。DFS题,注意数组状态保存以及方向变化。题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1045代码:Memory: 1804 KBTime: 15 M... 继续阅读 »
ACM

CodeForces 690D1-The Wall (easy)

CodeForces 690D1-The Wall (easy)
题目意思大概就是一堵墙,然后有些裂缝了,你需要判断现在有裂缝的墙有多少。一个DFS题目,和油田问题相似。题目:http://codeforces.com/problemset/problem/690/D1代码:Memory: 360 KBTime: 31 MSLanguage: GNU G++ 5.1.0Result: Accepted#include&nb... 继续阅读 »
ACM

2016HUAS_ACM暑假周测8 - C - Mike and Cellphone - CodeForces 689A

2016HUAS_ACM暑假周测8 - C - Mike and Cellphone - CodeForces 689A
        题目意思是有个人的手机掉水里了,他打电话只能靠平时拨号的按键习惯来拨号。请问他按下一串号码后会不会出现重复的情况。        模拟一下就好了,我们可以把他按按键的顺序看成是走迷宫的顺序,记录下来,然后从0-9挨个开始按照... 继续阅读 »
ACM

2016HUAS_ACM暑假周测6 - A - Prime Ring Problem - HDU1016

2016HUAS_ACM暑假周测6 - A - Prime Ring Problem - HDU1016
        题意:给你一个数n,代表有从1-n个整数点可供使用,然后你要用这些数围成一个圈圈,保证每两个相邻的数相加为素数。        思路:DFS,判断后一个与前一个相加为素数,注意最后一个和第一个的特殊情况,把素数打了个表,时间... 继续阅读 »
ACM

集训1|HDU1258-Sum It Up

集训1|HDU1258-Sum It Up
        一个DFS题目,应该说加深了对DFS的理解吧。以前对DFS的理解云里雾里的,今天一看,觉得数组的数值不会被改变吗怎么会输出正确的结果?我是看漏了DFS最重要的一点“return”!他找到正确答案或者超出边界是要return的!!!这样数组就会重新赋值,恍然大悟啊!!!   ... 继续阅读 »
ACM

2016HUAS_ACM暑假集训1-G-Oil Deposits

2016HUAS_ACM暑假集训1-G-Oil Deposits
G - Oil Deposits        连通块问题,和《算法竞赛入门经典(第二版)》里面的油田问题是一样的,利用dfs提高效率,递归一下就好了。DescriptionThe GeoSurvComp geologic survey company is responsible for detecting... 继续阅读 »