分类目录归档:essays

[POJ 3074]

Sudoku

题意:求解数独问题。

思路:用DLX解。首先,需要将格盘建模为DLX用到的十字链表。数字之间的互斥关系共有4种,因此可以对”每行每个数字”、”每列每个数字”、”每九宫格每个数字”、”每个格点位置”分别建立一个链表列,也即总共是9*9+9*9+9*9+9*9=324个链表列,十字链表中每一行表示在某格点放置某数,分别与4个对应的链表列相交。

然后,就是正式的深搜了。在深搜的每一层:
1) 在十字链表表头中找出元素最少且非零的一列,将该列以及列中包含的所有行元素从十字链表中移除;
2) 枚举列中的每行(作为解的一部分),将与该行相交的所有其他列以及这些列包含的行元素在十字链表中移除,递归下一层深搜;
3) 递归返回时,需要将2)中移除的相应列和行添加回十字链表;
4) 所有行枚举完毕时,需要将1)中移除的相应列和行添加回十字链表。

注意,对链表进行增删操作时,需要以相反的顺序修改各结点。同时,也需要动态维护表头的元素数。

没有想出太好的优化。c++下跑了188ms。

ps:
记得最早是11年寒假时,和Arios一起留校做MCM时听他提到,当时那道建模题可以用Dancing Links解。一晃眼,3年多过去了,我这才开始读Knuth的这篇论文

文章本身的算法不算难懂,因为深搜的优化是很多问题都要用到的。之前做题的时候,确实也有考虑过对链表进行动态调整,但发现无法根本上降低时间复杂度(依然是指数时间)后,也没有深究了。而Knuth这篇论文里介绍的DLX,通过对十字链表进行动态调整从而尽量保持搜索树最优,可以说是在通常情况下将深搜优化到了极致。

做这题数独时,在链表建模那一步想了大概一整天时间。主要是数独问题元素间的互斥情况比较复杂。一开始只用了前3种互斥关系,发现表头记录的元素数无法正确维护,每次暴力重算并加了些优化后竟然勉强过了。然后就一直在想正解。想出应该增加第4种互斥关系后,又用了很长时间才推出要移除与当前行元素互斥的所有行。最后对链表的修改要比一开始想的要复杂得多。

查了下status,Arios在5年前作出的时间是32ms,并且是1A 47ms过的。实在是很强。

books and reading

最近读完了松本行弘的程序世界,以及最后的贵族

前一本,在之前的几篇笔记里也有提及,除部分篇章略显单薄外,全书大部分都是作者多年来关于计算机语言的思考,在很多方面也打开了我的思路,实在是值得一读的好书。但这里主要还是想写写另一本。

从小到大都有政治课,但我经常是不及格,小时候也比较贪玩,对这种无法理解的东西一点兴趣也没有。应付考试也是拿着老师发的资料背一下忽悠过去。中考,高考,研究生考试,一晃都学了10多年政治课了,却也没感觉到学明白了什么。国内对政治这个话题真是非常敏感,来到北京之后更是加深了这种感觉。平时理工科就和政治不太沾边,同学间聊天也话题也很少涉及。身边朋友里几乎不关心政治的人也不在少数。

但大概每个年轻人都会或多或少对这个社会抱有好奇,尤其是在认识到面前不合情理地充满阻挠的时候。我也不例外。

最后的贵族一书原名往事并不如烟,作者是章诒和先生,主要讲述的是新中国建国伊始的一些事情。作者的父亲是当年被划为右派头目的章伯钧,是新中国首任交通部部长,也是当时的民主党派“农工民主党”的主席。还是引用作者本人的序吧:

这本书是我对往事的片断回忆,但它不是回忆录。

在中国和从前的苏联,最珍贵和最难得的个人活动,便是回忆。因为它是比日记或写信更加稳妥的保存社会真实的办法。许多人受到侵害和惊吓,销毁了所有属于私人的文字记录,随之也抹去了对往事的真切记忆。此后,公众凡是应该作为记忆的内容,都由每天的报纸社论和文件、政策、决议来确定。于是,历史不但变得模糊不清,而且以不可思议的速度被改写。这样的“记忆”就像手握沙子一样,很快从指缝里流掉。从前的人什么都相信,相信……,后来突然又啥都不信了。何以如此?其中恐怕就有我们这个社会长期回避真实、掩盖真实、拒绝真实的问题。

我这辈子没有什么意义和价值,经历了天堂、地狱、人间三部曲,充其量不过是一场孤单的人生。我拿起笔,也是在为自己寻找继续生存的理由和力量,拯救我即将枯萎的心。而提笔的那一刻,才知道语言的无用,文字的无力。它们似乎永远无法叙述出一个人内心的爱与乐,苦与仇。

寂静的我独坐在寂静的夜,那些生活的影子便不期而至,眼窝里就会涌出泪水,提笔则更是泪流不止,毫无办法,已成疾。因为一个平淡的词语,常包藏着无数寒夜里的心悸。我想,能够悲伤也是一种权利。

