Archive for April, 2009

金点十年了

Wednesday, April 29th, 2009

如果不是太无聊无意中去soft的blog瞅了一眼,我还真没有察觉到,原来,金点已经十年了。现在开始接触游戏行业的估计铁定不会知道这个名字了,但在当时,金点时空理所当然地占据着国内业余游戏开发的第一把交椅。我接触金点也已经六年多了,想想确实很长时间,换个角度却发现也不过一个初中一个高中而已。记得初三那年没上过网,金点好像也就是那个时候解散的。

::飞跃时空 经典无限::

::飞跃时空 经典无限::

从某种程度上说金点在我的一生中具有不可替代的位置。很小的时候玩游戏,而第一次明确地知道我也能做游戏大概就是认识了金点之后。当初金点的引擎做得还是不错的(在那个时候~),自己可以通过更改配置文件以及编写脚本来在这个基础上构建自己的RPG。其实很多人不知道,这种自己修来改去的过程是很锻炼人的,虽然提升的速度和空间都不大,但对于入门这也就是最好的方法了。所以那个时候我的积累就很深,对一些边边角角的东西用得就很多。等后来有人问我这些东西都哪里能学到的时候,我总是回答不出来,因为我确实不清楚到底是怎么积累起来的(当然另一方面的积累源于以前的瑞星社区)。

有了一个做游戏的想法,后来我就真的开始做了。买书,看书,一点点自己钻研,当时的感觉可以说跟《疯狂的程序员》里写的绝影的感觉差不多。无论你多牛了,都是从菜鸟爬上来的,千军万马过独木桥,摸爬滚打坚持到最后过了河,你就牛了。正所谓勤能补拙,所以我其实很承认我对一些问题的理解能力比人差得多,但重要的是我从来没有放弃过。

对于初中的时候的学习效率我觉得还是很高的,虽然学得要比现在慢,但现在快是因为那个时候基础扎实。那个时候天天看C语言,看DirectX,后来甚至还把《圣剑英雄传》的所有代码打出来一页页看,以及自己手写程序写满了一本本稿纸(当时身体不好父母限制上机只能离线工作学习)。苦的感觉从未有过,因为自己喜欢。

现在想想如果没有当时的积累,我现在根本不会是这个样子。从小到大做游戏的梦想真的从未改变过,虽然现实让我明白自己没有时间和精力去搞游戏了,但作为一个梦还是要做下去。如果哪天我连游戏都不想做了,那估计也是我退出这个行业的时候了。其实很多人都会有相似的梦,但真正做下去的能有几个呢?

点到为止;谨以此文纪念金点时空的十年历程。感谢金点给我带来的帮助,也很想念那些老朋友们。今天又联系到soft了;如果有以前金点时候的朋友看到这篇文章,希望能跟我联系~

疯狂的程序员

Tuesday, April 28th, 2009

He已然head for japan了,本来Q上人不多,加上这几天意识性地闭关修炼,越发觉得闷了,就从昨天下午开始看《疯狂的程序员》,看到刚才大约一共用了12个小时左右,35万字,看得我头昏脑涨,写完这篇马上去休息。

最早知道这本书还是作为买书的赠品,不过后来取消短期的买书计划了,也就没太注意。昨天不知道怎么就翻出来这个了,反正也是无聊,做题心里也乱,索性看了下去,谁知道越看越像看,最后还是看完了。我其实对小说很不感冒。想当初那个《无以言退》也是巨无聊的时候(那时候还在NOIP的早期复习)看完的。不过这次看的还算完整,而且文笔很好,最主要的还是描写得很贴切,很能产生共鸣。真的很喜欢这本书。官方论坛我没工夫去注册了,大家看完本文有兴趣可以慢慢读。其实不止是程序员,我觉得任何人都能从中找到一种激励自己奋进并对生活做出一个合理估计的力量。

