POJ 2714 Random Walk

题目

源地址:

http://poj.org/problem?id=2714

理解

一开始以为只是一道简单的求解最远距离的题目,但是敲完代码之后发现前两个样例过了,最后一个样例数据差距很大。然后仔细读题才发现,题目中给定的正负是不定的= =。一时间没有思路,以为需要使用DP的思想,然后去看了discuss,才明白用枚举的方法列出每一个向量,减少了很大的复杂度,使得问题能在1s之内解决。

Read More

POJ 3048 Max Factor

题目

源地址:

http://poj.org/problem?id=3048

理解

这不是我做过的最简单的题目,但一定是我做起来最逗比的题目。题意很明白,就是输出给定的数里面有最大值质因数的那个。题意中明确说明给定的数的范围是1到20000,然后我就开始机智了,20000的开方约为141,我只要打一个1到150以内所有素数的表,就OK啦~空间换时间,复杂度低得很。开开心心的敲完代码,结果WA了。看了一下discuss,针对一些特例微调了一下代码,结果还是WA。然后就进入坑爹模式,一坑就是一个下午。直到终于忍不住了,去问学长,学长看了一眼,说150到20000之间的质数呢?恍然大悟= =,没有考虑本身也是质数的情况,坑。

Read More

POJ 3194 Equidivisions

题目

源地址:

http://poj.org/problem?id=3194

理解

本以为只要逐个判断每一个数是否有相邻即可,事实上,少考虑了一种情况。 比如下面给出的这种:

2211
1111
1111
1122

根据我原来的思路这种也是good,但其实并不是如此。当然,这个例子并不完备,但用于指出原来思路的漏洞已经够了。正确的思路应当是使用DFS来寻找是否存在独立的区块。

Read More

POJ 1190 生日蛋糕

题目

源地址:

http://poj.org/problem?id=1190

理解

这道题是学长推荐的DFS练习题,一开始没有想明白,为什么这道题是DFS。多次推导之后发现,这道题确实需要用到深度搜索。每次都先确定第一层蛋糕的体积数,然后减去得到剩余的蛋糕体积,如此循坏,最后要保证最后的体积和等于给定的N。因为半径是递增的,所以可以去掉很大一部分无效的搜索。

Read More