44天的集训已经接近尾声，明天就是考验我们的时候了。上午8:30-11:30做四道题，然后，下午3点就能出成绩。这就是信息学竞赛的强大之处——上午的竞赛，下午出成绩。
今年的NOIP似乎有许多变化。系统改用NOI Linux。一个基于Ubuntu 7.10的残废系统。7.10古老的内核导致NOI Linux十分不易在电脑上安装。用了一个糙到极致的Mac主题，其他主题都被删了。另一个变故，由于北京初赛有所谓的“缺考”，减少了5个名额。然而这还不是真正的噩梦。今年的一等奖分配有了变化，北京只分到了17个，减去5个，只剩12个……要知道去年是30+。
于是不得不变化策略。本来准备AC两道题，再骗点分搞定，现在则必须在另外两道题上下功夫了。不过，不论一等奖如何分配，自己的发挥是最重要的。所以，不管水平如何，名额怎样，我们都要满怀信心地进机房，我们都要确保简单的题AC——这样，无论如何不会留下遗憾。
明天下午，游戏结果就将揭晓。无论如何，我已经对09年12月 – 10年11月有了个计划。明天再写吧。
今天是周五，明天是周六。我们的时间还剩下一周。
过去的一周，参加了若干模拟赛。虽然仍然极度受虐，但已经较一个月前的两位数分增加到三位数了（破百）。
这周高三的几个人加入集训，看到他们在刷USACO，谈论着1.2、1.3，我乐了。咱可是刷到2.4的人啊！刷USACO的那段时间，我还真是收获不小。不过，我不打算再往后刷了。这剩下的一周，看看一些常用的算法，做做经典的题，嗯。然后，坦然地面对复赛。
另：与OIer们分享一句话：“骗分的最高境界就是不骗分。”（来源：我是智障写的《骗分导论》，今天空虚时看了一下）
今天我写了一个用SPFA求最短路的小程序，Penhu同学想让我给他一个伪代码，于是我写了一个”SPFA.wdm”。为了有意思起见，我煞有其事地创造了一种完整的程序设计语言。因为wdm没有实际意义，因此改名DSL(Damn Simple Language)。写完后，Gedit自作聪明地用VHDL的语法给程序染了色，还真像那么回事。实际上，后来发现VHDL和DSL的相似度并不高，只是凑巧罢了。
Penhu同学在看到DSL后，灵感一现写出了Kubla语言的SPFA。一点很贱的是，Kubla内置的算法库里内置SPFA方法。不过，还是挺王道的，到头下来程序只有6行。分号后面是单行注释，叹号中间是多行注释。
! SPFA, in kubla language. Kubia, next generation language designed by Penhu201. SPFA, a alg to solve SSSP problem. ! (alg) ;包含一个库：alg（常见的算法） |\n/| ;输入n |\|\graph/|/| ;两个输入符号，代表输入二维数组graph d[n] <- alg`SPFA . graph . 1 . i, 2 -- n ;调用alg库的SPFA方法，传三个参数，句号作为间隔。返回值赋给d数组。 i, 1 -- n : 1 ;循环，从1到n，循环变量为i，间隔1 |/"To $i: $d[i]"\| ;输出
-- SPFA, in DSL(Damn simple language). -- DSL, a missing programming language designed by Xhacker Liu. -- SPFA, a alg to solve SSSP problem. inc io, ds io.fopen("Graph.in") -> fin io.input(fin, "%d") -> nodes ds.graph.matrix.input(fin) -> graph d[1, 2 to 10] <- 0, INFINITY ds.queue.init() -> queue ds.queue.in(queue, 1) while ~ds.queue.empty(queue) n <- ds.queue.out(queue) loop i; 1 to nodes; 1 if d[n] + graph[n][i] < d[i] d[n] + graph[n][i] -> d[i] ds.queue.in(queue, i) loop i; 2 to nodes; 1 io.output(stdout, "To $i: $d[i]")
备注：以上染色仅供参考。Kubla是用C的语法染的色，DSL使用VHDL。
半年就这么过去了，Ubuntu新版如期而至。
新的启动画面、软件中心、Ubuntu One、Gnome 2.28、Firefox 3.5，我们能看到的好像就是这些。然而，9.10的进步是远远不止这些的。
更好的使用感受。作为Linux for human beings，Ubuntu在每一个细节上都有很大的提高——虽然还不完美。
我从06年开始接触Ubuntu，现在已经有三个年头。每一个新版的发布，都是如此令人激动。这三年下来，Ubuntu的进步绝对是巨大的。6.06，我们甚至用不到全中文的Ubuntu；7.04，我们还要为挂载NTFS分区劳神、还要为安装驱动苦恼；7.10，广大用户可以直接开启Compiz Fusion带来的神奇特效；8.04，我们感受到了一个健壮、稳定的Ubuntu；8.10，我们把它装在了小小的USB盘里启动；9.04，我们看到了令人心情愉快的notify……
这三年来，Ubuntu从一个初出茅庐的发行版变成了现在Linux桌面的代名词。这时，再让我们看看所谓的“视窗”系统。8年后，人们还在用着01年雷德蒙德的产物。这从一个侧面反映出所谓的第七代系统较Xp而言没有多少提高——它似乎增加了一个新的任务栏，会使人们需要更多的操作才能打开窗口。若干年前，Linux还是多么丑陋，以至于没有桌面用户会去用它。而如今，满眼都是“Ubuntu 9.10 vs. Windows 7”。当然，Ubuntu在桌面领域距离Windows、Mac差距仍然不小，但先不论胜负，这种比较已经说明问题了。Ubuntu每个版本都注重用户真正的体验，而Windows，是在吃老本。几年之后的Ubuntu将不可小视。
看看这个新特性页面：http://www.ubuntu.com/products/whatisubuntu/910features，制作得十分精美。不禁感叹，Linux再也不是Hacker和Geek专用的系统，Ubuntu把它带给了全人类。
今天，初赛的成绩出来了，我们参加的18个人过去了17个（其中8人参加集训、未参加集训的有3个高三）。只有黄轶唯悲情了。于是，明天开始，集训将减少为7人。
还有20多天（已经不是一个月了），我的终极目标是350/400，如今已经安全地迈过了第一道坎。
昨晚参加了Curimit神牛的模拟赛（难度“略”高于NOIP）。刚开始一看，先被吓到了。后来做着做着觉着还可以，最后竟然做出来3道。于是昨晚自我感觉良好。今天上午一看，我一下蒙了，只有可怜的30/400。一道题得了10分，另一道20。
USACO的题倒是刷的挺顺利，现在已经2.3了。
黄轶唯走了，倒也清静了。机房将不再是游戏厅，CS、韦诺、视频将会消失。
再见，黄轶唯。
初赛的成绩一直还没有下来，不过我的58分没问题。
这几天一直在刷USACO的题，现在一直在第一章徘徊。虽然说第一章真的很水，不过要把程序写出来，也没有那么简单。我曾经写出过极其恶心的代码，比如（你得拖底下的滚动条看）：
... for(m[1] = 0; m[1] <= 3; m[1]++) { for(m[2] = 0; m[2] <= 3; m[2]++) { for(m[3] = 0; m[3] <= 3; m[3]++) { for(m[4] = 0; m[4] <= 3; m[4]++) { for(m[5] = 0; m[5] <= 3; m[5]++) { for(m[6] = 0; m[6] <= 3; m[6]++) { for(m[7] = 0; m[7] <= 3; m[7]++) { for(m[8] = 0; m[8] <= 3; m[8]++) { for(m[9] = 0; m[9] <= 3; m[9]++) { if(is_finish(cur_clocks)) { cur_len = 0; for(i = 1; i <= 9; i++) cur_len += m[i]; if(cur_len == shortest_len) { count++; j = 0; for(i = 1; i <= 9; i++) { if(m[i] > 0) { for(k = 1; k <= m[i]; k++) { j++; moves[count][j] = i; } } } } else if(cur_len < shortest_len) { count = 1; shortest_len = cur_len; j = 0; for(i = 1; i <= 9; i++) { if(m[i] > 0) { for(k = 1; k <= m[i]; k++) { j++; moves[count][j] = i; } } } } } move(cur_clocks, 9); } move(cur_clocks, 8); } move(cur_clocks, 7); } move(cur_clocks, 6); } move(cur_clocks, 5); } move(cur_clocks, 4); } move(cur_clocks, 3); } move(cur_clocks, 2); } move(cur_clocks, 1); } ...
这实在是太糙了……不过USACO数据弱，竟然过了。于是安慰自己，这种题谈不上什么高级的算法，暴力搜索就好，K.I.S.S.嘛，好吧。至少针对水题，用点水方法也不是不行。
Wave已经用上了，可是，没有人跟我一块Wave……于是什么也感受不出来。更杯具的是，咱现在还没法发邀请。嗯，那就先放放吧，等以后大家都用上应该就能感受到威力了。
今天打开Synaptic，瞎翻，发现GNOME Shell就在源里。一阵欣喜，然后安装。现在正在体验，感觉不错，稳定性也挺好。只是因为是早期版本，好多功能还有待完善。但这种形式我个人认为还是不错的。
这几天USACO保持一天一个Section的进度，后天就能昂首挺进第二章了。
水果新出了鼠标，如果未来相关的Linux驱动完善的话，可考虑入手一。
周末的时候，看到这里的抽Wave邀请的活动，结果，RP爆发：http://google.org.cn/posts/happy-weekend-google-wave-winners.html
于是，也就是说，我应该这两天就能用上Wave了。
估计与初赛RP爆差有关。
昨天的初赛弄得我十分不爽。一些很烧饼的题做糙了。一考完，我们几个就悲情地在初中楼2层的楼道电脑敲程序，果然残了。杨进基正在上面吼。几个人对了一下答案，我和胡颖健差不多悲情，而黄轶唯则是已经释然了，他后60分得了两分。后来，我们借C(S)消愁。再后来，借C(语言)消愁愁更愁。
于是昨天整下午+晚上十分不爽。网上找了一份标准答案，看了看，得55分。杯具了。昨晚一个人寂寞地在宿舍，把Geany翻完了，今天给作者发过去。另外，Ubuntu上放Keynote导出的QuickTime文件有戏了。今天Gnome-Mplayer的作者管我要一个文件，他想试试。嗯，挺好。
今天，得到可靠消息，20多分就能过初赛。转悲为喜。
于是，我将继续一个月的战斗，为…（你猜？）而战斗。
虽然还有一些时间，但我已经迫不及待上考场了。初赛说起来就是这么简单。但，往往简单的东西也是致命的。初赛，只能过，不能被虐。没有退路。
所以，再看看往年的题，再看看基本的算法，各种排序、各种查找、各种各种。明天秒初赛。
在N天的集训后，终于回家了，躺在床上听last.fm，真爽。过了初赛后，准备淘个耳机。
今天发现GNOME里面有一个叫做Hamster的好东西，应该说很适合我。它的中文名叫“时间追踪器”，可以追踪你每一分钟在做什么，玩游戏花了多少时间等等。（当然它不是自动的，需要你手工输入）这样，每天晚上我可以清晰地盘点一下一天都干了什么。
今天看了些初赛题，还看了看KMP算法。说起KMP，就不得不提到Knuth这个我十分钦佩的人。今天就不说他了，以后有时间再说。KMP算法略难理解，于是今天下午我在机房给大家讲。说老实话，这个要讲出来确实不好讲，于是，我几乎是：“这个……恩，好像是这样的……哦，对不起，刚才说错了……”本来就麻烦的东西被我这么一折腾，大家都糊涂了。在此，我诚恳地向大家道歉。不过索性最后还是让大多数人明白了。为了某些管我要程序的人，我也贴贴代码。
#include <stdio.h> #define MAX_STR_LEN 101 #define MAX_PATTERN_LEN 51 char str[MAX_STR_LEN]; char pattern[MAX_PATTERN_LEN]; int next[MAX_PATTERN_LEN]; void genNext(); int findPos(); int main() { char ch; /* 输入主串和待匹配字符串 */ printf("Enter string: "); str[0] = 0; /* str[0]存储字符串长度 */ while((ch = getchar()) != '\n') { str[0]++; str[str[0]] = ch; } printf("Enter pattern: "); pattern[0] = 0; /* pattern[0]存储字符串长度 */ while((ch = getchar()) != '\n') { pattern[0]++; pattern[pattern[0]] = ch; } genNext(); /* 生成待匹配字符串的next数组 */ int pos; pos = findPos(); /* 开始匹配 */ if(pos == 0) printf("Substr not found.\n"); /* 未找到 */ else printf("Position: %d\n", pos); return 0; } void genNext() { int i = 1, j = 0; next[1] = next[0] = 0; while(i < pattern[0]) { if(j == 0 || pattern[i] == pattern[j]) { i++; j++; next[i] = j; } else j = next[j]; } } int findPos() { int i = 1, j = 1; while(i <= str[0] && j <= pattern[0]) { if(j == 0 || str[i] == pattern[j]) { i++; j++; } else j = next[j]; } if(j > pattern[0]) return i - pattern[0]; else return 0; }
今天Blog的评论达到100条（不含Spam），我决定开瓶鲜橙多庆祝一下。在此感谢所有支持我的Blog的人。
另：最近玩 Gnome方块 有点上瘾，得适可而止。/* 里面有一个阴冷的Bastard Mode，害死我了 */