读的过程中真的有很多次都被感动着,甚至有一种掉泪的冲动。文字中所表达出的应该是每一个程序员的心声,描述的也是我们习以为常的生活。作为一部励志小说,它真的起到了应有的作用。首要的一点,它把我从题海中拽了出来,让我重新回味自己的经历,重新思考一下自己的方向,重新定位自己的人生。印象中,我有很多次都是被生活的琐碎冲昏了头脑,以至于忘了自己最终要追求的到底是什么。这次我想我需要清醒一下了。该去旅游的旅游了,该提前进校的也快了,该自己学习的也都安下心了;我呢?我要的到底是什么?书中描写的创业艰辛一点都不为过,甚至我想过比这更复杂的环境。但我终究还是没有想明白。教主退役了去理论研究中继续深造,我不想深造下去死扣理论,因为至少我还不是教主。我一直很明确,我的事业离开始至少还有5年的时间,但我从未明确过,每过一天,5年中就少了一天。现在坐在教室的同学们还要面对一个月之后的高考,而我自己想想看,仿佛去年的这个时候的情景与心境还历历在目。时间是不等人的。全世界都搞计算机了我就算撑死也要吃下去。我不会在这里停留太久,我会继续向前,给我两年的时间再充实一下,好让我更有资本去充实我的生活。

每次提到上一段倒数第二句的时候我都有一丝伤感。不知道为什么,我总是很怀恋那个时候,虽然那个时候心里很慌头脑不清晰,但总能感觉到那么一点点快乐吧。那是一种不一样的快乐,跟戏法真的变出来的时候不一样的快乐,一种源于人最内心的与人交流的快乐。《疯狂的程序员》从某种程度上也加深了我对这种快乐的渴望。真的,我是渴望。当然,我也会正视一切,很好地对待一切,处理好一切的。其实不管结果怎么样,我觉得这段过程都让我成长很多,至少在心理承受能力上得到了极大的锻炼,尽管很多压力是我自找的。如果我们不能改变结局,那我希望,我们可以完善这个过程,好让彼此都从中获取到更多。

关于《疯狂的程序员》本身所带给我的和让我思考的或许能写出来的就这么多。书中也确实有很多让我感触很深的语言,我也习惯性地记录了下来,由于比较长再往下粘太难看了,大家可以点击这里查看,是TXT的,排版一般我个人感觉还可以看。

然后说真正疯狂的程序员自己的生活吧。今天周二了,不知不觉就过了一周了。脑袋里还记得上周五晚上看到了那篇Monday Today之后对自己说,这周已经记了一篇了,等下周吧。那个时候还觉得“下周”很远呢,谁知道,这已经过了快两天了。有时候真的就是这样的,心里空虚的时候想写点什么充实一下生活,但又有点懒惰于是给自己找个很合乎的理由。没办法,空虚也是自找的,就像与人交流也得有个限度。

上次Monthly挂掉了,这次又抱着很复杂很矛盾的心态看着它到来:很期待但又希望再晚一点。期待是因为太想获得成功的喜悦,哪怕是很小的成功,也太想证明一下自己,虽然多半是给自己看的,告诉自己没白过一个月,还是有一点提高的。但我希望的又哪止是“一点”提高啊!5月份是个很重要的月份,错过了就不好了。月赛的头奖直接决定一个月的工作计划。有时候自己就是很贱,逼着自己干这干那的(所以从这一点我就跟绝影有很大共鸣)。但其实我早就在盘算着最坏的打算了,但我还总觉得这个打算(虽然也是我的初衷)有点太过幼稚而小气,更何况还会影响到正常的训练时间。所以人贱过之后其实也很矛盾,告诉自己下一次不要这样贱了。但有些事情是不一样的。是啊,不一样,换过来说,我对别人一样了,别人能有那个心思来对我一样吗?我不想思考了,每次想到这里都很难受,干脆就不想了。我只知道一味地坚持,尽管我懂得了一些,但还是觉得自己很被动。我不想这样生活。

上一段杂感有点多了,话到伤心处就不愿意说下去,如果说也多半是给自己说。好了,不说跟感情甚至情感有关的东西了。上次那篇周记里(我没决定过要写周记,但突然觉得老黄的做法确实挺好)说了要亲自去借书,今天果然去了。中文图书真的啥也没有,有也确实没啥好看的,于是直奔外文图书。可怜的DLU图书馆啊,楼梯都那么卡,只能容得下一个人走上走下。到了外文图书区,发现居然各种历史书,翻了好半天才在最后一个架子找到了一个区域排满了计算机书。不过真的都是好书!不少都是一直想买一直没下决心要买或者绝版了没法买的书。因为还有上次借的没还的两本在手里,所以只借了八本书。首先是《Effective C++》、《More Effective C++》、《More Exceptional C++》以及《C++编程规范》。毕竟靠着C++混日子,虽然这几本书早就想看但都一直没倒出功夫来看,只买了《Exceptional C++》看完了还是不过瘾,这回终于能如愿以偿了。然后是《数据结构与算法》,仰慕很久但也是很久之前仰慕的一本书,准备用作英文的提升练习顺便清理一下解题思路。看过教主的回忆录意识到欧洲选手强大的解题能力不是盖的,所以自己也要有一个理性的思维系统地思考问题。还有就是《计算机图形学》,终于能看到老外原版的巨著了,希望能给那个Gift带来突破性进展。再就是那本梦寐以求的《网络流:理论、算法与应用》,这一周沉浸于网络流中不能自拔,并且愈加认识到其重要性了。最后,值得一提的是,我居然还挑了一本《UNIX系统编程》出来。本来没想借这方面的书,但无奈别的书都是一捡起来就想捡一大堆的那种,只有这本书很早在书店看过有比较好的印象,正好填补一下每天研究算法的剩余时间了。

