D. Wang's Log

周末去看小家伙，小家伙顺利完成了答辩事宜，在学校比较清闲了。趁着这段清闲时间，继续我们在天津的腐败之路:)周六去了在远东百货的橘子工房，三杯鸡套餐很好吃，宝宝点了，鸡做得真的很好吃，我点了日式咖喱猪排套餐，一般般=,= 猪排一般，咖喱也很一般，比较失败。还要了一杯芒果冰沙，一大杯，我们是先吃饭，导致不断的融化往外流水，这个冰沙还行，一端上来还以为上面有好多芒果，后来发现不是。。。宝宝吃完大呼撑了，貌似套餐里面米饭不少，小家伙只顾好吃的，忘了自己的食量了 之后去了在新天地的米乐星KTV，好久没K了，我们都想一展歌喉 不错，收获不少，发现几首适合我们自己唱的歌。唱完发现策略有点不对，应该每个人唱几首换另外一个人去点，我们唱的时候一个人来个10多首，唱完直接上来累意了。最后感觉不错，唱的很开心:)

期间参加了百度之星08的比赛，第一天的题目总体感觉不难，第一题直接遍历，第二题稍微有点变化的DP，第三题我直接用暴力，估计会超时，可是又没什么好思路，也不是RMQ问题，需要一个动态维护区间高度的数据结构，想对各个区间高度做排序，然后二分，但是不实际，空间要求太大，最后想想算了，暴力吧，获取能过几个Test case:) 第四题无头绪，讨论说可用离散化，我没做。第二天的题目，至少从编码量上来说，要大一些。第一题也很直接，我稍微做了一个预处理，以加快纠正速度。第二题没别的思路，就是死算面积，然后带入化简后的公式，没怎么想，就先放着。第三题想想应该是网络流，自己做过的是最简单的网络流，对于涉及费用问题的网络流还没做过- -b 直接放下了。第四题，想想，自己所能想到的也没什么好方法，K为1时，最坏情况，这么大的区间，估计要超时。最后也没写。希望发我一件T恤吧:-)现在自己是专找这些免费T恤，这样就不用自己费心跑到商场去买了。

return;

还是在POJ做题吧~

这道比较简单，没测试过枚举的方法，直观的想是用中国剩余定理（具体流程一开始也给忘了，常年不用- -）。 不过数据得小心，我一开始考虑挺全面的，想到由剩余定理获得的结果可能会小于0，但是没想到会大于21252的情况，WA了好几次，加上这个条件就AC了。

POJ 1006

// Source code for POJ 1006  by billjeff, sep/11/2007

#include <iostream>
using namespace std ;


...

豆瓣链接：http://www.douban.com/subject/1073031/

这本书过去读过一次，这次重新看了一下，并且把里面的算法和题目都给实现了一遍，收获还是不少的。书中的内容涉及了图论当中众多的基础知识和算法，介绍了图的基本概念、图的存储、遍历算法、以及各种应用算法，包括各种网络流算法，生成树算法，独立集算法，欧拉路算法，Hamilton回路近似算法等。这次阅读，让我对这些概念和算法有了更好的理解和掌握，同时能够提高自己的编码速度。

 

...

这是基于匈牙利算法的一个实现，相比基于网络流的方法要简单一些。

// 匈牙利算法求二分图的最大匹配
// billjeff
// Aug/29/2007

#include <iostream>
using namespace std ;

#define FORI(n) for ( int i = 1 ; i <= n ; ++i )
#define FORJ(n) for ( int j = 1 ; j <= n ; ++j )

#define debug_over
#define file_io_no

class Graph {
...

同样基于网络流算法进行处理的。源代码如下

// Maximum Binary-Mapping
// billjeff
// Aug/30/2007

#include <iostream>
#include <limits>
using namespace std ;

#define debug_over

class BinGraph {
private:
  const static int MAXNODE = 100 ;
  bool _g[MAXNODE][MAXNODE] ; // Original graph info

源代码如下：

/*
 * Graph Algorithm: 有流量上下界的最大流和最小流
 * by billjeff
 * 2007/Aug/12
 */


#include <iostream>
#include <limits>
#include <cstdlib>
using namespace std ;

#define file_io
#define debug

class Graph {
    private:
     &...

#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
using namespace std ;

#define debug_off
#define file_io


const int MAX = 1000 ;
const int N = 100 ;


int lset[MAX][N] ;
bool graph[N][N] ;
int nodeNum ;
int resultNum = 0, numSet[MAX] ;


void read...

写了一个HashTable类，用开放地址法和邻接链表法处理冲突，表的大小为大于用户指定大小的最小质数。表本身会自动调整大小。详细代码如下：

/*
* Hash Table Class
* Created by billjeff
* 2007-07-12
* The hash function is: rotating hash
* unsigned int rotating( char *key, size_t len, unsigned int prime)
{
unsigned int hash;

Recently, I am wrting C++ codes to implement common algorithms and data structure. This is AVL tree's C++ implementation. ( Referenced from Yan Weimin's book called ``Data Structure'' published by Tsinghua University Press ). The core operations are left and right rotations. Here is my code:

/* AVL Tree
* Created by billjeff
* 2007-07-10
*/...

小家伙是周四过来的，刚好我参加完2007 Google开发者大会，领完几年T恤就匆匆赶去接宝宝了。顺便说下参加这次大会吧，遇见了几位Googler，Kaifu Lee，Shiva，这两位做了开幕演讲和Key notes，下午我去听了opensource分论坛，演讲的嘉宾是Jon Trowbridge，Mike Schroepfer，Guido van Rossum和苏哲，苏哲的演讲内容偏技术一点，其它的都讲的挺泛泛的，Jon演讲的时候很有激情，甚至有人问他为何so excited，呵呵。会上Guido最受欢迎，众多fans找他合影~

To be continued. 

...