这两天复习数据结构，看到AVL树这一部分，之前这部分一直处于“纸上谈兵”的阶段，表示有些遗憾。趁着最近比较闲，把它实现一下！

还是先讲一下AVL树的基本概念吧。其实，AVL树就是二叉树，与普通二叉树不同的是，它能通过某种操作（“旋转”）使得树保持几乎平衡，这里就是指左子树和右子树的树高差的绝对值<=1。当二叉树是平衡的情况下，在树上的搜索效率就会提高。极端情况下，能从O(N)降到O(logN)。

OK，那么又有哪几种不平衡的情况呢？我们来看一下下面几种情况：

右子树的右子树太“深”

树往一边倾斜，这是一种常见的不平衡状态。比如把一个已排序的数据插入二叉树就是这种情况。遇到这种情况，如果可以把k2“提”起来就好了。很简单，我们可以把k2作为树根，k1做k2的左孩子，再把B当作k1的右子树。旋转之后可以得到：

这样，树又基本平衡了。左子树的左子树太深的情况可依此类推。这两种情况成为单旋转。

还有一种情况，右子树的左子树太“深”

这样就k2不好“提”了，因为旋转之后，B子树的树高没有改变。把树描述的更加详细一些：

=>

我们的目标是把k3以及BC放的高一些，以降低整体树高。因为k1<=k3<=k2，那可否让k3来做树根呢？k3做了树根，k1和k2是其左右孩子，AD子树可以不变，B可以作为k1右子树，C可以作为k2左子树，这样就搞定了！

同样，左子树的右子树太深的情况也是类似。这两种情况成为双旋转。

好，用代码实现这些操作！

根据单旋转的图例，两步操作就可以完成：

1. k2的左指针指向k1

2. k1的右指针指向B

代码实现就是这样：

AVLTree* singleRotateWithRight(AVLTree* pNode)
{
    if ( pNode == NULL || pNode->right == NULL )
        return NULL;
    AVLTree* rightNode = pNode->right;
    pNode->right = rightNode->left;
    rightNode->left = pNode;

    pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
    rightNode->height = max(getHeight(rightNode->left), getHeight(rightNode->right)) + 1;

    return rightNode;
}

再看双旋转的实现，很奇妙的是，一个双旋转可以用两个但旋转来代替！

=> =>

实现起来相当简单：

AVLTree* doubleRotateWithRight (AVLTree* pNode)
{
    pNode->right = singleRotateWithLeft(pNode->right);
    return singleRotateWithRight(pNode);
}

插入操作怎么实现呢？其实就是在普通二叉树的插入操作之后，加入判断是否不平衡，若不平衡，判断是哪种情况，进行相应旋转操作。

AVLTree* insert(int data, AVLTree* pNode)
{
    if ( pNode == NULL )
    {
        pNode = new AVLTree();
        pNode->data = data;
        pNode->height = 0;
        pNode->left = pNode->right = NULL;
    }
    else if ( data < pNode->data )
    {
        pNode->left = insert(data, pNode->left);
        if ( getHeight(pNode->left) - getHeight(pNode->right) == 2 )
        {
            if ( data < pNode->left->data )
            {
                pNode = singleRotateWithLeft(pNode);
            }
            else
            {
                pNode = doubleRotateWithLeft(pNode);
            }
        }
    }
    else if ( data > pNode->data )
    {
        pNode->right = insert(data, pNode->right);
        if ( getHeight(pNode->right) - getHeight(pNode->left) == 2 )
        {
            if ( data > pNode->right->data )
            {
                pNode = singleRotateWithRight(pNode);
            }
            else
            {
                pNode = doubleRotateWithRight(pNode);
            }
        }
    }

    return pNode;
}

好吧，先写这么多，性能对比以后再写。全部实现代码可以在这里看到。

题目大意：

一种字符串加密算法，即在原有字符串的任意位置插入C、O、W，C的下标 < O的下标 < W的下标，将C、O之间和O、W之间子串交换，得到新的字符串。给你一个字符串，问其是否是对字符串Begin the Escape execution at the Break of Dawn经过多次加密过后的字符串。

我的思路：

首先，原字符串中并没有COW三个字母，所以不用判断COW是属于原先的字符还是加密时加上的字符，这样简单很多。另外，对于已加密的字符串，只要找到任意一组COW，交换CO和OW之间的子串，再把COW删掉，得到的字符串就是可能的一种原字符串，再这样递归下去，直到不可能的情况或者字符串变为Begin the Escape execution at the Break of Dawn。

在搜索时，有几种减枝可以排除目前的字符串：

