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

回校一周

到今天为止,已经回校一周了。以前从来没有试过这么早就回学校,这次算是体会到留校的人的痛苦了。首先是热水问题,那热水管的水几乎感觉不到暖,钱花花地流走了,却不能换来一滴热水,在这方面,热水公司绝对是侵害了同学们的权益。还有一个备受指责的是假期的饭堂,5块套餐都没一个肉,真是很难受,试过之后才知道平时是如此幸福。

不过艰难的日子还是过去了,天气越来越暖了,尽管春天的潮湿也随之而来。热水是一天比一天正常,而且因为天气变暖,这个问题慢慢没那么突出了。饭堂也正常了,也全部开了,所以终于不用再去那个难吃得要死的窗口。最重要的是感冒的身体痊愈了,所以心情也好了不少。

这个星期有很多好玩的发现,首先是twitter。早已听闻,但是以前的介绍都是说是微博客之类的,觉得好像没什么好玩的。直到最近身边很多IT人都推荐起twitter。用过之后我才感觉得到,twitter真的很好用,其中一个很重要的原因是使用起来很方便,可以用很多方式发布更新和看别人的更新,比如用Gtalk。这种高度的可互操作性使它和其它服务很不一样。

今天看到Solidot上介绍WriteOS这本免费的电子书,然后下载下来看,结果是重大发现!这本书介绍了写一个操作系统的一些基本的尝试。看了后了解了电脑启动时候的原理,虽然我学的汇编也是NASM的风格,第一次看作者写的汇编不是很习惯,但是理解起来还是可以的。最重要的是我也有条件可以完全做书上的例子,我是真机上装Ubuntu,虽然还没装VirtualBox,但要装不难。但可能我还是希望用其他的机器去试。而且作者solrex的个人网站也有很多好东西。

寒假的发现

在家里的这段时间很少写关于互联网的文章,现在正好一次过总结一下。

第一个发现是一本介绍开源世界的免费电子杂志在2008年1月登台了,名字叫《开源》。是简体中文的杂志,由“Linux宝库”网站制作。在第一期创刊里面内容很丰富,包括有业界的新闻,博客的文摘,还有一些软件使用的技巧和方法等。最后一部分还涉及内核编程的探讨。这本杂志比较全面而且及时地介绍开源的信息,我觉得很好看的,以后会继续关注。

第二个发现是北大的ACM系统。因为放假在家,所以无法登入中大的Sicily ACM系统,最后接触到俗称poj的北大ACM系统。后来发现这是全国里比较大型的了,题目也全,估计以后都会在北大的ACM系统继续做题,尤其是空余时间。

第三个发现是一本O’Reilly的好书《Beauty Code》。介绍简单的项目和优秀的简洁的代码。虽然拿到手几天,但是今天才认真看了第一章,介绍的是正则表达式的匹配器。用了C语言的递归和指针,所以整个程序才几十行,很简介,但功能很强大。当然文中也介绍,因为没有使用基于有限自动机的方法,所以效率比起使用有限自动机的方法稍逊一筹。我理解了之后,也按照原代码打了一次,编写了测试程序。如果正则表达式中的“.*”出现得比较少,效率很高,一般来说够用。以后如果要临时写正则表达式的匹配,有材料可以参考了,呵呵。

第四个发现是Makefile和make工具,原来真的很实用和易用,以后继续使用。

wenq

第五个发现是文泉驿的正黑字体,上图就是我装了之后浏览网页的情景。第一感觉是渲染得比IE7还漂亮,和Mac的感觉很像。现在才发现在Ubuntu装字体这么容易。其实还有很多发现,以后有机会再写,明天回校……

Fate/Stay Night

从年初一开始,一连花了三天,看完了动画版的《Fate/Stay Night》,真是闻名不如见面。而今天,也终于把游戏版本的《Fate/Stay Night》的Fate线打完了。

是一个哀伤的结局。这个故事讲的是男主角卫宫士郎无意中召唤出Saber,参加了圣杯战争。圣杯战争是七个魔法师带着七个召唤出来的英灵争夺圣杯的战争。但是主角有点特别,是基本上什么都不会的半调子魔法师,Saber是一个女剑士。

