流水帐

4、5 号从上海回来后，我自己的 CPU 就一直在以 100% 的负载在运行，每天平均睡不到 7 个小时，两周不到经历了各种事情，需要做个总结，否则下次再做总结恐怕写不下了。总结的风格依然是流水帐，技术加生活。

6 号上班做了一个 30+ 页的 PPT，对自己两个月的实习成果做一个总结，系统描述了整个视频生产系统的设计、编程实现、工具使用细节等等，晚上部门会议做了报告，效果还不错。 7、8 两天写出了自己人生的第一个 Python 脚本，脚本的功能是分析 nginx 访问日志，提取用户信息，判断某个用户是否完整看完了某个视频等等，形象化一点，就是把类似于下面的 log：

172.24.106.236 - - [01/Sep/2010:17:57:54 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:17:57:56 +0800] "-" 400 0 "-" "-" "-"
116.247.116.238 - - [01/Sep/2010:17:58:11 +0800] "GET /video/super_mpg_video/demo/taohua.f4v HTTP/1.1" 200 867480 "http://110.75.2.195/player/thvp/thVideoPlayer.swf?video=http://110.75.2.195/video/super_mpg_video/demo/taohua.f4v" "Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; Trident/4.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; Media Center PC 6.0; Tablet PC 2.0)" "-"
172.24.106.236 - - [01/Sep/2010:17:58:24 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:17:58:26 +0800] "-" 400 0 "-" "-" "-"
116.247.116.238 - - [01/Sep/2010:17:58:53 +0800] "GET /video/super_mpg_video/demo/taohua.f4v HTTP/1.1" 200 2097152 "http://110.75.2.195/player/thvp/thVideoPlayer.swf?video=http://110.75.2.195/video/super_mpg_video/demo/taohua.f4v" "Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; Trident/4.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; Media Center PC 6.0; Tablet PC 2.0)" "-"
172.24.106.236 - - [01/Sep/2010:17:58:55 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:17:58:56 +0800] "-" 400 0 "-" "-" "-"
172.24.106.236 - - [01/Sep/2010:17:59:25 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:17:59:26 +0800] "-" 400 0 "-" "-" "-"
172.24.106.236 - - [01/Sep/2010:17:59:55 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:17:59:56 +0800] "-" 400 0 "-" "-" "-"
172.24.106.236 - - [01/Sep/2010:18:00:25 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:18:00:26 +0800] "-" 400 0 "-" "-" "-"
59.42.126.48 - - [01/Sep/2010:18:00:51 +0800] "GET /video/super_mpg_video/20100826/moribingdu/moribingdu.f4v?th_key=4c7e3d82;1a7b6ebe;8292192f571cb7bbed3024e3998b5631&start=46582231&end=67158965 HTTP/1.1" 200 771638 "http://110.75.2.195/player/thvp/thVideoPlayer.swf?video=http://110.75.2.195/video/super_mpg_video/20100826/moribingdu/moribingdu.f4v&th_key=" "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 1.1.4322)" "-"
172.24.106.236 - - [01/Sep/2010:18:00:55 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:18:00:56 +0800] "-" 400 0 "-" "-" "-"
172.24.106.236 - - [01/Sep/2010:18:01:25 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:18:01:26 +0800] "-" 400 0 "-" "-" "-"
116.247.116.238 - - [01/Sep/2010:18:01:43 +0800] "GET /video/super_mpg_video/demo/taohua.f4v?start=20998492&end=41622742 HTTP/1.1" 200 20624263 "http://110.75.2.195/player/thvp/thVideoPlayer.swf?video=http://110.75.2.195/video/super_mpg_video/demo/taohua.f4v" "Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; Trident/4.0; SLCC2; .NET CLR 2.0.50727; .NET CLR 3.5.30729; .NET CLR 3.0.30729; Media Center PC 6.0; Tablet PC 2.0)" "-"
172.24.106.236 - - [01/Sep/2010:18:01:55 +0800] "-" 400 0 "-" "-" "-"
172.24.106.237 - - [01/Sep/2010:18:01:56 +0800] "-" 400 0 "-" "-" "-"

转换成相应形象化的显示：

整个 Python Script 大概 170 多行，同时封装了几十行的 Shell Script，算法是自己拍脑袋想出来的，具体描述可以另外写一篇技术文章了。脚本成形的过程渐渐体会到了 Python 的方便，结合了脚本语言的便捷性和高级语言的强大性，实乃居家旅行打家劫舍养家糊口之利器也。

