SHTSC

今天是 SHTSC(上海市信息学组队选拔赛)最后一次考试,也是宣布分数的时候。先说一下结果,

Day One

24(70 分):一道算 24 点的题目,说是说高级 24 点计算,其实高级了之后就非常简单(这句话很辩证),我大概在 10 分钟就做好了,没想到很多同学想了很久,还想了一个很复杂的。个人认为还能加 30 分,系统说我和 LTY 都是同样的错误,但经过手算,我们的答案显然是正确的嘛,写测评程序的人还真没水准。

Typesetter(0分):题目还没发下来,我就和 JRZ 说,是不是要我们做一个公式编辑器,他说很可能。没办法,看到这种字符串处理的题目心里就有莫名的恐慌,思路很混乱,而且很难里清楚,总结下来原因是,以前看到这种题目,没有静下心来好好研究,导致今天的结果就是——开天窗了。

Cactus(50分):一个图的计数问题,不是很难,DFS加高精度就可以了。一开始测评系统告诉我0分,结果在测一次的时候就50分了。没有满分的原因是,题目理解错误。更深层次的原因是,题目里对一种树——仙人掌树的定义,我看了半天才看明白(最后还是在一个细节上理解错了)。而对于别人呢,以前看到过,所以最多就是在看一遍,看看有没有出路就可以了。

Day Two

Incredible(100分):表面上是一个求方程解数的问题,实质是简单的递推,只要想到就OK了(反言之,没想到就挂了),复杂度看似很高,但是经过我的论证,实际复杂度很低,绝对可以再5秒内出结果。呵呵,只要是递推的题目,那就是十拿九稳的。

kth(30分):一看就知道考数据结构的,恶心啊。考卷一发下来,听见 HG 大叫,平衡二叉树,我这时就很残念,心想这题挂了,于是直接做最后一题了,后来反过来做这题,发现还是可以混几分的,于是就编了一个 Find + Partition 的算法,没想到考试结束后,HG告诉我,他也是用我这个方法的,我晕啊~

Color(0分):给一个 n 阶完全图,给边染色,求本质不同的染色方案数。最大的失误就是这道题目,原来以为可以靠这道题目翻盘的,结果……看到题目很高兴,因为一看就觉得是用波利亚原理做的嘛,正巧考试前一天,我看了一下午的波利亚原理,心里这高兴的~没想到,由于太高兴了,把题目看错了,看成把定点染色,结果就挂了,辛辛苦苦变得一个程序就这样废掉了,不过如果题目改一改(就是改称我理解错的那种情况),我那个绝对是一个好的算法,而且算法复杂度极低。不过现在换成边了,我还在思考中,在车上我已经想到怎么做了,但是在计算机上实现还是有困难,需要进一步优化,通过这道题目,使我对波利亚原理有了一个更深刻的认识,更让我对置换、对象、染色在波利亚原理里的关系有了一个清楚的认识。

总结:最后没有进队,其实也无所谓,2 个月,一直在弄计算机,学了很多很多东西(几乎把算法导论里比较实用的算法都学了一次),关键问题是,由于我始终没有学习使用指针,导致我没有学很多数据结构(很多高级的结构都是需要指针来实现),所以数据结构方面的东西不熟悉,更不要说灵活应用了。不过还是很有收获,这些知识我终身受用,计算机是一个实用的东西,欧拉路、网络流、二分匹配、素性检验、RSA,更高级的,自动机,NP,P。我看见了这个领域有一个很大的黑洞——让我不得不被它吸引。但现在我不得不要放下它一段时间了,因为还有数学和物理……有时新一轮的奋斗。

LoDaHo

昨天落大雨了。下午的时候回家,看看天色还不错,骑车到黄兴路的时候,突然天变得很暗,地面刮起大风,而且还是很了那种。接下来就不对了,当我到了军公路的时候,雨已经超级大了,大到眼睛已经很难睁开的境界。回到家,发现书包里的书都湿掉了。洗澡换衣后,感觉空气很清爽。看了看外面,雨还是很大,而且闪电也很多,据新闻说,东方明珠被雷击 6 次。看着窗外又 LoDaHo……想起了 S.H.E. 的歌……

从不要和陌生人说话到言论自由给我的启示

知道吗?和陌生人说话是很危险!

