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 1017 Packets

题目

源地址:

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

理解

在COJ上有一道一模一样的题目,当时做的时候没有做出来,因为没有考虑好剩余空间的利用。6*6和1*1的情况最为简单,但是其余的情况就分情况考虑了,特别是对于3*3这种情况而言,因为一个箱子正好可以装4个3*3的产品。

Read More

POJ 1657 Distance on Chessboard

题目

源地址:

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

理解

再一次脑洞大开了= =,居然还写了一个normalize函数用来区分是不是可行的走法,其实只要通过abs(x-y)%2!=0即可实现判断斜的方向上是否可以行走了。恩,这是程序设计实践导引上的例题,加上中文,没有什么好讲的。不过需要注意位置没有发生改变时的特殊情况。

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

POJ 2488 A Knight's Journey

题目

源地址:

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

理解

一开始没看懂,看了几遍之后才明白。是给定一个p*q的棋盘,要求计算出是否存在可能性使得骑士走遍整个棋盘,并要求按照字典序排列。这个字典序真的是要我的命,直接导致挂了很多次,还傻傻地去群里面问这道题是不是Special Judge= =。

Read More

POJ 1753 Flip Game

题目

源地址:

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

理解

我一开始的思路是错误的,企图通过正面的方法来找出从当前情况达到全白和全黑的方法,多次尝试之后,发现很难找到一条通用的方法,只能找出几个比较简单的特例。后来才明白过来,应当从全黑或者全白的情况出发,再来判断给定的图是不是其中的一个子集。因为是一个4X4的格子,不难看出,总共的情况只有2^16种。只要一一枚举即可。最后的步数就是这颗树的深度,使用DFS即可实现。

Read More