基本可以认为是幻想类的故事,因此看之前预计会以比较平常的心态看的。然而,看完之后却是对故事非常留恋,也带点哀伤。可能是无能的男主角比较特别,只会讲不会打,不过他的想法和行为也是称得上男人的。也可能是如此美丽的Saber但同时也很会打,华丽的剑法,女版的阿瑟王,她的英姿令我印象十分深刻,很喜欢Saber。总之说不出什么原因,但是远离实际而且也不算新鲜的故事能够引起我强烈的关注和共鸣。在我看过的卡通故事里,这个算一流的。

saber

故事的情节发展和其他卡通差不多,敌人逐个被消灭。但是故事的情感发展能够让很多看过的人回味无穷。“我是你的剑,你是我的鞘”这样的话在我看来比琼瑶的“风和沙”的比喻更加浪漫。结局是Saber想通了不再实现原本不可能的愿望,同时他们也发现圣杯里有的只是诅咒,所以士郎和Saber要毁灭圣杯。毁灭圣杯之后,黎明前的最后一刻,二人对望,Saber说出一句“我爱你”之后消失了。Saber主观意识破坏了契约毁灭了圣杯,因此终于能够回到濒临死亡的本体阿瑟王,命令随从把妖精之剑扔到湖里,然后死去。传说或者去了“理想乡”。这个TV的结局也是游戏版Fate线的True End。游戏中的UBW线还有一个Good End的。不过,True End让我们想到更多……

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下发文章,纪念一下。

家里用Linux

今天突发奇想,真的试试在家里用Linux,折腾了好一段时间,还蛮好玩的。

首先把启动的硬盘改为学校带回来的硬盘,这样就能进入GRUB界面了。等待了一些时间,果然,没办法进入Ubuntu的桌面。因为学校电脑用了nVidia的显卡,家里的是ATi的。于是上Google搜到重新配置的命令“sudo dpkg-reconfigue xserver-xorg”,配置完后再输入“sudo /etc/init.d/gdm restart”重新启动图形界面,果然成功了。而且还帮我自动备份原来的xorg.conf,我回到学校就不用再重新配置了。

好不容易进入到桌面,然后就是核心的上网问题了,因为既不是802.1X认证,也不是ADSL的PPPoE。我家用的视讯宽带的认证软件似乎是自己开发的,可惜没有Linux版。然而很意外,在wine下比较顺利就安装成功了。但是启动的时候还不行,加了sudo就可以用wine运行登录软件认证了。

pkuacm

这几天想试试pku的ACM系统,结果出奇地顺利,submit了8题竟然都一次AC了,稍微赞自己一下。也许是前面几题比较简单,也许是真的比以前有点进步,以后继续加油就是了,毕竟业余时间做ACM还是挺好玩的。但是中大的sicily在校外用不了,真郁闷。

哈利波特7

哈利波特7是这个寒假第一件让我充满兴趣的东西。看了差不多一个星期,昨天晚上看了一百多页终于全部看完了。

总体来说,第七本主要是在解谜,是时候把前面那么多伏笔隐藏的答案逐一揭晓。不过《哈利波特》真是很长,伏笔也很多,以致于揭开谜底的时候,很多次都不能马上反应过来,仔细想想才能回想起那个人或那件事。

换个角度看,其实作者安排得很巧妙,斯内普最终被证明还是一个好人,而且是勇敢的人,而之前的那么多伤害哈利的行为却又完全解释得通,因为斯内普喜欢莉莉,但是讨厌詹姆,哈利的样貌是詹姆翻版,斯内普讨厌哈利就不足为奇了,毕竟詹姆既侮辱过斯内普,也是斯内普的情敌。但是确实,纵观全书,斯内普没有对哈利做过什么真的伤害的,最多是侮辱一下哈利以求快感而已。相反,他救过波特,在书的最后全部阐明了。

从另一个角度想,作者似乎想灌输一些有益的价值观,而且手法很别出心裁。作者通过不同人不同的下场,三人组详细的心理描写以及他们的争论,显而易见地表达了“生”、“死”、“爱”等很多人生哲理的问题的意见。

Death Hallows

至于结局,我认为我自己一般不太注重结局,因为故事毕竟是故事,每个人希望的结局都不一样,真正的结局存在于每位读者的心中。不过讨论一下这个结局还是很有意思的,三人组打败了伏地魔,三人组活过来,但是不少深入民心的角色在最后的战斗死了,所以我概括为带缺陷的Happy Ending,其实我最喜欢这类结局,或者叫缺陷美,因为这样才能说明胜利来之不易,而且表明作者本身灌输的价值观就是不回避死的。而且作者也明白地表达这个观点,哈利不畏惧死反而搞定了伏地魔。