记得,上个星期,LY 和我说,有一个高一 5 班的小朋友问他,百度贴吧里面红琥珀是不是我,LY 回答是的。我这时候心里就感觉怪怪的,之后的事让我知道了,不要和陌生人说话!

话要从 5 月 17 日说起,那时候第一次上百度贴吧,看见一个帖子“强烈要求”,于是就回了几贴,反正无所谓,就说一个破解学校电脑的方案(还不是我想出来的,是班级同学告诉我的,而我,对电脑硬件可是一窍不通啊),本来以为很无所谓的,没想到……网络中心的人很看来很在乎!

再回到昨天。昨天早晨有点莫名,班主任做早操的时候叫住我,让我好好想想,我原来在教室里做了什么坏事?我想了半天,没想出来,他提示我是很严重的事情,而且表情严肃,我叫周围同学帮忙回忆,还是没有结果,我突然想出来一个可能:我最后整理教室的时候忘记把空调关掉,结果教室被烧掉了。后来一想,可笑,教室里没有空调。于是向老师索要答案,结果老师告诉我,学校网络中心说我把原来教室里的电脑密码给破了。我一听,感觉很莫名其妙,我平时用班级电脑除了上论坛下载音乐其他什么事情都不干(就算教室里装了什么 BT 或电驴,我都很矜持的——没用过一次),突然莫名其妙告诉我这件事情,让我感觉他们是不是在找茬。而随即老师告诉我,他们有证据,这就一下子让我把上面两件事和这件事情联系在了一起——果然!

早操后,老师说哪节下课一起去一次,我说好的,说得很大义,说得很凛然。
后来觉得这样很被动,而且第一节语文课心一直静不下来,就好像你拿到了传票,但是你真的是清白的,所以就急切地想解释,但是该听解释的人不在你面前。所以第一节下课,我就和 LQW 上了网络中心所在的办公室(请同学如果有必要的话做个证明,因为他比较懂电脑方面的东西)。

到了网络中心,看到张老师还有一个女的(名字不知),我主动表示我就是他们要找的人,那个女的发话了,开门见山问:“你是不是把管理员密码改了,或是对电脑做了什么不该做的事情。”我说没有。接着我同学解释“我们班级的电脑本来 CMOS 就漏电的”,这时老师有点激动,说“我们的电脑都是用一个 GHOST 做出来的,怎么你们班就出问题”,同学解释道:“我们班级拿到手就是这样的,可能是电压过低导致的”,听得我云里雾里,心想,是不是网络中心的老师自定义是权威,结果感受到了来自学生方面的挑战,所以为了维护自己的权威,就否定其他的可能性。我觉得有点偏离主题——我的目标就是说明这件事情不是我干的,其他的事情我一概不管。女的老师又说,很多学生说是我干的!我当即表示,如果有一个学生站在我面前说这件事情是我干的,那我接受任何学校的处分。(其实这时心里在想,如果真的有这种人,我肯定当场给那人一拳干死再说)。和我早晨猜测的一样,网络中心有老师经常潜水于百度贴吧,然后再通过学生(一种在我看来不很正大,不很光明的方式)了解到我的信息,于是找到我。但是明显这个老师不好意思说出来,否则就太明显了(明显到不用推就知道全过程),于是原本想说“很多学生说你是红琥珀”,现在改口说“很多学生说是我干的”,结果导致说错话。我回头看看张老师,还是那一张笑嘻嘻的脸,说了一些话,最主要的意思是“如果不是你干的,那你肯定知道是谁干的,然后你说是谁干的”,这就让我很郁闷,我是来解决自己的问题的,难道别人的问题还要我来帮忙解决?我回答“为什么我肯定知道?你们怀疑是我干的,但你现在又不能说明是我干的,又要我帮助你们知道是谁干的,这不就很为难嘛?”这让我想起来中国和美国法律体制的区别,在中国都是采用控方举证,而美国——比如美国的证监会银监会在处理一些问题的时候采用的事辨方举证。而且他们当时没有举出任何我是修改电脑设置这件事情的当事人,连辨方都不能算。经过几个回合,老师认为必须要找我们班主任一起来,有种的就单挑嘛~还请班主任出马,是不是有点打小报告的意味呢?而我的策略则是,让他们自己说出百度贴吧的事情。

