第一次参加周赛

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

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

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

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的值是多少，之后再读输入数据。

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