• 如果目前字符串的长度不等于原串长度+3×k，排除。（其实只需在开始时判断一次即可）

• 如果目前字符串中COW三个字母的数目不相等，排除。（也可只判断一次）

• 如果任意COW字符之间的子串，没有出现在原串中，排除。（这个减枝很重要，但是没想到，不应该啊）

• 字符串中，所有出现COW的地方，C应该排在第一个，W应该排在最后一个。否则，无法还原成原字符串。

• 用hash来判断目前字符串之前有没有出现过。（hash表的大小选择很关键，选的太大，可能会超时，选的太小，可能会WA）

另外，枚举COW时的搜索方式也很重要。如果每一层都会从i到len，像这样：

    for (i = 0; i < l; i ++)
    {
        if ( str[i] != 'C' )
            continue;
        for (j = i + 1; j < l; j ++)
        {
            if ( str[j] != 'O' )
                continue;
            for (k = j + 1; k < l; k ++)
            {
                if ( str[k] != 'W' )
                    continue;
                if ( CheckStr( RestoreString(str, i, j, k)) )
                    return true;
            }
        }
    }

很容易就超时了。

但是，如果先把所有COW的下标先记下来，再在每一层枚举它们的下标，像这样：

    for (i = 0; i < cNum; i ++)
    {
        for (j = 0; j < oNum; j ++)
        {
            for (k = 0; k < wNum; k ++)
            {
                if ( cIdx[i] < oIdx[j] && oIdx[j] < wIdx[k] )
                {
                    if ( CheckStr( RestoreString(str, cIdx[i], oIdx[j], wIdx[k])) )
                        return true;
                }
            }
        }
    }

就会快很多。

好了，废话不多说，直接上代码：

unsigned int elf_hash(string str)
{
    unsigned long h = 0, g, i, l;
    l = str.length();
    for (i = 0; i < l; i ++)
    {
        h = (h << 4) + str[i];
        if (g = h & 0xf0000000l)
            h ^= g >> 24;
        h &= ~g;
    }
    return h % HASH_NUM;
}

//COW的数目是否相等，以及数目是多少
//其实跟CheckStr中的判断有重复，还可以优化！
int CheckCOWNum (string str)
{
    int i, l;
    int nC, nO, nW;
    nC= nO = nW = 0;
    l = str.length();

    for (i = 0; i < l; i ++)
    {
        if ( str[i] == 'C' )
            ++ nC;
        else if ( str[i] == 'O' )
        {
            ++ nO;
        }
        else if ( str[i] == 'W' )
        {
            ++ nW;
        }
    }
    if ( nC == nO && nO == nW )
        return nC;
    else
        return -1;
}

//还原加密的字符串
//idx1 < idx2 < idx3
string RestoreString (string now, int idx1, int idx2, int idx3)
{
    string pre = "";
    int i, l;
    l = now.length();
    pre = now.substr(0, idx1);
    pre += now.substr(idx2+1, idx3-idx2-1);
    pre += now.substr(idx1+1, idx2-idx1-1);
    pre += now.substr(idx3+1, l-idx3-1);

    return pre;
}

bool CheckBetweenCOW (string str)
{
    int lastIdx;
    int i, l;
    lastIdx = -1;
    l = str.length();
    for (i = 0; i < l; i ++)
    {
        if ( str[i] == 'C' || str[i] == 'O' || str[i] == 'W' )
        {
            if ( finalStr.find(str.substr(lastIdx + 1, i - lastIdx - 1)) == string::npos )
            {
                return false;
            }
            lastIdx = i;
        }
    }
    return true;
}