第三节课上课前,班主任叫上我一起直奔网络中心,等了许久,老 Boss(因为张老师说要等她来才能解决问题) WYJ 终于出现了,这下才知道,肯定就是她派出她的得意门徒们追查到我的个人信息的。她也很开门见山,就直接告诉我,就是因为我在贴吧上面的一些言论,导致他们认为这件事情就是我干的,而且意思就是说我自己说这件事是我干的(事后这句话让我联想起了一些很牛的恐怖基地组织的行为)。但是我搜索记忆,没有发现我曾经表示这件事情是我干的,于是向她要求在看一遍这个帖子,并且认认真真地看。因为我知道,如果粗略地看帖子,很有可能认为这件事情是我干的,但是仔细一看一下,并且用脑子想一想,就知道明显我是在继续别人的事情。班主任也很好奇,走在前面一起看,并不停指责我这样说话会引起歧义和不必要的麻烦,这点我表示认同,看完第一页,WYJ 说,你看,这不就说明这件事情是你干的嘛。我问哪几句话说明这件事情是我干的了?我记得她当时局的例子是这句话

“不好意思,我们班级的 BIOS 电都放光了,所以可以完成我所说的事情,人品啊人品……”

我说为什么这句话就说明这件事情是我干的了?她指出后面的“我所说的事情”表明这件事情是我干的,而回到前文,这件事情应该是指

很简单,用光盘启动 windows,什么都可以干,比如在开一个比管理员权限高的账户……之类的。

两句话中主语没有出现“我”这个字,唯一出现“我”的地方就是修饰“事情”的“我所说的”,我想是不是你们逻辑混乱啦?出于礼貌,我说:“这就能说明吗?”,不知道哪个老师说:“这不就说明了嘛~”,我表示不认同。

接下来好像就没有我的事情了,网络中心老师从桌上拿起一旨“诉状”,上面写着我们班级的3大罪状,分别是:擅自修改网关通道,擅自安装什么硬件,还有一个是安装电驴软件。据说这个东西会交到德育处。

经过这件事情一折腾,心情不免很不愉快,晚上回家路上想了很多,回到家决定看看百度贴吧的一些法律文件,我完整地看了一遍,发现百度贴吧协议里是这样写的:

  • 第 5 条 用户的个人信息受到保护,不接受任何个人或单位的查询。司法、检察机关因法律需要除外、用户的个人设置公开除外。

这让我回忆到网络中心老师询问我是不是红琥珀,我一直坚持我既不承认也不否认我是红琥珀,因为我认为这是我的个人隐私。

有人会质疑(甚至我自己也质疑过)为什么这属于个人隐私(因为很多时候我们自认为一些事情是个人隐私,但事实上不是),后来我也找到了事实根据,百度免责声明:

  • 百度尊重并保护所有使用百度用户的个人隐私权,您注册的用户名、电子邮件地址等个人资料,非经您亲自许可或根据相关法律、法规的强制性规定,百度不会主动地泄露给第三方。

离开网络中心,下楼的时候,我抱怨没有这样不就没有言论自由了,班主任说,这是在中国,不是美国。但看了协议里的话是这样的:

  • 第 6 条 用户享有言论自由的权力。

只有一种解释,说的和做的有时候是不一样的,言论自由这种东西不是我们这种普通人所能奢望的,要是你比较牛,你言论自由没问题,如果你不足够牛,比如学生在老师面前是绝对牛不起来的,那你言论就要注意啦!今天看了你说的话,明天就派个小朋友到你班级问问,后天——哼哼——找你谈谈话,看你还牛不牛!还是陈老师说的好,“啊?你怎么不用匿名?傻了吧~”虽然我不喜欢用匿名的方式。

还有关于一开始的那个一 5 班小朋友的事情,我也不能说这个人很不好,只能再次警告自己,不要和陌生人说话,一个简单问题很可能导致一些复杂的事情。但是这并不能让我产生与世隔绝的心态,否则被这种小事扭曲人生观太不值得了,还是要养成健康的良好的彪悍的人生观啊!

回到教室,做考卷,心久久不能平静,半小时过去了,一个字都没写。我说你们整什么事不好啊,怎么整这种烦心事这么在行,真的是烦死了!

PS: 在回家路上发明了一个词语 spy students,特指那些替老师做眼线工作的学生。

Initial D