写到这里也不少了,累了,去休息了。也希望旅游的也别太累了……唉……

2289 — Jamie’s Contact Groups

Saturday, April 25th, 2009

这题的难点大概就两个。首先需要读出来名字后面的那些不定长的数字。其次是求解(废话……)。

看了Shanghai 2004给的Solution,用C++析取Token再atoi,很麻烦,而且效率必然也不高。我输入输出都是用stdio.h,这道题顺理成章就想到了用getc和ungetc实现一个peek的功能。数据是按行给出的,如果下一个字符是换行符,那就结束这一组的输入,否则继续。细节可以参考本文末尾的源代码链接。

然后就是求解。很直接地想到用最大流,但试了一下TLE了。看Discuss说有人用最大流过了,目前还不知道怎么做的。最后用Solution的方法,多重匹配。原理跟普通的Edmonds匈牙利匹配类似,只不过对右部添加了一个匹配计数,其正确性不言而喻。

今天是找最大流的练习题做到这个的,没打算继续把Regional做完。蓦然想到今年如果走“正轨”的话,大一我是进不了集训队了;仿佛校选就在5月,而我,没有“提前进校”……

不说了,大翻盘不需要常理,SJTU自己会想明白的。

点击这里查看poj_2289.cpp(3184K,266MS)

2455 — Secret Milking Machine

Thursday, April 23rd, 2009

最大流问题,我用50行代码解决掉了。第一次这么写代码,感觉还不错。算法题就应该这么写,单独的算法聚集着写操控感觉也方便一些。也就是说,我可能又要改变一下编码风格了……

题目很好理解,一个容易忽略的地方是边是双向的(bidirectional),我在这里WA无数次调了一下午才发现这个问题。

大概的思路是二分枚举答案(最长边长度)然后建图,把长度超过这个数的边都删掉,每条边容量是单位容量(重边计多次),最后求一次最大流就可以了。如果最大流小于T,则方案不可行应该放宽限制,否则寻找是否有更小的答案。

建模有点间接,不过题目很容易看出来是用最大流解。我用的方法很朴素,BFS寻找增广路然后扩充流。

点击这里查看poj_2455.cpp(1184K,391MS)

Results World Finals 2009

Wednesday, April 22nd, 2009

ACM-ICPC Word Finals 2009 Stockholm已经结束,比赛的结果可能令中国的朋友叹息不止:我们的教主ACRush(楼天城)在杭州赛区复出后再一次与Champion错过,而原因依然在罚时(记得上次应该也是)。虽然说可惜的事情天天都在发生,但这么可惜的事情确实很让人难受;而俄罗斯人独占鳌头的形势依然在延续……

这应该是教主的最后一次ACM了。今天在几个论坛走动的时候看到有人说教主写了个回忆录,很感兴趣,就到处找来着,发现居然就在校内。在这里把文章的地址贴出来方便大家阅读(顺便瞻仰~)。从中我们能了解到Proxima比较详细的情况,以及教主多次参赛的经历等等,虽然言辞并不华丽但确实值得品读,不仅是对于ACMer或者OIer们,即使是与此无关的朋友也可以从中或多或少获取一些益处。

Google Code Jam 2006回顾
2005年ACM-ICPC——酸甜苦辣
TCCC2006——死亡之组
2006年ACM-ICPC(上)——Mobile Robot的成立初期
2006年ACM-ICPC(中)——Mobile Robot上海对决
2006年ACM-ICPC(下)——古城西安
国内个人赛场——百度之星
ACM-ICPC World Final 2007——Mobile Robot东京决战
国际个人赛场——三大赛事
2008年ACM-ICPC——杭州复出

