POJ 2818 Making Change

题目

源地址:

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

理解

感觉很水的一道题,不知道为什么交题的人很少(吐槽一下坑爹的美元换算)。用DFS水掉了,分别从dispenser到pennies来算一遍就OK。我本以为用四个for也能过,但是discuss上面有人说过不了,TLE。有时间我试试看。

Read More

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