POJ查询技巧

POJ指的是pku的Online Judge系统,里面有很多ACM的算法题目。一般来说,做ACM算法题目是为了训练自己的算法能力和兴趣,所以一般都应该自己想自己解决,然后解决完之后才去查询别人用的方法,互相对比一下,看能不能学到一点东西。当然,有时候想了几天几夜都没能想出来的话,看看别人的解法自己再写一次,还是能够学到很多东西。

最简单的方法是在搜索引擎搜一下,毕竟POJ在国内相当出名,很多解题报告可以搜到出来。但是POJ更新得比较快,新的题目的解答不容易找得到。

第一个方法是搜索原题,POJ一般都会给出题目的出处,如果能够搜到测试数据,很容易就明白自己的程序问题出在哪里了。当然,如果这样做的话,算法题的挑战性和趣味性就大打折扣了。而且教新的题目不容易找到测试数据。

后来发现原来POJ每一题的页面的下方,在submit的旁边有一个discuss。在那里其实可以看到很多人的思路,尤其是该题是难题。以前因为一直在sicily,所以不知道原来POJ有这个功能。

然后,还有一个重要的地方是,有些比赛结束后会有Contest Report,比如月赛。进入的地方是主页里的Past Contest,然后点击相应的比赛进去,除了可以看题目,排名和状态外,有些比赛有解题报告看,以前一直不知道,汗。

Advertisements

POJ1014解题

POJ的1014是一题挺有意思的搜索题。题目说有价值为1到6的石头若干,然后每次的数据分别给出它们的数量,要求求出这些石头是否能按价值平均分。比如价值1的石头两块,价值2的石头1块,那么可以平均分。也有很多情况不能平均分。

所以思路就是搜索吧。当然如果总价值本身就是奇数,那么肯定不可以平均分了。但是总价值是偶数,也不一定能平均分。所以就搜索一下这些石头能否刚好凑到总价值的一半,如果可以就能够平均分了,否则不行。

但是题目的规模是每种石头的数量是0到20000,其实大家都知道直接搜索肯定会超时。然后对于这道特殊的题,剪枝的方法更是多种多样。但是我一直想不改进搜索,而是找到小规模的等价问题,从而求解。比如六种价值的石头数量“2,4,0,0,0,0”。那么两边都有一块价值为1的石头,两边都有两块价值为2的石头,刚好完全平分价值。因为我们给出的一组数据有解,而且解的两边有相同的东西,所以容易想到,两边各去掉一块1或各去掉一块2,两边还是相等的,所以可以知道,如果给出一组数据是“0,4,0,0,0,0”还是有解的。

也就是说,我想把可能规模很大的数据化为等价的规模很小的数据,直接搜索求解。但是说得容易,却很难证明其正确性,直到看到网上的一篇分析才知道。但是那篇分析不够严谨和清楚,我严谨地证明一次。

首先,如果原数据无解(不可平分),那么任何一种石头的数量减去2之后,仍然是无解。可以反证,假设减去2后的数据有解,也就是可以等分为两堆,那么每边各添加那种减去的石头一块,那两堆的价值还是相等,就跟原数据不可分矛盾了,因此得证。

然后,如果原数据有解,其中一种石头减去2之后,可能有解,也可能无解,我们很容易就可以举出例子,所以不举例子了。也就是这里,让我觉得很无奈,因为失去等价性,这种方法就没有意义了。但是后来发现,原来在某个数量上而且原数据有解,是可以肯定地得到减2之后也有解的,从而可以找到最小规模的等价数据。下面就介绍。

所以我们现在是假设原数据有解,以价值为6的石头说明问题吧。假设本身原数据的其中一个解,是两边都有6的,那么价值6的石头减2的数据肯定有解。然后如果其中一个解是6全在一边,如果能够把其中一些6交换到右边,那么就是刚才的情况了。然后我们会发现,有时候一定能够交换过去。比如,如果右边有六个5或以上,那么肯定可以把左边的五个6交换过去,因此如果右边有六个5或以上,把6的石头减2也还有解。同理,三个4,两个3,三个2,六个1或以上,都可以使得6从左边交换到右边。然后怎样才能使得右边会至少出现五个6等等呢,要不出现的话,右边最大是5*5 + 4*2 + 3*1 + 2*2 + 1*5 = 45。所以只要左边只要有8个6,那么肯定可以交换过去。

因此,结论是如果价值为6的个数大于8,都能把个数减2,而可分与否的性质和原来不变。因此6的个数如果大于8,偶数的可以等价为6,奇数的个数等价为7。同理,其他价值的石头也有类似的性质,规模减少后就可以直接搜索了。