9、10 两天请假。9 号睡了个小懒觉，然后去了趟校医院又开了一个星期的药，花掉 100 大洋左右，午饭后和同学会首，三人打车去西溪北园，准备 CUMCM 2010。到了那边也没什么事情，下午 3 点半左右又走回玉泉，拿了实习记录本，去找导师签字。到了导师公司又等了半个小时，跟导师汇报下暑假实习的情况和自己要找工作的打算，简单谈了谈，骗了个 90 分回来。晚饭在西溪北园食堂吃的，饭后想到布袋也住在北园，约好去看她，巧的是碰到了哈哈、小包、破船一行，他们前脚刚要走，我后脚就跟过来了。由于布袋还要导尿，不太方便，我就一个人在北园里面转了几圈，买了个大西瓜和几桶泡面——西瓜给布袋，泡面是自己的。与布袋聊了有两个小时吧，听了她在千岛湖训练的很多故事，以及体制内运动员训练的一些内幕，加上他们从千岛湖逃窜的惊险一幕，走之前和布袋掰了手腕——当然我是不会输的，不过布袋的力气已经非常出色了，我敢说一般的男生不是她的对手；享受了阿姨自制的酸奶，一袋乳酸菌，放入保温瓶，自然发酵，有点西藏酸奶的味道，赞的。

11 号早晨 8 点多拿到了 CUMCM 2010 的题目，A 题是一道看似简单但非常复杂的几何计算题，B 题就一句话——让你评估一下上海世博会的影响力。我倾向于选 B 题，因为看起来 A 题不太难——事实证明这个看起来不太难的结论是错误的，而且发挥余地有限；而 B 题的话只要找准一个切入点，成功的概率非常的大，即便不济，结果也总能忽悠出来的，不会太差。但是另外两名队友经过深思熟虑还是倾向于 A 题，于是少数服从多数，开始搞 A 题。第一天还是比较顺利的，我们顺利地解决了第一问，而第二问显然也是基于第一问的，这让我们每个人都面带笑容进入了梦乡——如此下去，第二天晚上就可以搞定第二问，第三天就有一整天的时间来写论文。

三人的分工基本上是这样，解题思路由三人共同商讨，然后 lyf 负责算积分表达式，ly 负责 MATLAB 编程和主要的数据拟合，我对 LaTeX 比较熟，所以除了解题思路和简单的数据处理，主要是看文档、写文档。

第一天的乐观到了第二天的傍晚就变成了焦虑——第二问的积分表达式由于过于复杂以致无法积出来，ly 和 lyf 用 MATLAB 算这个符号积分会卡住，我说 MATLAB 的符号计算比较弱，于是我在 Linux 平台上找到了著名的符号运算软件 Maxima，简单配置了 Emacs + imaxima，来算这个积分，Maxima 比较智能，会给你一些提示，比如提示你某个变量是 positive, negative or zero? 因为这个变量值不同积分结果也不同。总之积分表达式很复杂，我用 Maxima 算，不同的条件算出来也不一样，有时候算出来竟然是个复数！探索良久，符号积分的方法宣告失败，于是我们转而研究能否用数值积分的方法来算出一部分数据，打表拟合，然后根据拟合的结果判定拟合曲线和实际数据的相似性，确定最后的方程参数。但数值积分是一个比较棘手的东西，除了调用已有数学软件的方法，我们没有能力自己去写。ly 和 lyf 研究 matlab，我则找到了 maxima 的数值积分方法 romberg ，但是最后也宣告失败，至此，已经是第二天晚上 10 点多了……士气开始变的低落，ly 躺在床上，lyf 上网看看别的东西，我也在打酱油般地继续着一些无谓的探索——对于 A 题，我们已经黔驴技穷，换 B 题，还剩一天一夜，但是也有些来不及了——更重要的是大家都不太想做下去了。

12 号早晨大家都睡到自然醒，心情也不是太好——毕竟没有做出题目是件挺没面子的事情。我提议我们上午再按照打表的方法重新计算一下，然后大家随便算算，到中午基本上就彻底放弃了……于是乎我们就解脱了——ly 开始玩一些网页小游戏，lyf 上网或者单机游戏，我呢，看完了《当幸福来窍门》，修改了一下午自己的简历，找 Ouka 帮忙挑了挑刺，投了华为、网易等四五家公司。

13 号早晨老师打来电话，问我们论文咋么还不交，我们就坦白交代了说自己没有做出来，论文也没有写，于是我们的 CUMCM 2010 打酱油之旅就这样结束了。顺便提下这里提供的盒饭还是很不错的，虽然题目没有做出来，但还是赚了三天的伙食——太邪恶了……

离开西溪后冒着小雨骑车到了公司，刚好赶上早会。然后就开始了工作——看，角色转换如此之快。晚上 Google 的宣讲会加现场笔试，七点半到达现场，果然人山人海。8点挤到了位子，开始笔试。笔试总共 10 道选择和 3 道编程算法题目，时间是 90 分钟。选择题大概记得的几道：