bool CheckStr (string str)
{
    if ( str == finalStr )
        return true;

    int hash;
    hash = elf_hash(str);
    if ( hashVisited[hash] )
        return false;
    hashVisited[hash] = true;

    int i, j, k, l;
    int cNum, oNum, wNum, allNum;
    int cIdx[NUM], oIdx[NUM], wIdx[NUM], allIdx[NUM];
    cNum = oNum = wNum = allNum = 0;
    l = str.length();

    //记录C O W的下标
    allIdx[allNum++] = -1;
    for (i = 0; i < l; i ++)
    {
        if ( str[i] == 'C' )
        {
            cIdx[cNum++] = i;
            allIdx[allNum++] = i;
        }
        else if ( str[i] == 'O' )
        {
            oIdx[oNum++] = i;
            allIdx[allNum++] = i;
        }
        else if ( str[i] == 'W' )
        {
            wIdx[wNum++] = i;
            allIdx[allNum++] = i;
        }
    }
    if ( allIdx[allNum-1] != l - 1 )
        allIdx[allNum++] = l;

    //所有出现COW的地方，C应该排在第一个，W应该排在最后一个。否则，无法还原成原字符串
    if ( cNum )
    {
        if ( cIdx[0] > oIdx[0] || cIdx[0] > wIdx[0] )
            return false;
        if ( wIdx[wNum-1] < cIdx[cNum-1] || wIdx[wNum-1] < oIdx[oNum-1] )
            return false;
    }

    //任意COW之间的子串都应该在原串中出现过
    for (i = 0; i < allNum-1; i ++)
    {
        if ( finalStr.find(str.substr(allIdx[i]+1, allIdx[i+1]-allIdx[i]-1)) == string::npos )
            return false;
    }

    for (i = 0; i < cNum; i ++)
    {
        for (j = 0; j < oNum; j ++)
        {
            for (k = 0; k < wNum; k ++)
            {
                if ( cIdx[i] < oIdx[j] && oIdx[j] < wIdx[k] )
                {
                    if ( CheckStr( RestoreString(str, cIdx[i], oIdx[j], wIdx[k])) )
                        return true;
                }
            }
        }
    }

    //这样就会很慢。。。
    //  for (i = 0; i < l; i ++)
    //  {
    //      if ( str[i] != 'C' )
    //          continue;
    //      for (j = i + 1; j < l; j ++)
    //      {
    //          if ( str[j] != 'O' )
    //              continue;
    //          for (k = j + 1; k < l; k ++)
    //          {
    //              if ( str[k] != 'W' )
    //                  continue;
    //              if ( CheckStr( RestoreString(str, i, j, k)) )
    //                  return true;
    //          }
    //      }
    //  }

    return false;
}

void Solve ()
{
    if ( (str.length() - finalStr.length()) % 3 != 0 )
    {
        printf("0 0\n");
        return;
    }

    int nCOW = CheckCOWNum(str);
    if ( nCOW == -1 || !CheckStr(str) )
    {
        printf("0 0\n");
        return;
    }
    printf("1 %d\n", nCOW);
}

题目大意：

有N个栏杆，告诉你它们的长度以及它们各自的连接情况，求出围成的最短的封闭空间的周长。其中，1 <= N <= 100，栏杆长度Ls，1 <= Ls <= 255，每个栏杆至多与另外8跟栏杆相连。

思路：

就是在图中找最小环。因为N（即边数）最大为100，即使通过枚举每个点进行搜索，复杂度也不过为100×100，可以采用搜索。枚举每个栏杆的一端顶点，如果搜索到这根栏杆的另一端顶点，那么就意味着找到环了，更新答案。

这题思路倒很简单，但是由于输入是以边为中心的，所以实现起来稍稍有点困难。我将每个栏杆的两个顶点定义为s端和e端，如果从某栏杆a的s端出发，那么枚举与a的e端相连的栏杆b，再判断是b的哪一端连接着a，枚举b的另一端，以此类推。

还有一些减枝和优化，比如：

1. 收到上一题的启发，可以限定搜索深度，因为组成环的边数少，周长小的概率就比较大。

2. 当前的长度和大于等于目前的答案，退出。

3. 当前栏杆之前访问过，退出。

4. 只需枚举栏杆的一端即可，因为s->e和e->s的效果是一样的。

看了USACO的官方分析，貌似处理的比较复杂，先把输入转化成标准的图，再对于每一条边，先删除它，然后用Dijkstras算法求最短路。这种方案相交于我的思路，没有太多优越性，但是编码的复杂度却也高。-_–

关键代码如下：

const int N = 101;

int n;
int len[N];
vector<int> childSeg[N][2];     //[0] s end; [1] e end
short int connect[N][N];        //connect[a][b] = 0/1 means the s/e end of a connects with seg b
int curMax = 1<<20;
int visited[N];

/*
seg为负，表示当前节点为seg的s端
seg为正，表示当前节点为seg的e端
*/
void Search(int seg/*negtive s end; positive e end*/, int curLen, int destSeg, int depth)
{
    if ( seg == destSeg && curLen != 0)
    {
        if ( curLen < curMax )
            curMax = curLen;
        return;
    }
    if ( !depth )
        return;
    if ( curLen >= curMax )
        return;

    int segId = abs(seg);
    if ( visited[segId] )
        return;
    visited[segId] = 1;
    int childSegId;
    //whichEnd, segId的另一端
    int whichEnd = 0;
    if ( seg < 0 )
        whichEnd = 1;
    int i;
    for (i = 0; i < childSeg[segId][whichEnd].size(); i ++)
    {
        childSegId = childSeg[segId][whichEnd][i];
        //从childSegId的另一端继续搜索
        if ( connect[childSegId][segId] == 0 )
        {
            Search(childSegId * -1, curLen + len[segId], destSeg, depth-1);
        }
        else if ( connect[childSegId][segId] == 1 )
        {
            Search(childSegId, curLen + len[segId], destSeg, depth-1);
        }
    }
    visited[segId] = 0;
}

