0xBABAF000L - Geeky humor

0xBABAF000L 是一系列的漫画，很有Geek风格，尤其是UNIX Geek。我是通过Ai.Freedom同志的这篇post得知的。由于Ai.Freedom同志的介绍已经十分详细，我就不重复工作了，下面列出几个我比较喜欢的。

首先说一下主页。你也许已经看出来他们各自说的是谁，而其中The Bills 的介绍已经非常明确地把Microsoft讽刺了一番——他们的数量数不清, 每个都完全一样(虽然有时你能通过他们的衬衫的颜色分辨他们). 他们虽然很呆板, 但很恭敬, 也乐于助人. 他们的默认设置让人不爽, 总是把问题重复问你至少两遍, 却从不理会你的回答.（注：Ai.Freedom同志的译文）

接下来一个个说。

• http://tnerual.eriogerg.free.fr/0xBABAF000L/1_en.html

  这个还要用long long呢。就现在的机器说，long 就够惨的了。

• 从这张开始，一直到strip 6。

  SSH 固然安全，但terminal 并不是人人都能用的，友好的用户界面也很重要。最后一句尤其经典——"quit your bullshit and fetch me a gnome!"

• 这两张——1 2

  对死锁的一个形象解释。不过，优先级对调可不是我们想要的。

• 这一张。

  这是所谓的……“暴力搜索”？好在看来还有剪枝。

• 这一张。

  感觉这里的Debby 像是在说我～

• 从这张开始，一直到strip 15。

  What Microsoft realy is... GNUT 的疑惑不无道理，那个问题怎么能回答“OK”呢。"bill < yes", I know what you're to say.

• 这一张。

  Newton 的煮鸡蛋？

• 这一张。

  Sigh, isn't everything 42?

• 这一张。

  我比较喜欢这里对炒作的讽刺。

明天初赛

如题。来点组合数学。

Catalan & Stirling

首先是Catalan。Catalan数定义为C_n = (2n C n) / (n+1)。该数列的意义：C_n表示从(0, 0)到(n, n) 的下对角线格路径的条数。（晕乎？）换种说法，在坐标平面上，有一只蜘蛛在点(0, 0)处。它想走到(n, n)处。这只蜘蛛每次只能向右或向下移动一个单位。如果这蜘蛛从没到达直线y=x的上方（但是可以接触），那么它就有总共C_n种走法。与之等价的问题还有剧院的自动售票机等。

从Catalan数可以衍生出拟-Catalan数——C^*_n = n!C_n-1。该数的意义在《组合数学》中是以乘法格式的形式给出的，不过有点抽象。广大的OIer基本都知道合并果子，现以之为例。如果认为将第x堆与第y堆合并和将第y堆与第x堆合并是不一样的，那么将所有的果子合并为一堆的顺序就有C^*_n种。

接下来是两类Stirling数。第一类s(p, k)指将p个物体排成k个圈的方法数，由此可以证明其递归公式：s(p, k) = (p-1)s(p-1, k)+s(p-1, k-1)，方法类似于归纳法。第二类与之很相似，S(p, k)表示将p个数分成k分的方法数，递归公式：S(p, k) = kS(p-1, k)+S(p-1, k-1)。

去年就考了第二类Stirling，今年估计不会了吧。

庆祝“神舟七号”发射成功

如题。我一直看到张开太阳能电池板。

有人知道一些轨道参数吗？我想了解了解。

dd_engi的一道题——字典序最小的LIS

这几天基本在学校机房混，看着他们玩DNF（当然我不会），以幸灾乐祸为主。我这几天眼睛状态创造了历史新低，结果有一节政治课我60%的时间是——正襟危坐，面向黑板和老师，毫无表情，双眼紧闭。毕竟是理科班，不用太客气。

前几天看完了《穆斯林的葬礼》。这部作品写得很悲惨，我从来没有被感动到这种程度。心情一连两天处于低潮状态。用书中的一句话，全书也不过是一个字——情。在这里向没有读过的人推荐一下，不会白读的。

\end{nonsense} \begin{point}

此题出自dd_engi同学在2008.9.20 出的一套模拟赛中。我大略看了一下题，觉得这到比较简单，或者说只看懂了这一道题（毕竟它最短啊），开始了思考。此题完全是LIS问题的一个基本变形，可以说会LIS就能做上这道题。我用的LIS是最简单的O(n²)的算法，再添上那个简单变形。比较不巧，程序不在这里，改天发上来。这个算法由于复杂度的原因，只能过5个测试点，学会了O(nlogn)的再改过来。