以下各种排序种哪几种是稳定排序？
二叉树的前序、中序和后序遍历中，已知哪两种可以唯一却确定一棵二叉树？
${1, 2, 3, ..., 20}$ 集合中，挑选出 3 个数字，使得这 3 个数字不完全相邻，如 ${1, 2, 3}, {4, 5, 6}$，有多少种挑法？
32位机器表示的有符号数最小值是多少？
UNIX 文件的一道题目？
1024! 的结尾有多少个零？
C 语言指针的一道题？
数组中寻找中位数的算法复杂度是多少？
访问内存性能的一道题目。
忘了……

剩下的 3 道编程题目，第一道题目是编程求两个数组集合 A[m], B[n] 的交集；第二道是离散事件模拟，内容和严老那本经典的《数据结构——C 语言版》第 3 章栈和队列的最后一节一样；第三道应该是桶排序，就是给定 $n$ 个数，大小均在 $[1, n^2-1]$ ，在保证时间最优的前提下尽可能地优化空间。

Google 笔试的结果就是我理所当然的被 bs 了，虽然我觉得答得还算凑合吧，不过连面试的机会都不给，这个招聘也显得有点酱油的味道了——当然，比如像今年的百度之星冠军 hh，据说连 Google 的面试官都称之为大牛了，这是另类。

剩下的时间主要是借工作的时间学习，修炼秘密武器，看完了 W3Cschool 上的大部分教程，重点是关于 XML 的，XSL、XPath、XQuery、DTD、Schema 等等，研究了 Unicode 编码的基本知识（UTF-8、UTF-16、UTF-32，Big-Endian，Little-Endian 等），研究了 Python 读写 excel 文件的几个模块（xlrd, xlwt, xlutils, pyexcelerator）和 Python 有关 XML 的一些模块（lxml, jaxml 等），基本完成了《Learning Python》，除了 Class 看得比较少，剩下的就是熟悉一些常用的 mobule，多写写 Python 脚本，有时间再了解了解 Python 知名的开发框架，差不多了，剩下的按需学习。

14 号是好友 Ouka 同志的 22 岁生日，四年前的今日我拿到了化学竞赛的一等奖，收到 Ouka 祝福短信和亲切指导若干，四年后的今日，我在公司实习，趁午休时间简单改了个小程序，一程序员间独特的方式送出我的生日祝福。Happy Ouka, Fight Ouka。

17 号中午回到玉泉，参加了网易有道搜索的机试，两道题，两个小时，ZOJ 平台，20 个测试点，总分 270，有点类似于 NOI，是按照 Score 排名的。结果还是不错的，许久为碰 C++，还是拿下了 260 分，整场 50 人排名 15% 左右吧。两道题目如下：

奇偶矩阵

Time Limit: 1 Second Memory Limit: 32768 KB

给定一个 $N$ 行， $M$ 列的正整数组成的矩阵，求其中的一个子矩阵，使得奇数的个数与偶数的个数差值的绝对值最大

Input

每个文件包含一个测试数据。第一行是两个整数，$N$ ，$M$ 表示矩阵的大小 $1 \le N, M \le 100$ 。接下来 $N$ 行，每行 $M$ 个正整数，对应为矩阵中的元素，所有的数不超过 $2^30$ 。

Output

输出包含一行，为子矩阵中奇数个数与偶数个数差值绝对值的最大值。

Sample Input

3 3
1 2 3
3 2 1
1 1 1
Sample Output

5

最大和

Time Limit: 5 Seconds Memory Limit: 32768 KB

给定两个整数数组分别为 $A$ ，$B$ 。你可以从 $A$ ，$B$ 中分别挑选一个数，将他们的乘积作为你的得分。你可以挑选任意次，但是每个数只能被挑选一次。求你最后所能得到的分值和的最大值，你的初始分数为 0。

Input

每个文件包含一个测试数据。第一行是一个正整数 $N$，为数组 $A$ 的长度。第二行为 $N$ 个整数，分别为 $A$ 中的元素。第三行是一个正整数 $M$ ，为数组 $B$ 的长度。第四行为 $M$ 个整数，分别为 $B$ 中的元素。 $1 \le M, N \le 10^6$

Output

输出结果包含一行，为你所能得到的最大的分之和。A，B中的数及最后的结果均不超过2³⁰

Sample Input 4
3 2 6 1
3
2 6 3
Sample Output

49

第一提看上去比较悬，但仔细一想其实是个最大子段和的问题，核心算法可以参考 ZOJ 1074——我就是这么干的……应用之前需要预处理，就是扫描下整个矩阵，然后用 1 表示奇数而用 -1 表示偶数，最后算“矩阵的最大子段和”，这样做下来基本上可以通过 4–5 个测试点，弥补的方法就是对称性，考虑到奇数和偶数的平等性，用 -1 表示奇数而用 1 表示偶数再算一下。整个程序如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define size 102