void Solve ()
{
    int i, j;
    for (i = 3; i <= n; i ++)
    {
        for (j = 1; j <= n; j ++)
        {
            Search(j, 0, j, i);
//          不需要枚举另一端，因为s->e和e->s的效果是一样的
//          Search(-1*j, 0, -1*j, i);
        }
    }
    printf("%d\n", curMax);
}

题目大意：

给你N(1 <= N <= 50)段长度不一的木材，另外有R(1 <= R <= 1023)条栏杆需要修复，1 <= ri <= 128。问以这些木材为原材料，能够做出最多多少块栏杆？（做出的栏杆需要是完整的，不能拼接）

思路：

这是一道背包问题，不过，这是高维背包。是把R个栏杆放入N段木材中，传统背包的DP解法在这里貌似就无能为力了，看了hint才知道，原来要用到DFSID算法，也就是限制搜索深度的DFS。是一种类似BFS的求解过程，但是却用DFS来实现的算法。简单的说，每次枚举搜索深度，进行DFS，如果未得到解，则继续增加（减少）搜索深度，直至找到解。

搜索的过程中，有一些重要的减枝：

1. 如果可以组成k块栏杆，那么最小的前k块栏杆一定是其中的一个解。因为就算存在不连续的解，我们也可以将较大的栏杆替换成较小的栏杆，最终转化为最小的k块栏杆。

2. 根据R和ri ，可以看出栏杆的长度有很多都是重复的。将木材和栏杆排序，搜索时记录下当前的栏杆是选择哪块木材。搜索到当前栏杆i时，如果发现与上一个栏杆i+1的长度相同，则我们可以从i+1块栏杆所选择的那块木材开始搜。

3. 假设前k块栏杆是题目的解，那么在这种情况下最大浪费掉的木材maxWaste就是sumBoard – sumRail[k]。在搜索过程中，如果发现某块木材的剩余量比最小的栏杆都小，就可以把他计入curWaste，如果发现curWaste > maxWaste，那么肯定无解。

4. 我们还可以将R的范围减小，如果发现sumRail[k] <= sumBoard并且sumRail[k+1] > sumBoard，那么我们可以将R减小到k。

嗯，差不多就是这些。还有一个减枝，就是如果发现栏杆长度比最大的木材还要长的话，那在输入的时候就略去它（貌似减枝效果不明显-_-）。我们从（经过优化过的）R开始搜索，假设前k个栏杆就是解，对于每个栏杆，枚举木材，基本上就是这么个思路。做完这题的最大感受就是：要善于挖掘题目中的潜在信息。根据R和ri的关系，得知栏杆有许多重复的情况，以及如何推导出如果k为解，则前k个栏杆肯定能构成解，这就是真正的分析问题的能力了！

以下是关键代码：

bool Search (int rIndex)
{
    if ( rIndex < 0 )
        return true;
    int bound = 0;
    //如果当前rail和上一个rail的长度相同，则从上一个rail选的board开始搜索
    if ( rIndex < r - 1 && rail[rIndex] == rail[rIndex+1] )
        bound = railSelect[rIndex+1];
    int i;
    bool ret = false;

    for (i = bound; i < n; i ++)
    {
        if ( board[i] >= rail[rIndex] )
        {
            board[i] -= rail[rIndex];
            railSelect[rIndex] = i;
            if ( board[i] < rail[0] )
            {
                curWaste += board[i];
                //如果当前浪费的board大于最大允许的浪费量，则不选这个board
                if ( curWaste > maxWaste )
                {
                    curWaste -= board[i];
                    board[i] += rail[rIndex];
                    railSelect[i] = -1;
                    continue;
                }
            }
            ret = Search(rIndex - 1);
            //恢复之前状态，顺序很重要！
            if ( board[i] < rail[0] )
                curWaste -= board[i];
            board[i] += rail[rIndex];
            railSelect[rIndex] = -1;
            if ( ret )
                return true;
        }
    }

    return false;
}