昨天老弟主动把《头文字 D》借给我。今天早晨起床(家长都去上班了),看见床头的 DVD,什么都不做,直接开电视看起来。

片中的车技镜头拍得貌似挺不错的,可惜我没有这方面的鉴赏能力。日本的风景很美,特别是清晨时候的秋名山山景(上次在日本的时候都怪那个台风,去富士山的时候什么风景都没看到,只好买点明信片回家看看)。

有感触的台词:

  • 杜汶泽:神,即是人,只是他做了人做不到的事情,才成为神。
  • 夏树:人要找到属于自己的世界才会快乐。(原本这句好好的,可是夏树她原来是……有点打折扣了)
  • 黄秋生:你要赢的是自己。

搞笑台词若干:

  • 杜汶泽 & 钟镇涛:当众打儿子不好,会给小朋友留下阴影。
  • 黄秋生:有一次他说他的眼睛很模糊于是带他看医生,可是医生说他根本没有问题,后来才知道怪不得他总是说看周围的东西变得好慢,原来是他越来越快了。
  • 杜汶泽和周杰伦打架后流着鼻血说:“这样流法,以后会不会每个月来一次?”(怪不得 DVD 的刻字上写着小字——IIA 儿童不宜)
  • 周杰伦:“这是 3 年前打的,这是 3 天前打的,这是蚊子叮的。”
  • 钟镇涛:“你这个疯子!!你儿子行不行啊?”
  • 黄秋生:“我有说过我儿子正常吗?”——黄又醉倒了…..

不说这么多了,早饭还没吃,冰箱里应该有“半成品”的饺子,微波炉转转,早饭中饭一起搞定,这生活混乱啊~

关于新教室的补充

昨天有一个经典语录忘记提了,看到 Henry Hu 的 Spaces 我才想起来。

下午,在新教室,老师给我们做新教室感言,他说的大体意思是,你们肯定会和历届一样,别看现在干干净净的,可以给人住,过了一段时间,就会变成给狗住的,再过一段时间……就是给猪住的了。所以你们一定要保持住,直到离开的时候,都保持一个像人住的一个环境。这时我向老师提议,我们要遵循自然规律……(隐含意思大家清楚)。老师随即表示要把我扔到猪圈住几天,并举例,学农时候的那个猪圈不错。至此,大家狂笑~呵呵……

新生力和新环境

今天上午两节课都放掉了,大家就尽情地玩啊!

打好篮球,突然身后听见有人打招呼,一转身,看见两个人,但不认识,我一问,他们说是进华的,我挺高兴,于是我问,你们怎么知道我是姜子麟。他们说,上次我回学校给他们班级讲“废话”的时候认识我的,我这才想起来。看到新生力,我不经很高兴,估计又要多几个好朋友了~我随即表示热烈欢迎,并向他们询问上课地点,他们回答在相辉楼,万老师——也就是我们的班主任——教他们数学。

今天下午是平行班分班的时间,很多班级之间组织了体育比赛或是文艺活动,操场上好不热闹。(今天中午原来要进行什么野外生存大赛复赛,一看才知道,原来是脚绑脚走路,介于其无聊的要命,我们就弃权了)

下午我通过四个来回,终于把所有东西搬到了新的教室,通过钟诚同学的研究,这个教室在有大火发生的时候,非常容易进行逃生,原因是窗外有一个水管,进一步研究显示,这个水管是不可能被小偷所利用。对于硬件,我不是很在意,关键就是——我终于能从第一排退居倒数第一排了,简直太舒服了!这样以后我就能安心做自己的事情了。

看见新生力,来到新环境,心里有无限的惬意,却说不出来。

庞加莱猜想

6 月 4 日那天很晚的时候,没事看看网上有什么新闻,突然发现新浪头条“中国科学家破解百年数学难题——庞加莱猜想”。

第二天,我和胡一发短信的时候,问他“你知不知道庞加莱猜想”。他回答“我知道……”当我告诉他“庞加莱猜想被证明了,你知道伐?”他表示极度惊讶,当我告诉他,还是被中国人证明了,他简直有点不敢相信,他告诉我:“菲尔兹奖曾经4次授予对庞加莱猜想有贡献的人,如果这次真的把庞加莱猜想证明了,那就不得了了!”,我说“对的,这次中国数学家就能在数学家大会上做一小时报告了”