那个问题的进展

如题。现在感觉基本可以——

我们可以把偏转电场分为无穷多个小块，这样每个小块都可以看作匀强电场，在第一个小块里路径相同，因而以同样的角度进入同样的下一块，所以大概一样。但是懒得计算究竟是否成立，这几天太累。

一个问题：带电粒子的轨迹

一些题外话。这几天没有抽出更新时间，现在在学校机房。终于可以利用自习课搞竞赛了，于是用了很多时间。昨天才发现原来Topology 译作“拓扑学”，看来犯了一个大错。那个post已删除。现在开始以做题为主了，尽管算法复习还没完事呢。晚上在家时继续复习。

Le point. 问题来源于物理课上的灵感。最近学了“带电粒子在电场中的运动”。这种运动是，粒子只受电场力作用，静止开始，经过匀强加速电场，垂直进入匀强偏转电场，最后出来。这种运动有一个性质，说的是无论粒子带电量、质量如何，只要是在同一位置静止开始，轨迹相同。当然速度大小不尽一致。我想到的问题是，如果偏转电场不是匀强电场，此结论是否成立？更一般的，给定空间中已知电场，不同的带电粒子在同一点静止释放，其轨迹是否相同？问了老师（也是老大），告诉我不知道，但大概不能。我觉得那个一般的大概不行，但是那个特殊的呢？不敢确定。我既没有举出反例，也没有证明（不论是正证还是反证）。大家试试。

中秋节快乐

如题。我不想说太多，我现在离中国文化太远了。即使说了，未免让人笑掉大牙。还说的出口的就是今天回老家一个大家庭的人一起过节。把昨天买的那本The Adventures of Tom Sawyer在那边差不多全看完了。书放在老妈那里，有一段时间书没在我这里，否则那一本书根本不够今天一天的。除了这个，无甚事可做，由于失眠的毛病，更惨。这已经不少了，所以

\end

New desk

你看到的是我经过疯狂改动的新书桌。我在学习法语上又一次向中国的教育让步。互联网上的内容无法传递足够的信息。

今天买书时很囧，买了一本Software Engineering - A Practitioner's Approach by Roger S Pressman，回家后发现严重破损。连续六七页大面积损伤，其中有两页近四分之一的内容不见踪影。遂返书店，商议换书。书店虽同意，但连我买的那本破书在内总共就剩两本此书，另外那本也破了。无奈之下，拿了另外那本破的相对轻一点的。

今天买的书还有两本法语教科书（全国高校统编）（一、二）及其参考书（也即，练习参考答案），还有第一册的配套磁带；一本常用词汇3000（当然也是le Français）；一本The Adventures of Tom Sawyer英文改写版；一本Topology。有了这些书，桌子可以大手术了。去掉了一些水平较差的书，放上了这些新书。中国人写的计算机书似乎质量都偏差，只有老谭的讲语言的书相对有些可看性。我那个小书架上已经全是我自己的书了（原来那本同学的《解析几何》在数学那格里），不过那两本《高等数学》还是同学的。那两本字典是不是显得太寒酸啦，哈哈？Oui, Oui.

终于做出来了：无穷大带电平面的电场

题目自出，源自前几天的物理竞赛。大致如下：

无穷大均匀带电平面，描述其电场。

首先可以通过电场线的性质的得到这是匀强电场。这样的平面等价于静电平衡的导体，电场线垂直于表面，又电场线只能终止于该平面或无穷远，因而是匀强电场。关于另一个问题，见下面。

然而可以用微积分的方法得到定量的结果。如下，原创，来自Yap截图。

前面所说的另一个问题是电场线是否会弯曲。看出来没有？

À demain！

续：Dijkstra更详细的信息 及SPFA

昨天晚上实在是太晚了，脑子也乱了，有些东西没想起来。现在把关于Dijkstra 的剩余部分说一下。