void Solve ()
{
    int i;
    memset(railSelect, -1, sizeof(railSelect));
    sort(rail, rail + r);
    sort(board, board + n);

    boardSum = 0;
    for (i = 0; i < n; i ++)
        boardSum += board[i];
    //找到可以优化的R
    //用一个int表示前k个rail之和
    railSum = 0;
    for (i = 0; i < r; i ++)
    {
        railSum += rail[i];
        if ( railSum > boardSum )
        {
            railSum -= rail[i];
            break;
        }
    }

    -- i;
    for (; i >= 0; i --)
    {
        curWaste = 0;
        maxWaste = boardSum - railSum;
        if ( Search(i) )
        {
            printf("%d\n", i+1);
            return;
        }
        railSum -= rail[i];
    }
    printf("0\n");
}

题目大意：有n（<=10）个整数a1, a2, …, an（<=256），问是否存在无法用a1～an的线性表达式（k1a1 + k2a2 + … + knan）组成的数，如果有，其中最大的数是多少？（这个数的上限为2,000,000,000！）

思路：本想可以用简单的DP来实现，但一看到2,000,000,000的上限，放弃了DP的想法，结果好几天都没有思路。如果这个上限可以下降的足够小，那该多好！上网查了下资料以及问了下周围同学，得到一个结论：a1~an所无法组成的最大数的上限可以为其中最大两个数的最小公倍数！这样的话，题目的上限就可以一下子缩小到256×256了！DP就变得可行了。

其实，完整的证明我也暂时不能完全理解，这里先给出只有两个数的情况。

当有两个数a1和a2，a1和a2互质，可以证明无法用他们表达的数的上限为a1×a2，即大于a1×a2的数都可以表示成k1×a1+k2×a2。

即，对于任意正整数x，有：

a1*a2 + x = k1*a1 + k2*a2

=>  (a2 - k1)*a1 + x = k2*a1

因为k1任意，所以a2-k1也任意，将(a2-k1)a1对a2取模，因为a1和a2互质，所以余数必然在0～a2-1的范围内，设为x’。另外，因为x也是任意的，所以我们将x表示成ka2-x’。这样，等式左半边就可以被a2整数，等式得证。

再一次意识到，数学对于计算机科学来说是多么的重要！

好！上限确定下来之后，剩下的就是简单的DP了，以下是关键代码：

void Solve ()
{
     int i, j, bound, gcdNum;

     gcdNum = box[0];
     for (i = 1; i < n; i ++)
          gcdNum = gcd(gcdNum, box[i]);
     if ( gcdNum != 1 )
     {
          printf("0\n");
          return;
     }

     canMake[0] = 1;
     sort(box, box+n);
     bound = box[n-1] * box[n-1];
     for (i = 0; i < bound; i ++)
     {
          if ( ! canMake[i] )
               continue;
          for (j = 0; j < n; j ++)
          {
               if ( i + box[j] < bound )
                    canMake[i+box[j]] = 1;
          }
     }

     for (i = bound-1; i >= 0; i --)
     {
          if ( !canMake[i] )
          {
               printf("%d\n", i);
               return;
          }
     }
     printf("0\n");
}

题目大意：有N(<=20)首歌，打算放在M(<=20)张CD中，每张CD可存储T(<=20)分钟的音乐，给定每首歌的时长，问如何将歌曲按照日期（也就是输入）的顺序，存在这M张CD中，并且每首歌不可以分开存在多张CD上，使得存储的歌曲的数目最多。

来看给的样例：

4 5 2
4 3 4 2

答案是3，可以直接看出，存放的方案是将第1首4分钟的歌存入第1张CD，然后将第2首3分钟和第4首2分钟的歌存入第2张CD。

思路：

一看到题，就冲动的想到搜索。后来理智还是打败了冲动，20层的搜索还是有些接受不了。于是试着看这题能不能DP。DP的关键就是能否准确的记录子问题，我们来想一想子问题应该如何表示。很自然的，子问题可以表示为：前n首歌考虑放入前m张CD，所能放入的最大歌曲数。然后我们就可以将问题逐渐扩展，直至N、M的规模。但是，子问题如何扩展呢？那就是将[n][m]的情况下，考虑第n+1首歌。如果不放这首歌，就转化为[n+1][m]；如果放这首歌，可以分两种情况：将第n+1首歌放在第m张CD上，将第n+1首歌放在第m+1张CD上。那怎么判断第n+1首歌可以放入第m张CD上呢？因此，还需要一个维度，那就是在[n][m]的规模下，第m张CD还剩余的时长。最后，子问题就可以表示成如下的形式：

maxSong[songNum][diskNum][remain]

• songNum表示已考虑到的前songNum首歌

• diskNum表示已考虑到的前diskNum张CD

• remain表示在第diskNum张CD上剩余的时长

maxSong[songNum][diskNum][remain]（假设值为n）可以扩展为以下状态：

1. maxSong[songNum+1][diskNum][remain]( = n ) 不放第songNum+1首歌

