在多人 project 里, 代码注释是必不可少的东西, 通常注释都是解释此段程序的用途, 但下面这段注释却让人啼笑皆非:
//
// Dear maintainer:
//
// Once you are done trying to 'optimize' this routine,
// and have realized what a terrible mistake that was,
// please increment the following counter as a warning
// to the next guy:
//
// total_hours_wasted_here = 32
//
更多例子请见此帖.
(original post via walking randomly)
看到Terence 老师在他的博客上写过一篇文章, “Does one have to be a genius to do maths”, Zhiqiang 老师评论说“他写这种文章是站着说话不腰疼.”
的确, 对于Terence老师这种12岁就获得国际数奥金牌的人来说, 天赋毫无疑问是他走向成功的一个因素. 但是, Terence老师下面这段话却发人深省:
In some cases, an abundance of raw talent may end up (somewhat perversely) to actually be harmful for one’s long-term mathematical development; if solutions to problems come too easily, for instance, one may not put as much energy into working hard, asking dumb questions, or increasing one’s range, and thus may eventually cause one’s skills to stagnate. Also, if one is accustomed to easy success, one may not develop the patience necessary to deal with truly difficult problems. Talent is important, of course; but how one develops and nurtures it is even more so.
对应的译文: (来自LiuXiaochuan老师)
有的时候，大量的灵感和才智反而对长期的数学发展有害，试想如果在早期问题解决的太容易，一个人可能就不会刻苦努力，不会问一些“傻”的问题，不会尝试去扩展自己的领域，这样迟早造成灵感的枯竭。而且，如果一个人习惯了不大费时费力的小聪明，他就不能拥有解决真正困难的大问题所需要耐心，和坚韧的性格。聪明才智自然重要，但是如何发展和培养显然更加的重要。
反过来想自己, 即使在创新能力要求极强的信息学中, 原来最重要的不是自己的那些灵光一闪的新点子, 而是严谨踏实的学术作风.
前几天，在2009年全国信息学竞赛冬令营中，CCF 的杜秘书长提出了近期要取消 NOIp （全国信息学竞赛分区联赛）的一等奖保送资格，取而代之的是高考加分。有些人就不高兴了，我在冬令营的寝室里就经常听到众多选手的埋怨。接下来，CCF 的网站被黑了，大概也是这个原因。还有就是 cnBeta 里发的这一篇《论NOIP取消保送与CCF被黑——NOIP选手自白》。
第一题：给出一串已经拓扑好了的事件，求最短完成时间。
做滥了的题目啊，直接扫一边就出解，O(n)
第二题：给出第二周的歌曲排行榜和每首歌的歌曲排名变化（上升、下降、持平），求前一周的歌曲排行榜的一种可能解。
字符串处理的题目；
首先，我们把上升了的歌看作要把它往下移，而下降了的歌呢就看作要把它往上移，再把所有的持平歌去掉。
那么，现在的排行榜的首位肯定是下，而末位肯定是上了。
现在，找所有下一位是上的下节点。从这个下节点往上延伸到所有连着的下节点，而从这个上节点往下延伸到所有连着的上节点，把这两个模块互换即可。
第三题：你向银行贷款，告诉你你的贷款额、每月还款额和还款月数。求每个月的月利率（每个月银行先算利再让你还钱）
初以为这道题目十分简单，发现不然，这个题目列出来是个高次方程。其实是可以用log函数来解，但是对于有未知数的log函数，Pascal语言显得十分麻烦（几乎不可能实现）。所以，我在考试的时候使用了枚举的方法，得了60%的点。
但是我竟然忘记了世上有二分这样的好方法，其实，以你的总还款额/贷款额的利率（这个是绝对不可能达到的）为上界，下界为0，来二分求解，效果很好。但是虽然二分时间不超，但是发现有一个点竟然超过了int64和extended的届，呵呵。
第四题：走迷宫变形，有起始朝向，就是一秒钟内可以走1格、2格、3格，而且向左向右转也要耗费一秒。
爆容易的题目，难得写了。只有50×50的大小，不说广搜，深搜都能过啊。
课后孟LJ简单阐述了下搜索的优化，无非以下三种：
1、双向广搜（省时一半，较容易实现）；
2、普通判断剪枝（子树）；
3、估价函数剪枝（A*）。这种做法需要良好的估价能力，适合要打路径的题目。估价函数是一个可以求出从当前状态到目标状态的大概花费的函数，其值必须小于等于真实花费。所以，当走到一个（当前花费+估价花费>已知最小花费）的点时，完全可以把他的子树剪掉。这就是一种动态剪枝方法。效果甚佳，但本人未实现。
题一 进制转换：
负进制，短除法，但是余数小于0时要从上一位借位（商+1，余数-进制数）（LRJ大牛提出）
题二 乘积最大：
动规+递归
设d(i,j,k)为第i-j个数字中用k个乘号所取得的最大乘积。
转移方程（我直接用递归调用 ^_^）：
d(i,j,k)=max{数(第i到第t个字)*d(t,j,k-1)} (i<=t<=j-1)
临界：所有k=0的值就为原来的值。
题三 单词接龙：
求出一张表示每两个单词（有序）之间的增长字母数的表，根据这张表枚举第一个单词来搜。居然全不超时。但是发现有的单词可以用两遍，囧。
题四 方格取数：
一直没想通。LRJ的报告太草了。飞机的报告里面是“广搜式Dp，效率还不错。可能数据比较弱。”，囧；
Google了一下，发现“上帝的右手”大牛的报告不错：
两条路线同时进行的动态规划
阶段：按所走的步数来分阶段，从左上角走到右下角，共2n-1个步骤，故共2n-1个阶段。但，有两条线路，故每一阶段的状态都会复杂一些。
状态：有两线路同时走，在某阶段的某状态，要用两个坐标来分别表示两线路的两个点。如：第一阶段，共一个状态：(1,1),(1,1)；第二阶段，(1,2),(1,2);(1,2),(2,1);(2,1),(1,2);(2,1),(2,1)共四个状态。
由于在第k阶段的任何两个点的x,y坐标是有关系的：k+1=x+y。故可只用ｘ坐标来表示一点的坐标，故状态可表示为(x1,x2)，对应的y坐标为：y1=k+1-x1,y2=k+1-x2。
决策：若用0,1分别表示向下或向右走，则每个状态的可能决策有四种：(1,1),(0,0),(1,0),(0,1)。两个数值分别表示两个点的下一步走向。
状态转移方程：
设map(x,y)为方格图，f(k,x1,x2)表示第k个阶段走到(x1,x2)状态的最大和
f(0,1,1)＝map(x1,1+1-x1) 即map(1,1)
f(k,x1,x2)=max{f(k-1,x1′,x2′)+map(x1,y1)｜x1=x2，f(k-1,x1′,x2′)+map(x1,y1)＋map(x2,y2)｜x1<>x2} (x1′,x2′)表示可通过某决策到达(x1,x2)的所有点
明天再把第四题实现一下，就要进入恐怖的2001后了。。。
Welcome to WordPress. This is your first post. Edit or delete it, then start blogging!
Bottom post for my other posts in other website and BSPs.