上一个Post里的那个实现使用邻接矩阵存储图，隐式地使用了一个只出不进的队列。由于所有边权值非负，出队顶点的ans 值随时间递增。因此该算法正确。如果使用邻接表存储，复杂度为O(V²+E)，因而还是O(V²)。但如果想要用堆或RMQ优化，则必须使用邻接表存储，不然只能是浪费。我认为这些优化在竞赛中是不必要的，性价（Programming time）比太低。

有些人说SPFA很简单，我做了一下，却不这么认为。但也必须用它，如果有负权边的话。SPFA基本是一个做了剪枝的广搜，区别是不使用广搜中的visited标志而用路径长度判断，并因而需要一个in_queue判断。实现起来大致是搜索中，每次从队首取出一个顶点，对与之邻接的顶点松弛，被松弛的入队（已经在队里的不管），没有的不管。算法中需要显式地维护一个队列，复杂程度还可接受。

Next mission: Dijkstra

上一个post里描述了Floyd-Warshall 算法，它解决了每对顶点间的最短路径问题，其复杂度为O(V³)。当然，这个复杂度比较大，并且如果我们只需要求一对顶点间的最短路径，这是不必要的。因此我们研究单源最短路径问题。解决这类问题常用的算法有我们将要看到的Dijkstra 和另一个比较猥琐的SPFA。

这个Dijkstra 算法的限制是，图中不能含有负权边。SPFA没有这一限制，但如果已知图中没有负权边，通常优先选择Dijkstra。我想主要原因在于Dijkstra 的复杂度比较稳定，一个很简单的实现，可以稳定的为O(V²)。很明显这要快于Floyd-Warshall，不然它也没什么价值。对稀疏图的优化可以达到O(VlgV + ElgV)的复杂度，但我不用，因为如果碰上稠密图或是完全图，时间反而多了。它的竞争对手SPFA 复杂度一般为O(E)，不过某些情况下会变成O(VE)。这更危险。

下面是一个能正常运行的实现，由于较复杂，列出的内容较多。

int G[nmax][nmax], ans[nmax], pred[nmax];
bool processed[nmax];
int n, s;

int find_min()
{
 int i, min_id = _infty;
 for (i=1;i<=n;++i)
   if (!processed[i]&&ans[i]<ans[min_id])
     min_id=i;
 processed[min_id]=true;
 return min_id;
}

void relax(int a, int b)
{
 if (ans[a]+G[a][b] < ans[b])
   ans[b]=ans[a]+G[a][b], pred[b]=a;
}

void dijk_calc()
{
 int i;
 for (i=1;i<n;++i) //loops exactly n-1 times.
   {
     int p=find_min();
     int j;
     for (j=1;j<=n;++j) //for each vertex \in adj_p
 if (G[p][j])
   relax(p, j);
   }
}

前面所说的优化可以修改find_min()使用堆或是RMQ实现。尽管这是一个好算法，遇到负权边时也不得不换成SPFA了。有时间我会简要说明一下，extremely sleepy now.

Bonne nuit!

Floyd-Warshall 算法及其优化

今天是教师节，因而下午放假，有了些复习时间。上午挺强的，几个老师被我们用彩带一顿狂喷，有几个还被迫唱歌了。因为前方黑板被占（几个大字），有两个老师是站在后面上课的（后面有空黑板），这下我这类最后一排的有福了。不过后黑板平时无人使用，没放板擦、粉笔，两节课都是我主动到前面去拿来的。第一节是灵感突发，第二节我看没人接班，无奈，只得又去一趟。算是RP++吧。

好了，言归正传。Floyd-Warshall 算法解决了有向图中每对定点间最短路径的问题，时间O(V³)，空间O(V²)。适用条件是，换句话说限制是，不能有负权值环，当然还有，最多只能有一条从一个点到另一个点的弧（基本都是这样。不然，长的那个可以直接去掉，没用）。对于无向图，把一条边变成两条弧。尽管有负权值环时它不可用，但可以判断是否有负权值环，方法是再运行一次（不过代价不小）。

这是个动态规划算法，基本思想如下。如果顶点k在顶点i到顶点j的一条路径上，则称k为该路径的一个中间顶点。如果路径p是从i到j的最短路径且k是其中间顶点之一，则以k为界将该路径分成两段，每段都是最短路径。（不然的话会出来一个更短的。）相反，如果路径a, b分别是i->k, k->j的最短路径，将a和b合并起来的路径不一定是最短路径。为了得到最短路径，我们必须考察图中的所有顶点，以他们为中间顶点，合并起来才能是最短的。基于此，我们可以得到算法。用邻接矩阵表示图，算法如下（C++）。