教主非完美退役了,而正在向上的同志们依然要奋进,这其中当然也包括我…… Bless me~

也谈Oracle收购Sun

Tuesday, April 21st, 2009

好多人都在谈Oracle收购Sun的问题,如果你还不太清楚怎么回事,可以Google一下(或者更“人性化”地说“可以用你喜欢的搜索引擎搜索一下”……)。简而言之,就是那个曾经辉煌好几时的公司被收购了。

说实话我对Oracle没有很深的了解,也从未用过它的任何产品,生活里除了在公交车上看到那句“甲骨文是企业软件精英”之外,几乎从未对这个公司有过任何反应。而Sun不同,我用过它的操作系统,也正在用那个不算太垃圾的NetBeans,以及我最喜欢的虚拟化软件VirtualBox。曾经对Sparc很感兴趣,但一直没仔细研究过。至于Java,我向来敬而远之。“敬”是因为看到这个东西这么火,一定是有原因的,大家都不傻。“远”是因为我从未感觉这个东西能给我的生活带来什么影响,更别提能颠覆C++在我心目中的地位(况且我还有PHP和Ruby)。但Java的思想确实很值得借鉴,这个是不能否认的。

不久之前就有过传闻说IBM对Sun有意思,结果Oracle以高于IBM每股0.1美元的价格将Sun收入囊中。这多少来得有点突然,但Sun被收购这个事实却并没有多少悬念。很多人从很多角度剖析了Sun为什么没落了,这个满哪都是,讲得都差不多,核心就在于方向不正确,不能很好地把握时机(Java)。

于是“Oracle将成为业界唯一一家提供综合系统的厂商”(CSDN);Microsoft、IBM、Oracle将“三国鼎立”,Sun则从我们的视线中淡出。

收购之后就面临着产品线整合的问题。Sun之前搞到了MySQL,这下遇见Oracle了,也不知会怎样。至于Java,Oracle的意思是要创立新形象,毕竟它的产品多数也依赖于Java平台,生存不成问题,长成什么样就难说了。Solaris会是Oracle的王牌,只是名字说不过去没有意境了。Sparc生死未卜,但Sun强大的硬件基础会是Oracle超过Microsoft与IBM比肩巨人的一大筹码。

产品线的导向关键在于解决方案。不妨将此前两公司的解决方案列出来比较一下。Oracle的解决方案主要面向银行、保险、金融服务通信、高科技、生命科学零售公共部门公用事业。Sun的解决方案主要面向金融、能源、电信、医疗、生命科学零售政府教育。相似的部分我已经加粗并安排到相似的位置列出。可以看到,方向还是很贴合的。而Sun恰恰弥补了Oracle最大的“硬”伤,其服务器与存储技术都将带领Oracle原有的产品进入一个新的阶段,巩固Oracle在中间件和数据库的巨头地位。

由此可见,对业界的发展趋向来说,Oracle比IBM更适合“拥有”Sun。但经济危机的形势下,Sun被收购同时面临着裁员一万,而且资金上的运作不协调还可能造成两公司中间隙的产生。不过,总地来说,显然收购的结果依然是利大于弊。

最后,作为开发人员来看,我们关注的焦点应该落在什么地方呢?我觉得主要还是Java能否产生新的影响。同时我个人也很关注MySQL的命运。

P.S. Permanent Link起得有点卡,请不要介意。另外,今天终于用上路由器了,感觉还不错,这回文件也可以共享了。

3730 — Ebbinghaus method

Saturday, April 18th, 2009

刚刚灵光突现瞅了一眼清明节Monthly的Problem H,发现AC的人还是很少(10个)。比赛当天因为数据有问题,所以我一直交一直WA……罚时无数最后决定放弃比赛,唉~

为什么我一直交呢,因为我确信这个题很简单,就是贪心而已。注意题目中说“Facer always memorize all the wordlist in sequence”,这就决定了贪心是必然的(因为我快吃饭了就偷懒不写证明了)。我们只需要记录上一次“放置”背单词第一天的位置(last),然后从这开始往后找,如果能“放置”在当前位置就放,放不了就接着往后(多简单直接的贪心啊~)。没过的可能是因为题目没看懂,那我就没辙了,你自个儿好好看吧……

刚刚发过的题解,这篇也不直接贴代码,换成导出的HTML。但编码风格不是现在的风格了,我传的是比赛时候写的(水题懒得再写了~)。

点击这里查看poj_3730.cpp(125MS)