POJ 1011 木棒

题目

源地址:

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

理解

一开始的想法比较简单,单纯的求和然后找出最短的那根。但是这样的做法有下面的一些问题:第一,最后的棒子的和不能比最短的棒子还短;第二,最后的棒子必须是由给定的棒子合成的。因此只能使用搜索的方法,但是常规的搜索会超时,必须辅以有效的剪枝,以下是参考之后的代码。

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

题目

源地址:

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

理解

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

2211
1111
1111
1122

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

Read More