for (int k=1;k<=n;++k)
  for (int i=1;i<=n;++i)
    if (ans[i][k] != _infty) //the one line optimization
      for (int j=1;j<=n;++j)
        ans[i][j]=min(ans[i][j], ans[i][k] + ans[k][j]);

那个仅一行的优化是我后加的，可以去掉。预处理时[i][i]为0，有弧的是权值，没有的是无穷大。_infty是预处理时当作无穷大的量。优化后的具体时间复杂度我一直没有做出来，总之松弛的界是Ω(VE)和O(V³)。这个算法极其简洁，我认为是最优美的算法。（其次是堆。）上述代码整合到程序中后，通过编译且运行正确。

RP骤减

Salut!

今天人品大概创造了历史新低。

首先是上午的体育课，乒乓球拍撞到案子上，坏了。然后是校服丢了。

接下来，中午有篮球赛，别人搬凳子时搬的正好是我的，结果赛后凳子没了。

最后，物理测验，一道并不难的题，一个条件没看到，做出来一个完全错误的答案。

看着吧！校服这问题最严重，而且还没解决。希望明天RP能好一点。

上次的那个积分，今天作出来了，不过好像是错的——成了负的。有点不可思议，但是却没找到错在哪里。转换成极坐标积的，由于幂次为负，结果是负的——以前有回算引力势能也是这问题。不过那是相对的，这电场强度……

初赛已经开始报名了，我还没大规模复习呢。该开始了，不过也该给法语安排点时间。读音成问题了，看来网络有着其局限性啊。

明天把Dijkstra & Floyd-Warshall 解决掉，后天争取把KMP 解决掉。接下来复习Binary Search Tree, 然后又有最小生成树~太乱了。学习又最近出现了点问题，看来真够忙的。

\end.

Bonne nuit!

Yet Another Day

今天是又一个周一。
照常上学。
今天，老大一整天没来。据说是下乡了？无从考证。总之过得挺逍遥，前几天刚学完逍遥游。
现在还不大熟悉blogspot—— so the posts will be a little boring。不知道这里用LaTeX是不是像wiki那样方便。如果还要自己编译，然后截图——so painstaking. Damn!
正在听Nightingale - Yanni。本想听Deilverance来着，但是Youtube的服务器还不是很快。中午时还很流畅，现在好像$\approx 1 kbps$？Deliverance风格比较豪放，原来只感觉到很乱，现在听出了其中韵味后便爱不释耳了。
今天中午从en.wikibooks上下载了一个教法语的书。To me, it's another world. 现在才明白那些老老师读L时为什么是那么一个奇怪的音，原来法语里是这么读的。哪天把法语学好了，回去跟英语老师耍两下。
下午上课时想起昨天物理竞赛中一个问题。说的是无穷大带电平面的电场特征，总电量没有明说，估计是无穷。从题目判断是匀强电场，但我一直在想怎么证明。列了一大堆积分式子最终得到了一个貌似挺简洁的式子——
可惜的是我已经积不出来了。

好了，现在在听Dance with a stranger。Ming Freeman 这个台湾人技术挺不错的。还有那个Kerry Hughes吹得也不错。Yanni乐队里还有一个Karen Briggs 我也很喜欢，去掉Yanni 就是她了。Deliverance 里如果没有Briggs 这段Solo 会减色不少。
突然想到，还有两个月就NOIP复赛了，还在这里做些无关Programming 的事。差的还不少呢，比如KMP还没有真正做出来一个能正常运行的——道可道，非常道；囧可囧，非常囧。
看看自己做的，真是非常萎靡——Youtube, NFS(Need For Speed? Or Network File System?)。ItoA(Introduction to Algorithms. <stdlib.h>里有个atoi)也好久没翻了，不过那一行”using namespace std;“还很顺手。
就到这里了，继续学法语。
Good evening.

The start

This is the starting post of this blog.

This blog will be mainly about the following topics.

• My daily life.
• Physics.
• Informatics, especially the OI.
• Programming.
• Free softwares, especially GNU.
• Mathematics.
• Schoolworks.(Maybe the endless exams~)

I'm doing nothing now, as this post is about nothing.