往事如烟,往事并不如烟。我仅仅是把看到的、记得的和想到的记录下来而已,一共写了六篇,涉及八人(不包括我的父母)。这些人,有的深邃如海,有的浅白如溪。前者如罗隆基、聂绀弩,后者如潘素、罗仪凤。他(她)们有才、有德、有能,除了史良,个个心比天高、命如纸薄。可说而不可看,或者可看不可想。过去,咱们这儿总喊“解放全人类”,却残酷地践踏身边的人。其实,不论贵贱和成败,人既不应当变为圣像,也不应当遭受藐视。

书是献给父母的。他们在天国远远望着我,目光怜悯又慈祥。

这本书实在让我无法评论,想写的东西太多太多。能读到这种毫无保留地讲述过去事实的书籍,实在是太好了。

昨天路过什刹海的时候,在地图上竟然看到有“张伯驹潘素故居纪念馆”。找到了门口,却很可惜的发现没有开放。这也是我第一次到什刹海,环顾四周,大概是北京城内风景最好的一角了。书中讲述的小说般的故事,却真真实实的发生在不远的过去,伸出双手仿佛就能触碰。回头想想,为何非要千里迢迢从广东到北京读研。其中最吸引我的,也就是这点了吧。

361_0

361_1

books and reading

最近也是在啃松本的书,越读越喜欢。

作为Ruby语言的作者,其书中对程序语言的看法非常独到。比如拿“面向对象”来说,我在之前看的书里面大多只是讲:类怎么写,继承怎么用,虚函数的作用是什么,诸如此类等等等玲琅满目堆砌了一大堆细节。很少涉及到非常关键的一点:为什么要用面向对象?当然某些书里会含糊其辞地写到,用“对象”的思想对客观事物进行模拟,会让写出来的程序更加合理。“但真的是这样吗?”这是我知道有面向对象以来一直存有的疑问。直到在本书中,读到松本写到的“从实用主义的观点来看,面向对象的精髓就在于对OCP的实践。至于把对象看做物体理解起来比较容易,能够建立现实世界的模型等,这些都只不过是些锦上添花的东西。”(P111),对我来说,这句话犹如醍醐灌顶,很多问题霎时间就明白了。(这里的OCP指的是open-closed principle,指程序对功能扩展要是开放(open)的,而修改则要对外呈现封闭(closed))

这本书里,作者还写到“但是不管过去怎样,现在对面向对象最好的理解是,面向对象编程是结构化编程的延伸。”(P32)。作者认为,我们写程序时,最初所用的结构化编程是非常自然的。但是当时仅能够做到“程序的结构化”,而无法做到“数据的结构化”,也即数据无法随着程序一起“流动”,造成了处理上的困难。而面向对象的出现,使得数据可以与程序捆绑在一起,由此便实现了程序完全意义上的“结构化”。

我无法判断这种思想是对是错,但若是反过来从头看程序语言的演变,由以上思想作为出发点的话,很多事情都变得容易理解了。甚至让我怀疑“面向对象是为了根据现实进行抽象建模而出现的编程思想”这种思路反而才是牵强附会。

另外,这本书里还讨论了其他很有意思的设计,包括“Duck Type”,也即动态类型,还有对多重继承的处理(对比了RUBY、C++、JAVA、SMALLTALK、JAVASCRIPT和LISP等多种语言解决多重继承问题背后的思想,以及优劣所在)等等。实在是让我眼界大开……

当然,我还不敢肯定自己到底理解了作者想表达意思的程度,而无法判断作者所言是否有理,但这种思想碰撞的过程,太让我享受了

惯例也贴一份有趣的程序,用Ruby实现微秒级别的时钟,以前用C时只能调用到毫秒,还以为系统不支持呢。另外本程序也是为了表现Observer模式的思想。

books and reading

最近在啃Effective C++

虽然一直以来都很喜欢写C++(其实是不会其他语言),也确实体会到C++语言的各种好处(清晰的变量类型,灵活的内存处理,强大的STL等等等等),但发现确实对面向对象的C++没有任何好感。

主要是书里面讲到的太多解决问题的“巧妙”方法,在我看来却是太投机取巧了。换言之,我认为如果非要这样才能写出高效的代码,那对程序员的要求实在是太苛刻了,况且这里还没有涉及实际项目的要求以及和他人的协作。当然,这本书还是让我明白到了C++设计时的一些思想,这是仅仅粗读C++ primer所无法领会的。

自己的一点粗浅体会,也写在这里吧:总体感觉就是,C++最初被设计出来时,是在考虑执行效率的前提下为程序员尽可能地提供了自由的功能实现方案。然而随着时间的推移,越来越多的技术被发明/发现出来,而C++也在不断进行扩充。直到今天在我学习的时候,发现她身上存在着太多的历史包袱,从一开始的继承C的语法以及面向过程,到后面的面向对象和模板泛型编程,虽然包罗万有,却又让人无所适从。做项目不比做题目,当一个庞大系统要实现出来时,往往代码的规范一致性和可维护性要比执行效率更重要,这也导致了很多高效的写法事实上无法应用于工程。而且,作为一门古老的语言,它提供的很多功能其实是累赘的(例如在本书P151中作者明确表示“protect继承的意义至今仍然困惑我”),并不能真正反映软件设计的需求。

