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 1753 Flip Game

题目

源地址:

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

理解

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

Read More

POJ 2159 Ancient Cipher

题目

源地址:

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

理解

一开始的理解是按照题目的意思,先进行一次置换加密再进行一次排列加密。置换只要按照规律一个一个替换就OK,排列加密则用到了next_permutation函数。两重for循环,模拟出去全部的加密方法。Coding出来之后提交,WA。然后才开始审视另外的可能性:谁说置换就一定要按照规律来?事实上,的确如此,按照题意,只需要明文和密文字符形成唯一映射就OK。如果还是按照原来的思路,这道水题还真的不水。其实,在加密过程中,有一样东西是不变的,就是各个字符(对应)出现的频率。这样想的话,就简单了,只要统计出每个字符出现的概率,sort排序后,判断两个数组是否完全一致就好~

Read More

POJ 3299 Humidex

题目

源地址:

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

理解

我的理解有误。主要是看input里面都是给定T,D求H的情况,便以为这道题就是用一下公式。没想到这道题还有其他的两种情况。说明不管在怎样的条件下,看题都是至关重要的一步。还有就是在输入输出上,%s%c的区别,值得注意。

Read More