int DP(int a[],int n);

int main(void) {
  int m, n;
  int i, j, k;
  int he;
  int max1, max2;

  int a[size][size];
  int b[size][size];
  int sum1[size];
  int sum2[size];

  scanf("%d%d",&m, &n);

  for(i = 1; i <= m; i++)
    for(j = 1; j <= n; j++) {
      scanf("%d",&a[i][j]);

      if (a[i][j] % 2 == 0) {
        a[i][j] = -1;
        b[i][j] = 1;
      }
      else {
        a[i][j] = 1;
        b[i][j] = -1;
      }
    }

  max1 = max2 = -200000000;

  for(i = 1; i <= m; i++) {
    memset(sum1, 0, sizeof(sum1));

    for(j = i; j <= m; j++) {
      for(k = 1 ; k <= n ; k++)
        sum1[k] += a[j][k];

      he = DP(sum1, n);

      if(he > max1)
        max1 = he;
    }
  }

  for(i = 1; i <= m; i++) {
    memset(sum2, 0, sizeof(sum2));

    for(j = i; j <= m; j++) {
      for(k = 1 ; k <= n ; k++)
        sum2[k] += b[j][k];

      he = DP(sum2, n);

      if(he > max2)
        max2 = he;
    }
  }

  if (max1 > max2)
    printf("%d\n",max1);
  else
    printf("%d\n", max2);
  return 0;
}

int DP(int a[],int n) {
  int i, f[101];
  int max = -200000000;

  for(i = 2, f[1] = a[1]; i <= n; i++) {
    if (f[i - 1] > 0)
      f[i] = f[i - 1] + a[i];
    else
      f[i] = a[i];

    if (f[i] > max)
      max = f[i];
  }

  return max;
}

第二题的思路比较清晰了，需要注意的是负数的情况，考虑四个正数 $a \le b, c \le d$ ，显然 $ac + bd \ge ad + bc$ ，就是要得到最大值，大大相乘优先。如果遇到负数，负负为正是可以考虑的，正负相乘则需要舍弃。按照这个原则进行排序、分割，在处理下去就不难了。有一个 Test Case 是 "Segmentation Fault" ，最后找到原因了，可惜没有时间了，程序如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

int main() {
  int m, n;
  vector<int> a;
  vector<int> b;

  int i, j;
  int item;
  int s, sum;
  int ai, bi;

  cin >> m;
  for (i = 0; i < m; i++) {
    cin >> item;
    a.push_back(item);
  }

  cin >> n;
  for (j = 0; j < n; j++) {
    cin >> item;
    b.push_back(item);
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  for(i = 0; i < a.size(); i++) {
    if (a[i] >= 0) {
      ai = i;
      break;
    }
  }

  for(i = 0; i < b.size(); i++) {
    if (b[i] >= 0) {
      bi = i;
      break;
    }
  }

  sum = 0;
  for(i = 0, j = 0; (i < ai) && (j < bi); i++, j++) {
    sum += a[i] * b[j];
  }

  for(i = a.size() - 1, j = b.size() - 1; (i >= ai) && (j >= bi); i--, j--) {
    sum += a[i] * b[j];
  }

  cout << sum << endl;

  return 0;
}

最后的结果还是不错的，这也让我感到惊喜，好久都没有如此开心过了，期待面试通知。

另外，现在所在的实习公司已经有了口头上的 offer，给我一个月的时间考虑，在实习结束之前给答复，待遇和淘宝应届是差不多的，而且创业阶段，发展空间还是非常大的，我在部门也受到重视，我相信继续实习一年，毕业后我会处于一个比较高的起点，这样的结果，对于我这么一个挂科达到两位数的刚毕业的本科来说，应该算很不多的了，但是我还是在犹豫。老实说我还是想去大的公司体验两年，体验下大的平台和大的气质；妈妈每次打电话都让我回北京，家近、方便。所以我还在继续投简历。

18 号下去 2:00–3:00，百度大牛徐串的技术讲座；19号下午 2:00，百度内推小型见面会； 20号晚 6:30，MSTC 主席 Pluskid 大神的小课堂，各种大牛，膜拜。

除了这些，印度宝莱坞的电影《三个傻瓜》前前后后看了 4 遍，哭笑中带来人生的思考；看了《当幸福来敲门》，我喜欢那种“He must have a nice pants”的自信；看了柴静的《面对面》——李连杰“壹基金危机”，“侠之大者，为国为民”，李连杰当之无愧；“方向对了，就不怕路远”，加油吧，Lox!