下面是有关庞加莱猜想的资料,和大家分享:

一百多年前,法国数学家庞加莱提出,任何封闭的三维空间,只要它里面的所有封闭曲线都可以缩成一点,这个空间就一定是一个三维圆球。专业的表述是这样的:单连通的三维闭流形同胚于三维球面。它的推广是:任何与 n 维球面同伦的 n 维闭流形必定同胚于 n 维球面。更详细的内容可参见:Mathworld

我只能说,庞加莱猜想很可能被中国人证明了!但不管有没有被证明,我听到这个定理的第一反应是:将这个定理应用于整个宇宙系统,根据霍金的理论,整个宇宙原来是一个奇点。那么再根据庞加莱猜想,这个宇宙空间就一定是一个三维圆球!(个人拙见,仅供参考)

最后谈谈数学家的眼光:

庞加莱猜想是“七大世纪数学难题”之一,下面引用新浪网的资料:

2000 年 5 月,美国的克莱数学研究所筛选出了七大世纪数学难题,并为每道题悬赏百万美元求解。这些题目包括庞加莱猜想、黎曼假设、霍奇猜想、杨-米尔理论、P 与 NP 问题、波奇和斯温纳顿-戴雅猜想、纳威厄-斯托克斯方程。

在丘成桐眼中,庞加莱猜想和黎曼假设是两个最大的猜想。他一一分析指出,剩余下的六大难题中,很多人攻关的黎曼假设还没有看到破解的希望;引起很多著名数学家兴趣的霍奇猜想“进展不大”;和流体有关的纳威厄-斯托克斯方程“离解决也相差很远”;P 与 NP 问题“没什么进展”;杨-米尔理论“太难,几乎没人做”。

从中可以看到什么是数学家的眼光,虽然我现在还不能站在高点看问题,但是我已经能感觉的会当临绝顶时是什么感觉了。

Ponder This

不知道大家有没有主意我更新的链表,我常去的网站多了一个”Ponder This”。

这是IBM公司提供给全世界的一个平台,每个月有一个问题,然后大家可以去做,问题有的简单有的则可能是还未解决的问题,这个月我去看了一下,发现不是特别难,所以就做了,今天收到了IBM的回信,内容如下:

Dear Reader,
Thank you for your interest in “Ponder This.”  We have received your answer.  We generally do not respond individually but if your solution is correct your name should appear on the web site within a few days.

research.ibm.com Webmaster
webmaster@watson.ibm.com

To:
webmaster@watson.ibm.com
cc:

Subject:
ANSWER: June
2006 Ponder This

真得很高兴!

科幻社和云游社

科幻社和云游社~这两个社团的活动我都参加过。我设想如果我开一个电影社,那这两个社的人气就差不多了~

这个星期去看了科幻社放映的电影《金刚》,这是第二次看。今天中午又去看了云游社的《达芬奇密码》。熟不知这部电影和云游社的关系是什么,还堂而皇之地在博学楼底贴出告示,说是云游社派对,我晕,就这种垃圾社,到了高三我开个社团把他们一个一个灭掉。

不过还是要感谢这些社团提供了优越的条件给我们这些莘莘学子在繁忙的学习生活中一个喘息的机会。

星期四中午还参加了云游社的一个野外生存挑战赛的初赛,很有成就感的!我们班三个人成为一队参加比赛,除了我还有李家荪和钟捷。比赛一开始是一些是非题和选择题,虽然我不是很清楚,但是凭借我们的猜题技巧(他们两个靠过托福,接受过这方面的训练,而我则深知出题人的诡计,比如描述的语句很多的是非题一般选正确),答案基本全对了。接下来是问答题,我们的题目大致是问出去旅游应该带什么?因为前面已经有班级回答过这个问题,所以我决定要回答得有新意,我让李家荪准备“去沙漠或登山应该带什么”,让钟捷准备“去内地旅游应该带什么”,而我准备“去周游欧洲应该准备什么”。三个人上去轮番轰炸,效果很不错。而且赛后我们发现,只有我们一个班级是三个人都上去的,其它班级都是派一个代表上去说的。地里老师说,这也是给我们打高分的原因之一。看来我的决策是正确的!赞一记!

今天公布了结果,我们班级的队伍以初赛第一的身份进入了复赛,真得很开心。