POJ 3048 Max Factor

题目

源地址:

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

理解

如果一个数可以通过其他数的各数字位相乘得到,则说这个数具有productivity property。要求求出第i个具有这种性质的数。我们考虑1~9这些数字,显然,我们只要考虑1,2,3,5,7这四个质因数,因为别的数都能通过他们来得到,于是可以得到代码。

Read More

POJ 1014 Dividing

题目

源地址:

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

理解

我的思路非常直接,直接当成一道数学题来解。于是把所有的数都mod2,得到了一个二进制串,然后以这个为基础,开始寻找特例,结果挂的很惨。比如0 3 2 0 0 0,这种情况是在mod2的时候直接就舍去的。说明我这种方法本质上有着缺陷。网上的大牛们大多采用了多重背包的方法,但是有一个人在discuss中提出了mod60的方法。实际上,这个是mod2思路的进一步延伸,也就是解决了0 3 2 0 0 0这种类型的特例。然后再不断的用sum去减,判断最后能都减至0,实质上是用了DFS。

Read More

POJ 1011 木棒

题目

源地址:

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

理解

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

Read More