2. maxSong[songNum+1][diskNum][remain-songTime[songNum+1]]( = n+1 ) 将第songNum+1首歌放入第diskNum张CD

3. maxSong[songNum+1][diskNum+1][T-songTime[songNum+1]]( = n + 1 ) 将第songNum+1首歌放入第diskNum+1张CD

这样，按n、m和t的规模从小到大一次进行扩展，最终maxSong中最大的值即为答案。

关键代码如下：

void Expand(int songNum, int diskNum, int remain)
{
     if ( maxSong[songNum][diskNum][remain] == -1 )
           return;
     if ( songNum == N && diskNum == M )
           return;
     int curMax = maxSong[songNum][diskNum][remain];
     if ( remain >= songTime[songNum+1] )
     {
          maxSong[songNum+1][diskNum][remain-songTime[songNum+1]] =
                max( maxSong[songNum+1][diskNum][remain-songTime[songNum+1]], curMax+1);
     }
     if ( T >= songTime[songNum+1] )
     {
           maxSong[songNum+1][diskNum+1][T-songTime[songNum+1]] =
                max( maxSong[songNum+1][diskNum+1][T-songTime[songNum+1]], curMax+1);
     }
     maxSong[songNum+1][diskNum][remain] = max( maxSong[songNum+1][diskNum][remain], curMax);
}

void Solve ()
{
     int i, j, k, ans;
     ans = -1;
     memset(maxSong, -1, sizeof(maxSong));
     maxSong[0][0][0] = 0;
     for (i = 0; i <= M; i ++)
     {
           for (j = 0; j <= N; j ++)
           {
                for (k = 0; k <= T; k ++)
                {
                     Expand(j, i, k);
                }
           }
     }

     for (i = 0; i <= M; i ++)
     {
           for (j = 0; j <= N; j ++)
           {
                for (k = 0; k <= T; k ++)
                {
                     if ( maxSong[j][i][k] > ans )
                     {
                           ans = maxSong[j][i][k];
                     }
                }
           }
     }
     printf("%d\n", ans);
}

题目大意：一句话！已知二叉树的前序和中序，求二叉树的后序，树的节点数不超过26。

二叉树的前序的节点处理顺序为：根节点、左子树、右子树； 中序为：左子树、根节点、右子树； 后序为：左子树、右子树、根节点。

因为前序的第一个元素是根节点，则可以找到根节点在中序中的位置idx，这样idx左边的序列为左子树、idx右边的就为右子树。根据左右子树的个数，就可以知道其在前序中的相应位置，然后就可以递归的处理左右子树了并得到它们的后序排列，最终的答案就为：左子树的后序 + 右子树的后序 + 根节点。当子问题足够小的时候，即前序、中序长度为1或0时，后序就是前序或者中序。

题目中例子的解题顺序如下图：

关键代码如下：

string getPostOrder(string preOrder, string inOrder)
{
     assert(preOrder.length() == inOrder.length());
     if ( preOrder.length() == 1 || preOrder.length() == 0 )
          return preOrder;
     int rootIdx;
     rootIdx = inOrder.find_first_of(preOrder[0]);
     assert(rootIdx != string::npos);
     string leftTree, rightTree;
     leftTree = getPostOrder(preOrder.substr(1, rootIdx), inOrder.substr(0, rootIdx));
     rightTree = getPostOrder(preOrder.substr(rootIdx+1, preOrder.length()-rootIdx-1), inOrder.substr(rootIdx+1, preOrder.length()-rootIdx-1));
     return leftTree + rightTree + preOrder[0];
}

题目大意：

由N（3 < N < 200）个点构成的多边形，问1) 该多边形是否为简单多边形，2) 从某一点(x, y)可以看到哪些边？看到边的任意部分就算可以看到该边，但如果从(x, y)只能看到边的某一顶点不算能看到。

             几乎没怎么做过计算几何，鸭梨好大啊！第一问比较简单，只要线段之间没有相互相交（不含端点）就可以了。第二问没直接想到思路，参考了N种方法，终于找到一种好理解且实现简单的解法。看到这题，最直观的想法就是从观察点发出射线，找到与其相交且截距最近的线段就可以啦。但是，射线应该有哪些方向呢？360度绕一圈，效率低且精度无法掌握。较好的方法是将观察点(x, y)与每个顶点(xi, yi)连接，再将该射线按顺时针和逆时针转动很小的角度，通过这些射线找到的截距最短的线段集合就是最终的答案（没找到理论基础，只是直觉上感觉是对的）。最终答案需要排序，不过这题的排序规则没什么意思，其实就是在顺序输出的基础上，有两个例外：如果第n-1条线段可以被看到，交换第n-1条线段的两个顶点；如果第n-1和n-2条线段都可以被看到，交换两条线段。