相比起来,更为“现代”的语言,比如pyhton,在这一点上做得要好很多。其开发者相信“应当只用一种——而且是最好的一种——明确的方式去做一件事。”(“There should be one – and preferably only one – obvious way to do it.”),大概也是其得到广泛普及的重要原因。但个人认为,就语言学习来说,python这种“单调”的语法也对暂时不需要写项目的我没有太大吸引力。接下来想看的是Ruby作者写的松本行弘的程序世界

还是贴几段书中有趣的小例程,第一次知道C++还可以这么写:

模板编程(这里最多只能500,不知道为何):

用boost的:

以及:

编译这个还要专门写makefile(用的是os x下brew安装的boost库):

但貌似用clang编译时还是报找不到库…不管了反正不用xcode

[POJ 3373]

Changing Digits

好久没做POJ了。依然跟随POJ题目分类表,这题属于”记忆化搜索”。

貌似是要求高精度,但稍微分析下便知道,由于k<=10,000,那么n最多改变4位数字便一定能被k整除的,因此这里还是使用int除法,递归修改n的每位数字时顺便求出当前模值即可。 搜索的思路很容易出,由条件3和4,易得到搜索的方向:(1)由改变较少位数开始;(2)从高位开始。但是剪枝还是稍微想了一下。最后发现,根据dfs的传入参数,若该次dfs失败,可以用数组标记该参数组合无法满足题意。后续的搜索中,每次根据参数检查数组中对应位置是否已有标记,若是则直接返回0。其实不算难的一题,做的人却不多。另外,也开始习惯用vim敲程序了,开着fedora,窗口A左面vim,右面terminal(编译+运行),窗口B开着chrome读题,很是顺手哈哈。

这段时间有点迷茫,不知道接下来学什么好,能够交流的人也好少。 又买了Effective C++APUE,还是希望能把C++和Linux学得扎实一点。

今天也去了下阿里巴巴组织的大学生课堂,好久没听过课了,加上坐得比较远,实际没听到多少内容。倒是见识到好多牛人,都能各种和讲师交流了。就目前自己了解到的信息,还是很想去阿里的,但现在还不太够格。

亲爱的妈妈,不是我不想追女生,只是现在只能一心追时间啊。

Back to BUPT!

20天的暑假,实在是不敢再呆在家里了,毕竟休息放松的目的已经达到了,还有很多要学……

假期一行代码都没有写。倒是读了一下A Byte of Python。薄薄的100多页,却是让人读完后就能马上动手,觉得这样才是真正快速上手一门语言的最好方式!以前也借过同学的大部头Python学习手册,这本书当时读起来真是太无味了……详尽的语言细节介绍不是不好,但对于一个新手来说,这些东西真的可以放一放再说。

也读了一本《别逗了,费曼先生》,非常喜欢。除了感慨费曼先生的才华,书里让我印象最深、同时也是最令我敬佩的一点是他对科学和教育的毫不妥协。生活中的费曼是一个好奇心旺盛(当过艺术家,做过鼓手),爱开玩笑以及做恶作剧的大男孩,但当被邀请参加学术会议、审阅教材时,他仿佛变了另一个人。即使得罪会议小组里的全部其他人,他也坚持自己的意见;即使其他审阅教材的评委都随意打分,他也坚持亲自阅读全部教材再给分。或许是为了点出本书主题,全书的最后一篇文章也是费曼一次关于科研态度的演讲。虽然都是非常简单的道理,但如今自己作为研究生时环视左右,能做到的又有几人?……

隐隐约约地觉得,身边追求成功的人,大致可以分为两种:一种人积累的是自我,追求独立人格和思想,比起“目的”,更在乎“手段”,目标是找到“正确的事”;另一种人积累的是客体,追求的是外在世界的认可,比起“手段”,更在乎“目的”,其人生态度大概可归纳为“实用主义”。在我看来,费曼是属于前者的。我无法判断怎样的人生更为理想,毕竟人人都有自己的生存方式。但若就我自身而言,可能要在第一条路上永不回头了(会倒在哪里呢?)。

之后也希望能好好珍惜研二这宝贵的最后一年。比起(眨眼即逝的)研一,加倍地燃尽自我吧。

ps: 又发现一个好blog

Hello, this is Eurce…

 

用了2天多时间初步搭好了BLOG,过程比想象中还要顺利。

用的是linode的VPS,日本机房,速度还行吧。

同时也搭建了PPTP的VPN,越来越体会到Linux的好用。

好吧,还是希望站不要太快被黑掉。

接下来也希望能好好利用VPS的资源,定期做下codeforces。

这段时间做的几场比赛让我明白到差距好大。

想学的东西也还有很多,还是希望能继续努力吧。