第一次参加周赛

在中大计算机系几年了,以前一直对ACM没什么好感。不过现在觉得ACM还不错,所以就试一试周赛的感觉。这次是晚上6点到10点,无奈因为开会,只能8点才开始。不过好在都是简单题(起码前面几道是),而且都是做过的或者差不多的,直接找以前的源程序改一下交了,结果还不错,一个小时可以Accept了3题。然后人品开始降低了,见到一题简单题,但是用了笨拙的方法,最后改了提交,却提示“Out of the contest”。郁闷的是,这道题也是简单题,却占了一个小时。看来经验还是很重要,而且我还有很多算法没学会。

这次印象最深的是周赛的1000。是一道简单的把输入的数据排序的题,敲的时候想尽量快,所以保存在一个结构体数组,再快速排序,结果真的一次就Accept了。所以本来印象不深,但是后来结束后重新敲一遍的时候,而且是用二叉树一边输入一边排序的时候,却提示“Wrong Answer”,试了很久,放弃了。基本排除了程序结构错误的可能,可能是规模太大的时候malloc返回了NULL吧,不知道呢。

然后昨天中午的时候,POJ也有一个在线比赛,是“World Final Warmup”。然后试了试,果然人品不错,目标是做一题,因为很想睡觉,结果选了A,是经典Joseph问题,而且问的是最后剩下编号为几,因为大概会做,所以直接敲,然后一次Accept了,目标完成,睡觉。

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。同理,其他价值的石头也有类似的性质,规模减少后就可以直接搜索了。

PKU的1012

1012实际上是一条简化版的Joseph问题。Joseph问题是指从1到n的n个人,围成一圈,给定一个m。首先从1号开始报数,说到m的人就死掉,然后下一个人重新报1。比如n等于6,m等于5,那么死亡的编号顺序是5,4,6,2,3。1012是给出一个k,要求n等于2k,找出一个最小的m,使得后k个人先死。

这道题目实际不难,因为k的规模是0<k<14。就算最大的13,求出m的结果才是2504881。因此,就算逐个枚举,也是不会超时的。何况这个枚举很容易优化,m必须是(k+1)的整数倍或者整数倍加1。

但是,非常无奈,怎样提交,总是超时。一直想不明白,搞了一天一夜,终于明白了。原来虽然k是1到13,但是测试输入数据却有成百上千个,不断重复k的可能值。那么当然也有一大部分是k等于13的数据,测试如此多次,超时也就不出奇了。因此,解决的方法就是弄一个数组和循环,保存k从1到13时,m的值是多少,之后再读输入数据。

pku1012

第一次在Linux下发文章,纪念一下。