这道题用到了大量的计算几何模板，不用不知道，一用吓一跳。里面有一些逻辑错误和精度问题。

比如以下两个算法：

/* 判断点p是否在线段l上
条件：(p在线段l所在的直线上)&& (点p在以线段l为对角线的矩形内) */
bool online(LINESEG l,POINT p)
{
     return ((multiply(l.e, p, l.s)==0)
          && ( ( (p.x-l.s.x) * (p.x-l.e.x) <=0 ) && ( (p.y-l.s.y)*(p.y-l.e.y) <=0 ) ) );
}




// 如果线段l1和l2相交，返回true且交点由(inter)返回，否则返回false
bool intersection(LINESEG l1,LINESEG l2,POINT &inter)
{
     LINE ll1,ll2;
     ll1=makeline(l1.s,l1.e);
     ll2=makeline(l2.s,l2.e);
     if(lineintersect(ll1,ll2,inter)) return online(l1,inter);    //!!!!!
     else return false;
}

第一个算法的精度有问题，应该把精度调低一些，把0换成EP(1e-10)：

bool online(LINESEG l,POINT p)
{
     return (abs(multiply(l.e, p, l.s) <= EP )          //!!!!!
          && ( ( (p.x-l.s.x) * (p.x-l.e.x) <= EP ) && ( (p.y-l.s.y)*(p.y-l.e.y) <= EP ) ) );
}

第二个算法逻辑有问题，求两个线段是否相交，它的思想是先求两线段所在的直线是否相交，再看交点是否在一条直线上，但如果是下图中的情况，那答案就是不对的。

所以我改成了：

// 如果线段l1和l2相交，返回true且交点由(inter)返回，否则返回false
bool intersection(LINESEG l1,LINESEG l2,POINT &inter)
{
     LINE ll1,ll2;
     ll1=makeline(l1.s,l1.e);
     ll2=makeline(l2.s,l2.e);
     if(lineintersect(ll1,ll2,inter)) return online(l1,inter) && online(l2, inter);
     else return false;
}

经过修改，这题终于AC了！关键代码如下：

int nearestLine (LINESEG ray, LINESEG* lines, int num)
{
     double curMinDis, tmp;
     int minIdx, i;
     POINT interPoint;

     curMinDis = INF;
     minIdx = -1;
     //every fence
     for (i = 0; i < num; i ++)
     {
          if ( intersection(lines[i], ray, interPoint) && (tmp=dist(ray.s, interPoint)) <= curMinDis)
          {
               curMinDis = tmp;
               minIdx =  i;
          }
     }
     return minIdx;
}

void FindFence ()
{
     int k = 200;          //射线延长倍数
     double delta = 1e-10;     //旋转角度
     LINESEG ray, line1;
     POINT interPoint;
     int i, j;
     double curMinDis, tmp;
     int minIdx;

     memset(visible, 0, sizeof(visible));
     ray.s = ob;
     //every point
     for (i = 0; i < n; i ++)
     {
          ray.e = point[i];

          ray.e.x = k * (ray.e.x - ray.s.x) + ray.s.x;
          ray.e.y = k * (ray.e.y - ray.s.y) + ray.s.y;

          line1.s = ray.s;
          line1.e = rotate(ray.s, delta, ray.e);
          minIdx = nearestLine(line1, fence, n);
          if ( minIdx != -1 )
          {
               visible[minIdx] = 1;
          }

          line1.e = rotate(ray.s, -1 * delta, ray.e);
          minIdx = nearestLine(line1, fence, n);
          if ( minIdx != -1 )
          {
               visible[minIdx] = 1;
          }
     }
}

void Output ()
{
     int i, cnt = 0;

     for (i = 0; i < n; i ++)
          if ( visible[i] )
               ++ cnt;

     printf("%dn", cnt);
     if ( visible[n-1] )
     {
          swap(fence[n-1].s, fence[n-1].e);
          if ( visible[n-2] )
               swap(fence[n-2], fence[n-1]);
     }
     for (i = 0; i < n; i ++)
     {
          if ( visible[i] )
          {
               printf("%.0lf %.0lf %.0lf %.0lfn", fence[i].s.x, fence[i].s.y, fence[i].e.x, fence[i].e.y);
          }
     }
}

这段时间闲来无事，正在学习Scala语言。Scala语言，简单的说，就是一种运行在JVM上的具有面向对象和函数式编程特性的语言，具体介绍可以看到官方网站看看。至于当初为什么决定学Scala，还是受到了《多核危机：Scala vs. Erlang》这篇文章的“诱惑”。

