http://cuitianyi.com 我读·我听·我思·我行 Tue, 23 Feb 2010 05:08:03 +0000 http://backend.userland.com/rss092 en 今天，我回到了浙大，我把这算成寒假的结束。上个学期最后一门考试的前一天拿到了一台 Kindle DX，于是这个假期的所有书都是在这台 Kindle 上读的，大致按照读完的顺序如下： 周国平《尼采：在世纪的转折点上》 The Power of Less (Leo Babarta) 陈冠中《盛世》 《中国健康调查报告》 Outliers (Malcolm Gladwell) Programming in Scala A Rulebook for Arguments (Anthony Weston) 罗素《西方哲学史》卷一 四本中文书，四本英文书。有小说，有编程，有成功学，有哲学史，有健康指南，有批判思维。虽然数量不算多，不过我相信这是一段富有平衡性、充满营养的阅读体验。这些书读的时候多少都做了一些摘抄、提纲和感悟之类的文字，在此就对每本书做个简短的的读后总结吧。 周国平的《尼采》一书是在ASES读书会中了解到的。我喜欢周国平写的尼采，类似于我欣赏钱穆书中的孔子。钱穆以儒家信徒乃至道统传人的信念写《论语新解》，自然将论语的妙处诠释得淋漓尽致，读者也最能从中受益。（插一句广告，我一直坚定地认为钱穆《论语新解》是用来了解论语以及儒学的最好的入门读物，在此郑重推荐。）我无旁据地揣测，写此书时的周国平必自认为尼采的信徒（虽然不一定会公开承认这一点），而这个角度的介绍，是追求他山之石而非价值判断的我所乐于阅读的。 Leo Babarta 是我订阅了一段时间的英文 blogger，于是它的书 The Power of Less 的英文电子版躺在我硬盘里好久了。真正在 Kindle Store 里买了并从头到尾阅读一遍才如梦初醒，书中完全点明了我拖了那么长时间没抽出空来读它的症结。我非常庆幸能在寒假的开始以及一年的开始时读到这本书，其中的精神整个改变了我的寒假计划，我想也会改变我接下来一年的安排。这本书好像也刚出了中文版，强烈推荐给每个像我一样对“more”有着不懈追求的人。 《盛世》这本书我看的是 Twitter 上分享的陈冠中先生亲自校对和分享的盗版PDF。依我的理解，它从纯粹文学的角度看不算是第一流的小说艺术。对其思想性不评价，主要是因为觉得自己没那个能耐去评价吧。 会去看《中国健康调查报告》这本书是因为有践行书中建议的素食饮食习惯的朋友的推荐。读之前特意在 Google Scholar 里输入了作者的名字，发现确实是个学术大牛，才放心地读了下去。我承认书里的论据和结论都是非常有说服力的。这促使我在过年前的某一天中午对抢我的Kindle看了这书的一部分的我妈说，今天中午吃一顿素食吧。这顿素食带来的后果是我在几个小时之后窜到厨房里对正在准备晚餐的我妈大声喊：“我要吃肉！我要吃肉！”于是这本差不多是素食主义者的圣经的书遇上我这个打小无肉不欢的家伙就完全没起任何作用。嗯……应该说这本书还是带来了一些让我在四十岁或者更老的时候转向素食主义的可能性，至于现在就算了吧…… Malcolm Gladwell 写的 Outliers 一书的副标题是 The Story of Success，最初是在李笑来老师的blog上听说此书的。这本书论证讲述了现实世界中的事业成功被哪些因素左右，并得出了一些有悖于常识却又有说服力的结论。中文译本的书名是叫《异类》，推荐给每个希望了解并达到事业成功的人。 假期里读的唯一一本跟我自己的专业直接相关的书是 Programming in Scala，是因为最近要用到而读的。作为一本编程语言的入门书，它是中规中矩的。至于 Scala 语言本身，我本来想好好写一段技术评论，不过眼界和经验所限，还是不写出来误导人了吧。总之，我的结论是，Scala 绝对大有可为。 会在 Kindle ... http://cuitianyi.com/blog/%e8%bf%99%e4%b8%aa%e5%af%92%e5%81%87%e8%af%bb%e7%9a%84%e4%b9%a6%e5%8f%8a%e5%85%b6%e5%ae%83/ ;; 2.1 (define (make-rat n d) (if (< d 0) (make-rat (- n) (- d)) (cons n d))) ;; 2.2 (define (make-point x y) (cons x y)) (define (x-point p) (car p)) (define (y-point p) (cdr p)) (define (make-segment start end) ... http://cuitianyi.com/blog/sicp%e4%b9%a0%e9%a2%98%e8%a7%a3%e7%ad%94%ef%bc%9a%e7%ac%ac%e4%ba%8c%e7%ab%a0%ef%bc%88%e4%b8%8a%ef%bc%89/ ;; 1.29 (define (simpson-integral f a b n) (define (coefficient i) (cond ((or (= i 0) (= i n)) 1) ((even? i) 2) (else 4))) (let ((h (/ ... http://cuitianyi.com/blog/sicp%e4%b9%a0%e9%a2%98%e8%a7%a3%e7%ad%94%ef%bc%9a%e7%ac%ac%e4%b8%80%e7%ab%a0%ef%bc%88%e4%b8%8b%ef%bc%89/ ;; 1.1-2 略 ;; 1.3 (define (greater-two a b c) (- (+ a b c) (min a b c))) ; 或 (define (greater-two a b c) (cond ((and (> b a) (> c a)) (+ b c)) ... http://cuitianyi.com/blog/sicp%e4%b9%a0%e9%a2%98%e8%a7%a3%e7%ad%94%ef%bc%9a%e7%ac%ac%e4%b8%80%e7%ab%a0/ 昨天，ACM/ICPC杭州赛区以金奖（第五名）谢幕。对于Genesis队，本赛季的所有比赛已经结束，以后不大可能再在比赛中看到我们这支队伍了，希望Genesis得到的两块regional金牌以及一直以来的表现能让关注我们的人满意。 对于我已经研一的两名队友，这大约是他们最后一次以队员的身份出现在ACM/ICPC的赛场上；与高远(xgy)、杨克特(T_T)两位学长的无间配合是太过愉快的经历，学长的经验也让我受益良多。 而对于我，一名正式进入大学才三个月的大一新生，一切才刚刚开始；前方还长的路让人激动憧憬，请相信我会带来更多惊喜。 其实，这赛季能够连拿两金，取得对于我这种新手来说可称辉煌的成绩，不仅取决于全队的努力，对于我自己来说，其实不乏运气成分。这学期我主要的突破是仔细读了本《简明数论》（其实这书只有一半名副其实，“明晰”是无疑的，“简单”则谈不上），打下了还算扎实的数论基础，差不多能应付Regional中通常的数论题了，结果我们队参加的哈尔滨和杭州两个赛区正好都有数论题出现，特别是我们在哈尔滨最后才解出的B题更是我们夺金的关键。另外，在杭州赛的前几天，我匆匆浏览了《柔性字符串匹配》的后半部分，主要内容是用有限自动机做正则表达式匹配。对那本书的主题我自然是一知半解，不过倒对有限自动机有了较多的感受和认识。没想到杭州赛区的H题就是判断两个有限确定性自动机是否等价的题目。虽然没见过，但正好这几天见识了很多与自动机有关的内容，灵光一现就得出了算法，使我们队解出了第6题，也是场上解出的最后一道关键题目。 这样看来，我第一年的ACM/ICPC征程真可称顺风顺水，似乎幸运眷顾，完全没遇到挫折地走下来。当然，以后还是老老实实提高自身实力才是王道，近期打算学学Java，读读SICP之类的书。 这个学期还剩下大约一半，除了为了保持状态做点SRM以外，就不再寻求编程竞赛方面的突破了，应该多尝试点不同的内容。学Java达到与目前的C++近似的熟练程度，读SICP、Concrete Maths、Programming Pearls是必须完成的内容，如果还有闲暇就打算读读Algorithm Design以及一些AI方面的书目。最近一本《数学分析原理》让我多少发现了纯数学的美感，虽然这学期应该不大可能了，但以后还是要读些纯数学的经典教材的。物理是这学期多少令人头疼的科目，得抓紧看一下，希望能培养出兴趣。 好吧，读书去了。 http://cuitianyi.com/blog/2008%e5%b9%b411%e6%9c%8824%e6%97%a5/ 注：凡“旁注”性质的笔记，都是无规划不成系统的读书随想。尤其与我大多数短篇的读书笔记一样，并不求别人也看懂。 第1章 (2008.11.16) 1.24：引入复数的一切都很完美，只是这个乘法的定义还是略显突兀。能否通过M1~M5以及零元、幺元等内容将这个定义更顺畅地推导或引入呢？换句话说，有了很自然的加法的定义，要满足(1,0)为幺元以及M1~M5，有了这些条件能否得出“合理”的乘法定义有哪些？于是就是函数方程了。如果这是唯一满足的定义那就完美了，不过我的推测是：它是函数方程所有解中明显、特殊、或朴素的一个。 1.35：又是那种“神来之笔”的证明……怎样理解这优美的构造？ 1.A.9：任何两个具有最小上界性的有序域同构。我会找到它的证明。 第2章 (2008.11.17) 这章的目的为何？完全不明白，也没办法搞清定理之间的联系。 2.12：可数个可数集的并是可数集。 2.23：所以同为开集与闭集的集就仅有空集和全集。 2.23：紧集，对于集合的每个开覆盖，存在一个有限子集也是开覆盖。 2.44：Cantor集的概念。 第3章 (2008.11.17) 这章的目的应该是判断及求得数列以及级数的极限。 3.1：极限的概念可以直接在度量空间中定义。 3.21：定理能按数列与级数两种语言来叙述与应用。 3.27：正项不增序列a_i的级数收敛当且仅当2^k a_{2^k}的级数收敛。这可以用相对很稀疏的项判断级数的收敛性。 3.38：幂级数的收敛圆（由根值法推出）。 3.42：∑a_n有界，b_n单调递减到0，∑a_n b_n收敛。（分部法）推论：交错递减则收敛。 3.47：级数乘积的定义有卷积的味道。 3.53：对（收敛但非绝对收敛的）级数重排会改变收敛的值！奇妙…… 数列：单调有界定理，比较法，Cauchy准则。 级数：比较法，3.27，另一种形式叙述的Cauchy准则，比率法与根值法（3.37说明前者有效的后者一定有效），收敛半径，分部法及推论。 第4章 (2008.11.18) 4.8：函数 f: X->Y 连续，当且仅当对于Y的每个开集V，f-1(V)是是X中的开集。（由于开集的补集是闭集，所以叙述中可以换成闭集。） 4.18：一致连续是函数（在某个定义域上）的性质，而连续是函数在点上的性质。然而在紧集上，这两个概念等价。 4.23：函数的连续性保持定义域的连通性。 这章应该是探讨了函数的连续性与第2章中集合的特性的关系。2、4两章应该都是构建后文微分、积分理论大厦的基石与原材料。 第5章 (2008.11.19) 5.9：直接证一般中值定理，很赞。 5.12：导函数可以不连续，但不能有第一类间断，且在区间内能像连续函数一样取到所有中间值。 5.13：L'Hospital法则的证明，看上去很不直观。Wikipedia上的证明似乎更优美。 5.15：这个证Taylor定理/Lagrange余项的方法简洁得很诡异，其实没看懂……Wikipedia上的先证integral reminder再用积分中值定理直接得到Lagrange reminder的方法直接且精炼。 第6章 (2008.11.20-21) 6.1：这个定义与Wikipedia上的Darboux integral完全相同。上积分、下积分——它们必定存在，可积性便等价于二者是否相等——于我是新鲜的概念。以下便用这些定义（还有一个“加细”）证明了若干关于可积性的性质。 6.2：在概念中增添“-Stieltjes”之后，让关于x的Riemann积分可以关于任意函数α(x)，扩充的要点是，α不必可导，甚至不必连续。 6.15：有点绕……第一遍没看明白。不过的确是一下子让人发现Riemann-Stieltjes对于Riemann的扩充，然后函数值、级数(6.16)都可用一个Riemann-Stieltjes积分来表示，6.18是点出本质的总结。 6.20-21：微积分基本定理的两部分。我总是觉得Wikipedia上的证明一下子就能看懂，这书故作高深的倾向却要让人看很久才知道他是怎么证出来的……这种从定义就开始“立意求高”类似于“伤人乎不？问马。”，教材中的例子有萧树铁的《大学数学——代数与几何》中对行列式的定义。这样的教材的确有境界，不过最好还是借助大众化的Wikipedia补充一下。 http://cuitianyi.com/blog/%e3%80%8a%e6%95%b0%e5%ad%a6%e5%88%86%e6%9e%90%e5%8e%9f%e7%90%86%e3%80%8b%e6%97%81%e6%b3%a8%ef%bc%88%e4%b8%8a%ef%bc%89/ Euler函数φ(m)，定义，积性不完全； ； ； 。 用积性证很简单；证明二：按与m的最大公约数分类。 f(n)的Mobius变换：； Mobius逆变换：； 以上两式等价，f(n)与F(n)的积性也等价。 f与g的Dirichlet卷积：，h保持f与g的积性。 同余： a对模m的最小非负剩余、绝对最小剩余； 同余式是等价关系；同余式可加减乘；ca≡cb (mod m)等价于a≡b (mod m/(c,m) )； 对模m的逆的定义。 同余类、完全剩余系定义； 既约剩余系包含的同余类个数即φ(m)。 (a,m)=1时，x遍历m的完全/既约剩余系当且仅当ax遍历m的完全/既约剩余系。 用这个可轻松证明Fermat-Euler定理。 Wilson定理，即(p-1)! ≡ -1 (mod p)。 证：除了-1外，其它因子可与（不相等的）逆元配对抵消。 即，p的既约剩余系的积模p得-1。 扩展：p可换成pk，2pk（这两者p是奇素数）。 事实上，r不取1,2,4,pk,2pk时，r的既约剩余系的积模r得1。 ax≡b (mod m) 型的同余方程。 (a,m)|b 是有解的充要条件，解有(a,m)个。 可求a对m的所有逆元。 注意到一个解是 ，也可用扩展欧几里德求特解。 所有解是，其中0<=t<(a,m)。 形如的一次同余方程组。 若{m_i}两两既约，则解数必为1（中国剩余定理）。 解为。 其中，。 当a_i分别遍历m_i的完全/既约剩余系时，x遍历m的完全/既约剩余系。 若{m_i}并非两两既约，例如(m_i,m_j)=a时，可将模m_i与m_j的两个方程化成模a、m_i/a、m_j/a的三个方程。 编程时，直接化为若干个模p^k的方程似更简便，其中p^k || [m_1,m_2,...,m_i,...]。 f(x)≡0 (mod n) 的解数设为 T(f;n)，则T(f;n)是关于n的积性函数。 于是只需研究f(x)≡0 (mod p^k)型方程的解法。 即求解多个方程后再解个模{p^k}的一次同余方程组。 http://cuitianyi.com/blog/%e3%80%8a%e7%ae%80%e6%98%8e%e6%95%b0%e8%ae%ba%e3%80%8b%e7%9a%84%e7%ae%80%e6%98%8e%e7%ac%94%e8%ae%b0%ef%bc%88%e4%b8%ad%ef%bc%89%ef%bc%9a1321%e8%8a%82/ 10月8日晚的火车，三十多个小时的旅途，去往一座遥远陌生的北方城市，哈尔滨。 上火车后，惊喜地发现，我们硬卧车厢的走廊窗口下竟然有两相和三相的电源插座！可以无顾忌地使用电脑，似乎会给旅途增添不少趣味和意义。火车上，我把觉得比较有用的论文看了一遍，又对照着CD看了几章《听音乐》。 我在重要的比赛或考试之前容易滋生紧张情绪，这也是NOI2007的败笔之一。不过这次不同，一路上有队友相伴，本应枯燥的车厢里，充满欢声笑语。 灿哥通过神奇方式买到的火车票十张全是上铺，不过大家发现这种新式车厢的上铺非常舒服。更何况，在某人的下铺处有一只天真无邪可爱动人如假包换的小萝莉……这个话题不展开了，请自行YY。 T_T同学出了一些猥琐的迷题（e.g. 一只公牛和一只母牛同时踩坏了别人家的田，为何公牛主人赔偿三分之一而母牛主人赔偿三分之二？），令大家都很惊讶的，某位dd同学几乎每次都反应很快地第一个说出答案。好吧……在此我申明三点：第一，那些迷题没有一个是我之前听过的；第二，之所以我每次都能最先得出答案，我的唯一解释就是：我的思维敏捷、智商高；第三，我很天真哒，我的话讲完啦。 火车上的每顿饭都去餐车吃，虽然贵且不好吃，但毕竟是能找到的最佳选择了。这时T_T同学的母亲在德州站送上来的三只扒鸡正如雪中送炭，众饕餮很快就将那些可怜的无毛二足动物杀得片甲不留，对其二足尤不留情^_^。 火车到站时间是10日早晨5时许，一群几乎都没来过东北的人立即领教了寒风的威力。一干人等饥寒交迫地奔赴某盖头gg事先选定的车站门口的KFC，却发现人满为患无处容身。我通过手机上的Google Map搜索到了最近的另一家KFC，大家便打车前往。BTW，发现哈尔滨的GPRS网络很棒，明显感觉到比杭州的快，然而不知为何某只很拉风的iPhone在哈尔滨却无论怎样都连不上GPRS…… KFC的早餐让大家都找回了久违的饱腹感，充电完成的一干人等玩起了由gdb引进的多人纸牌游戏“盖棉被”。如果仅描述规则的话，听起来真是一个挺傻气且低技术含量的游戏：若干人轮流出牌，同时循环报数1至13；若某人打出的牌和说出的数字恰相同，所有人都需要尽量快地将手掌盖向牌堆，盖在最上面的手掌（也即反应最慢的）需要拿走所有的牌；手中无牌者胜。不过大家都玩得不亦乐乎，情不自禁高声大叫，引来了KFC MM礼貌的制止。在KFC的经历，让大家明白了一个深刻的道理（做小学生作文状）：南北风俗不一样！好吧，看不懂的请略过或自行YY -___-。 打车来到哈尔滨工程大学……门口的八一宾馆报到，然后在志愿者MM的带领下入住十五元一天的学生宿舍-___-，还好后来在我们强烈要求下换成八一宾馆的标准间了^_^，偶和可爱的xgy队长gg一间哦~ 10日一天都没什么安排，继续盖几圈棉被以后，一堆无聊人士围坐一圈玩起了同样低技术含量的梭哈，用另一副牌当筹码。赌博的结果是有的人（可怜的xgy gg，cmft）输到倾家荡产，有的人（就是我啦^_^，嘻嘻）成了大资本家，我赢了比翻倍还要多哦~ 午饭选在某忘记了名字的火锅店，灿哥中途从机场赶来加入。相信大家都吃饱了，而且我自己认为吃得还不错，只是某人点了过多的丸子浪费不少…… 下午和晚上，除了必要的赛前准备，大家仍然把时间用在了打牌与谈天之类娱乐放松的项目上。期间七个人玩两副牌的接龙还是挺好玩的。顺便炫耀下，在哈尔滨玩的很多盘接龙的分数都记录了下来，在幸运与实力的双重照耀下，dd同学是总积分的最后赢家~oh yeah~ 期间值得一提的事情是，我们目睹了某欧阳极囧的脸红过程，并拍下了真相。欲知详情，请私下交流或自行YY……关键字：罩杯-___-。 10日晚上一直玩到午夜才睡。 11日上午貌似仍然是谈天玩牌。哈工程“大学生美食广场”午饭后，Genesis+gdb的猥琐男们在哈工程的长椅上懒洋洋地晒太阳，顺便开展猥琐的分手现场偷窥行动以及路过MM打分行动，期间小耗子乱入-___-。 下午试机，觉得电脑上的NetBeans还算好用，决定第二天比赛就用它了。试机期间，主办方的组织让人不能满意：每队三个人只有一份题目且不说，最不能忍受的是judge故障连连。我默默祈祷正式比赛时最好不要出现judge问题。 11日晚上，大家没有过分的娱乐，早早回到了各自的房间里养精蓄锐。我看了lrj“习题指导”和北大出版社《简明数论》两本书中的重要章节，听了贝交第五全曲，九点半安然入睡。 12日早晨六点半，醒来后的我感到前所未有的精神焕发，觉得这应该就是所谓的最佳比赛状态了。早餐中，灿哥给我们讲了若干“坚持到最后一分钟翻盘”的传奇故事。我相信听者没人想到，那天的比赛中，我们中的一支队伍会创造另一个传奇，一个毫不逊色，且注定被一遍遍讲述的传奇。 开赛半小时前进入场地，我们的装备大致如下：德芙巧克力一盒、红牛饮料若干罐、圣经一本（和合本+NIV对照）、牛津高阶词典一本、以及常用参考书一堆。 比赛开始了，共有十题，从A到J。按照一贯的读题分配：T_T看ABC，xgy看DEFG，我看HIJ。 我分到的题目都比较长，H大致看懂了，断定绝不是前期能写的题；I题意很简单，给定一个顶点的度序列，问是否存在对应的无向简单图，我觉得这应该是的经典问题，但却完全没看过类似的问题或算法；J的题意也不难理解，但可以看出，相当有大自然题的潜质。 大家把题都看的差不多了以后，互相两两交流了一下题意，没发现明显可做的题目。这时看到大屏幕上已经有四个队过题了，过的都是I。我意识到，I肯定不是难题，便专心yy之。期间xgy和我都怀疑是否只判断一下度的奇偶性就可以了，不过很快找到了反例。仿佛灵光一闪，我脑中突然出现了一个贪心构造的方法，讨论后，大家都没思路证明其正确性，却也找不到反例，于是我便上去敲了代码并提交之。 这时看到有牛队过了A，T_T给我讲了题意后，我写出前N层和的表达式给了他，他完善了一下二分答案的细节，便上去写了。写完后发现，按照我给的表达式计算的话，虽然输入不会超过六十四位整数，然而计算的中间过程完全可能会溢出，一时没有找到解决之道，只好由xgy把这个C++程序翻译成Java用BigInteger来写，交上去以后很快返回了Yes。这时已经拖了不知多久的I终于返回了，还好是个Yes。拿到两个气球的我们排名并不乐观。 在此之前，xgy给我讲了他对F的想法，我在他的基础上很快推出了完整的充要条件，但我俩都不太确定该怎么实现比较好。T_T听见后表示，如果充要条件是这样的话，那么他完全能写，因为写过很类似的题目。于是他上去用DP/递推的方式写了个程序，很快Yes了。三道题都1Y的我们第一次冲进了前十名。 写F期间，我和xgy在讨论G题，这道题的文字叙述得挺模糊的，不过通过仔细阅读加合理推测，我们很快发现原来就是一个有向无环图上的博弈问题，拓扑排序一遍再DP就行了，我上去写了以后也1Y了。当我们第4题的AC反映在大屏幕上的时候，我发现，在比赛时间过去约一半时，我们是全场第一个AC 4题的队伍，排名第一。旁边堪称全明星的清华IronGods队也只有三个气球。 这是我第一次感到情绪波动的时候，在此之前，我一直都保持着平和淡定的情绪，精神非常集中，头脑非常清醒，基本上处于巅峰状态，思考和敲题的效率都很高。然而此刻，看着大屏幕上飘扬在最上方的team53（我们的队伍编号），我出现了不应该有的过分激动以及过分自信。现在，我（多少有些羞愧地）承认，在那一瞬间，我想到了斯德哥尔摩。暂时领先造成的情绪波动直接影响到了我后半程的发挥，这也是我个人本次比赛得到的最重要的教训。 C题大概是早就得出了二分图最优匹配的算法，T_T上去写，似乎是用了令我难以置信的短暂时间就敲完了。交上去以后，返回了我们的第一个WA。我提醒T_T是否注意到船到达port以后不能再出来的条件，他意识到忽视了这一点，很快改好了，没想到仍然是WA。于是T_T打印了代码让xgy和我看。给代码查错应该是最需要集中精力的活，而我在看那份代码时却完全做不到这点，草草地、甚至一目十行地在看，怎么看都觉得没错误。很无奈的我们便想，是不是题目比较阴险必须用64位整数才可以过呢？其实赛后来看，这绝对是不必要的想法。因为当时至少有十多支队伍过了C，不少队伍都是作为第四道题过的C，且其中不乏1Y。这可以推断出，WA不大可能源于出题人的阴险，而是应该源于我们自身的问题。不过，当时的情况是，改了long long，依然WA。这期间，4题甚至5题的队伍越来越多，我们的rank一直在跌，前景非常不容乐观。看来我的缺点就是这样……处于顺境的时候容易被冲昏头脑，只有适当的逆境才能达到冷静。我再次看T_T的代码，不漏过一个字符的认真看，终于发现了程序中的低级bug。——只是注释掉了一行代码，程序就AC了。那个错误的根本原因是T_T在写那一小段时稍微有点想错了，而我从局外的角度看这段代码时，本应很快意识到这个几近愚蠢的错误，然而由于第一遍的不专心，我直到若干次WA之后第二遍阅读代码时才发现了它，这题做得不好，我至少应该承担一半的责任。 还好，虽然C题罚时比较多，在我们前四道题全部1Y的基础上，终于五题的我们名次还不错。接下来可做的题只有B和D。前者是数论题，我已经推导出了一个结果，有算法了；后者是纯粹的高斯消元而已；二者的共同点是都需要用到大数，最好是用Java来写。嗯……应该是我们队的另一个缺陷吧，我们没有人能把Java写得跟C++一样熟，所以必须用Java写的题在敲代码的速度上是吃亏的，甚至有些有关语言特性的东西还需要在赛场上试一试才知道。我们三人中写Java最熟练的xgy队长觉得B似乎更容易实现，于是便上去写。花费了比通常要多的时间，但却是严格地按照我给定的算法写出来的，没想到交上去以后WA了，只好打印出来交给我们查错，而他自己接着写D。——我想在这时我们的缺陷就完全暴露出来了：剩下两道可以写的题都需要用Java写，而赛前的训练中用Java写过题的竟只有xgy一人。这导致此时能写D的仍然只有xgy，而自己写的B还没能AC的xgy恐怕无法专心全力去写D，T_T和我在下面对着打印出来的B的Java代码YY其bug……T_T和我一致认为那Java代码十分“诡异”，表达算法时显得很不直白，但分析的结果也无法找到错误。我建议把那代码改成不那么诡异的形式再试试，大家同意了，便放下D来改B的代码。终于改出了比较清晰易懂的代码以后，测试的结果却似乎与刚才“诡异”的程序并无区别……（期间我还忍不住下手帮着写了几行，现在回忆时发现，赛场上的那几行其实是我平生第一次写Java代码- -。。。）貌似又是在我的撺掇下，把那个改完以后完全看不到区别的程序提交了，结果又是WA。这时进入比赛的最后一小时已经有一段时间了，封了board，各个队伍的排名已经不再实时公布，但从现场升起的气球情况来看，貌似已经有七题的队伍了，如果我们再不抓紧时间搞出第六题，能否拿到金牌相当未知……这时xgy继续写不知道有多大希望的D，而T_T和我做了一个相当正确的决定：我们从题意开始，对推导的过程完整地讨论地检查了一遍。期间，T_T的一句话启发了我，我发现原来是我在一开始的数学推导中少考虑了一种情况，难怪一直WA到死……我谢罪。。。还好把那种情况的代码加到程序里并不困难，加上以后就AC了，在比赛还剩十多分钟的时候，我们终于六题。 看到屏幕上的Yes的时候，我们全都激动地站了起来振臂欢呼。这是出现了一个喜剧性的小插曲，比赛的志愿者MM给我们送气球时弄错了：应该给我们的是B题对应的浅紫色气球，她却拿来了J题对应的深紫色气球。据说当时观众席上立刻一片哗然，没人想到会有队伍在比赛中把最不可做的J给做出来。周维民教授（ICPC中国区秘书长）也马上带着一堆摄影记者走过来对着我们不住地拍照。（嗯，以上文字有野史的风范，若有不确切之处请一笑而过^_^。。。） 最后几分钟的时间里xgy在敲D，不过花在这题上的时间和精力的确是比较少，加之我们不知道高斯消元在无需考虑精度的情况下会有比标准的做法好写很多的实现，所以直到最后也没能写完。至于旁边我们的Sirius凭借最后一分钟提交的D题冲至第五的神迹，我们也只有深深膜拜了。。。Orz 金牌到手的我们无忧无虑，下午我玩了会儿牌，听了会儿音乐，晚上代表队伍上台领奖（非常感谢队里的两位gg给我这个荣耀的时刻）。 接下来的时间里，Genesis与Sirius们都兴高采烈，发挥失误获得银牌的三个gdb则无法避免地淡淡失落。不过大家都知道团结勤奋的gdb实力还是相当强的，相信你们下次在成都的比赛中会弥补这次的遗憾！ 其实我发现……比赛结束以后的事情我大都不太清楚了，因为颁奖结束的那天晚上起我就全身心地沉迷在一本奇书里。包括在归途火车上也一直是捧着电脑在进行一千多页的脑力激荡与思维历险……嗯，接下来我会抽空慢慢写点关于GEB的读后感的，虽然一下子很难整理出繁复的思绪。。。 哦……这次的哈尔滨之行Sirius与gdb各自也有非常精彩的小结，请原谅这篇略有些虎头蛇尾的文章吧，这五千多字已经写得我要吐血啦。。。有什么脱误遗漏错愕指出请指出，我一定修改。 好了，下一站杭州，在自己家门口比赛，相信通过对哈尔滨之行的总结，我们会越发完美。Genesis加油！ http://cuitianyi.com/blog/acmicpc-asia-harbin-2008-%e5%b0%8f%e7%bb%93/ 按：数论貌似是我目前还接触太少的领域，遵从vls的推荐借了北大出版社的《简明数论》来浏览，还是很好玩儿的……下面是从中总结的一些比较新鲜的结论。 {a_i} 的最大公约数等于 {a_i} 的所有整系数线性组合组成的集合中的最小正整数； 事实上，被最大公约数整除，等价于能表示成整系数线性组合。 一次不定方程 ∑a_i*x_i=c 有解的充要条件是 c|({a_i})； 解一次不定方程的算法（待实现）。 x^2+y^2=z^2 的本原解：x=r^2-s^2, y=2rs, z=r^2+s^2； 其中r>s>0, (s,r)=1, 2不整除r+s； 等价地刻画了单位圆周上的有理点。 Chebyshev不等式：，； 其实重点在于：O(π(x))=x/log x，O(p_n)=n log n。 （π(x)即不大于x的素数个数；p_n即第n个素数。） 数论函数：[完全]积性函数的充要条件； 除数和函数； F(n)=∑_{d|n}f(d) 保持f(n)的积性。（除数即Divisor） Mobius函数：； 事实上与容斥原理很有关联； 引理： 集合A中与K互质的元素个数，其中A_d是A中被d整除的子集； 将A取不超过x的实数，K取不超过的所有素数的乘积，可得，这样可以在已知不超过的素数的前提下求π(x)。 从算法的角度看似无意义？ http://cuitianyi.com/blog/%e3%80%8a%e7%ae%80%e6%98%8e%e6%95%b0%e8%ae%ba%e3%80%8b%e7%9a%84%e7%ae%80%e6%98%8e%e7%ac%94%e8%ae%b0%ef%bc%88%e4%b8%8a%ef%bc%89%ef%bc%9a112%e8%8a%82/ 上周六，第一场正式的ACM/ICPC比赛，哈尔滨赛区网络预赛，结束以后，我感冒了。（……有联系么？- -）直到今天，仍处于很难受的状态。近几年，我的感冒一年最多一两次，但每次都让我难受得要命。 昨天上午，我坐在电脑前，头昏脑胀、浑身无力、流涕不止，为翘课且没交作业而沮丧。听了几首巴赫、几首莫扎特，罕见地觉得不合口味，判断为感冒影响了听力。非常偶然地，我打开了Bernstein指挥的“命运”，贝多芬第五交响曲…… 我有一年多没听过贝多芬了，上次听大概是07年8月卓越上Günter Wand的贝交全集打折的时候买了一套，但只听了一两遍就放下了。因为不喜欢，甚至厌恶——声嘶力竭的铜管，持续轰鸣的定音鼓，那种让人想起军乐的进行曲色彩，以及没完没了的表现斗争与反抗的不和谐音。——贝多芬交响曲并非全都如此，但至少从小听人津津乐道的“英雄”第三、“命运”第五以及“合唱”第九或多或少带有这些特质。我能接受的最富斗争色彩的古典乐，恐怕止于肖邦的“革命”练习曲，至少钢琴的音色总还是悠扬的，不像富于煽动的铜管。 但昨天，轻微的肉体上的痛苦，突然让我开始理解贝多芬！——斗争的主题，并不一定代表低下的音乐。（遗憾的是，我以前的看法与此相反。）但是，如果带着富足、平和甚至出世的心境去聆听贝多芬那些富有斗争性的篇章，只会听到无谓的嘈杂与吵闹，难以感受其中的力量之美。（被问及“假设一个唱片店飞向太空，你认为外星人会喜欢怎样的古典排行榜”时，Glenn Gould答道：“这很难讲，但我认为有一个作曲家不会上榜，那就是贝多芬———这不包括他的晚期作品和几首早期作品。”） 后来，我又在看Karajan八十年代指挥贝交的视频，重点在第九交响曲“合唱"的第四乐章。我喜爱合唱这门艺术，目前还有加入合唱团的打算（虽然声音和体貌都不一定合格= =）。然而，我曾无知地认为欢乐的主题也是低下的（貌似这与我的古典启蒙老师约翰·施特劳斯被我始乱终弃有关-____-）。对欢乐的赞颂，在我看来也许不如对神的赞颂那样有感染力。但要明白，贝多芬写作此曲时的晚年境遇（一个全无听觉的音乐家）应该是极度痛苦的！在欢乐中歌颂欢乐，类似于“真是好啊真是好”，是无谓且无味的。但在痛苦中对欢乐的追寻，如同在尘世中歌颂天堂，给痛苦中的人们带来的是大彻大悟般的洗涤。 合唱团唱出《欢乐颂》的主旋律，每一个音节都清晰地斩钉截铁。激动得脸部发热、浑身冒汗的我甚至觉得困扰多天的感冒已经不药而愈了！直到Karajan挥下最后一个短促坚定的手势，乐声开始绕梁，才意识到感冒之蛊只是暂时蛰伏，却从未离我而去……我还是得边擤鼻涕边咳嗽边写blog…… ~~~~~~~~我讨厌感冒的分割线~~~~~~~~ 现在要隆重宣布的是……本blog要转型了！从这篇开始，它将成为一个主要谈论古典音乐、兼谈个人生活的blog。 其实，不知是否有人注意到，本blog是经历过转型的。最初写blog的时候，这里的主题是现代诗，有不少作品及创作谈之类的东西。后来，由于参加各种编程竞赛，主题变成了与编程相关的种种，尤其是算法相关的东西很有一些。嗯，那时的名字叫”左手程序右手诗”。而现在，很久没更新了，这两个主题中的任何一个都让我提不起兴趣写到blog里，可悲地发现似乎进入了blogging的倦怠期。解决的方法就是，转型！趁现在处于狂热喜爱古典音乐的时期，多听，多写。 我不清楚是什么样的人在订阅我的blog。有一天我很惊讶地发现仅在Google Reader上的订阅数就有三位数！这鞭策我在保持风格的前提下，注重自己文章的质量。希望正在阅读的你也能喜欢我接下来关于古典音乐的文章。 p.s. 你见过被手握自己学分的任课教师逼迫催促更新的blogger吗？555~我真可怜啊。。。 http://cuitianyi.com/blog/%e7%97%85%e4%b8%ad%e7%9a%84%e8%b4%9d%e5%a4%9a%e8%8a%ac%ef%bc%8c%e5%8f%8a%e5%85%b6%e5%ae%83/