为什么现在有关Scala这样的重视并行计算的语言会受到越来越多的关注？我觉得原因有两点：一是性能，二是成本。

性能，很好理解的。企业随着规模越来越大，用户对于系统服务的请求频率也会越来越高。对于企业来说，系统服务的请求响应肯定是越短越好，系统的并发程度肯定是越高越好。但是对于已有的硬件条件、系统框架，性能达到了瓶颈，这时必然要考虑改变已有的一个或者多个因素，以达到性能的再次提升。改变系统的框架、所实现的语言，这是一种解决方案。就像当年淘宝的系统是用perl完成的，结果当系统和用户规模提高时，系统的性能就无法满足要求了，于是淘宝决定把原有系统推翻，改用Java的框架实现，问题得到了解决。现在，已经有一些企业，将原有的系统改为用Scala实现了。

成本，有两个方面吧：硬件成本和开发维护成本。企业花大价钱买了多核的高性能服务器，结果发现使用已有的系统，服务器的资源使用率和性能都不高。或者，可以开发出性能更高的系统，但是开发难度巨大、潜在bug无数、可能迟迟不能交付。这两种关于成本的窘境，可能都是现在许多企业正在面临的，那么大家肯定都会寻找既能充分利用已有计算机硬件资源，开发难度又不大的语言或者某种解决方案。

关于Scala在并行需求下的效率，我目前只是在概念上有所体会，今后要实际用实验测试一下看看，大家可以看看QCon上《并行需求下的Scala和Erlang比较》这篇演讲。

另外，Scala语言的一个特点是函数式编程，可以让我们用更严谨、更不易出错的方式表达问题，解决问题，使我们从平时的命令式语言的思维中跳跃出来，用另一个角度思考问题。说到这，我们还需要思考一下，目前大学里面上的计算机课程，是不是有些落后于目前业界的需求了？当外面的世界早已都是分布式计算、并行计算、多核编程的时候，大学里面的许多课程都还是重点考察学生对于某种语言的语法掌握情况，而不是用某种语言解决现实世界的问题的能力。:(

今后的硬件（服务器、PC、手机、各种嵌入式设备）都是多核的，能够高校利用多核硬件资源、进行高性能并行计算的语言，用到的地方还是会很多的，我看好Scala语言！

前段时间，经历了种种的不顺和纠结，有实习方面的，有“学术”方面的，也有个人感情方面的。还好，现在这些事情基本上都算过去了，整理一下思路，为最近这几个月作个初步计划。

编程

编程还是我们程序员的基本功的，每天至少要进行1～2小时的编程。最近在看Scala语言，多编几个例子实践一下，然后做个小工程。有时间再做做USACO，看毕业前能不能把里面的训练题都做完。最后，抓住一切可以锻炼自己编程能力的机会！

读书

不能不读书啊，不管是专业书还是杂书。

先看这些专业书籍吧：

• 《Unix环境高级编程》

• 《Programming in Scala》

• 《编程之美》

还想找几本关于软件构架方面的书，求推荐。

杂书方面，先把白岩松的《幸福了吗》还有《智慧书》，然后再找其他的看

博客

要坚持写博客，要有自己对于软件行业的看法（哪怕是错的），要多总结、多分析，不应只是复制已有的文字以及对于知识的初步概括，要写的有点深度才可以。

锻炼

每周进行2～3次健身，2～3次慢跑，周末有时间找人一起爬爬山。

英语

一直没有突破，但却从未放弃，还是从VOA入手吧，多听多写多读。还有就是口语，先把最近买的《疯狂口语900句》读完再说吧。

工作

最近找个实习是不大可能了，就安心准备8、9月份开始的招聘吧。得把专业相关的知识系统地复习一下了，数据结构、算法、设计模式、操作系统、数据库、网络，这些至少得过一遍。

个人感情

种种迹象表明，我还是个比较痴情的人的，另外本着宁滥勿缺宁缺勿滥的原则，所以如果没有十分合适的话，这件事还是先放一放吧。不该联系的人就不要再联系了，多花点时间在家人和朋友的身上。

“学术”

哦，对了，还有所谓的“学术”。虽然我对中国的学术已经表示有些失望了，虽然每次谈到中国的学术，我总有退学的冲动。但我还是尽力吧，坚持每天都看论文，多与导师讨论，把毕设搞好。（虽然我现在还是不知道我的毕设应该从何入手……）

好了，思路整理的差不多了，下面就是做好时间规划，一项一项专心的去做吧！