SinRain::If not you,Who!

在写程序时，调试程序也是一个重要的环节。怎样才能够更有效地调试程序，发现并修正错误呢？

1、调试中的输入输出

为了调试程序，我们可能需要反复执行程序，也就需要反复输入相同或不相同的测试数据。如果每次调试运行时都是以手工的方式输入测试数据，相信很多人都会觉得不胜其烦。其实我们可以用一些辅助的手段来简化这个过程。

方法一：使用剪贴板

可以将输入数据预先写好（用记事本、开发环境的编辑器或随便什么能够录入的东西），再将输入数据复制到剪贴板上（也就是说我们通常所说的复制操作）。在调试运行时，就可以直接将输入数据粘贴上去，不需要手工输入，这对于反复调试同一组测试数据尤其方便。

方法二：使用重定向

使用剪贴板对于多组测试数据或者比较长的测试数据就会显得不那么好用了。而使用输入输出的重定向则会更方便。

输入输出重定向是在终端窗口下的一种命令行功能，在命令行上可以用“<”表示输入重定向，在“<”后跟随输入文件名，则程序将从指定的输入文件中获取输入数据，而不再从键盘读入数据。也可以用“>”表示输出重定向。在“>”后跟输出文件名，则程序产生的标准输出将写入指定的输出文件中，而不是显示在屏幕上。

我们可以预先将输入数据存到文本文件中（如果有多组测试数据，可以存成多个文件），用重定向指定准备使用的输入数据。

例如，程序名为myprog，输入数据已经存到文件test.txt中，则在命令行下可以这样执行：

C:>myprog < test.txt

则程序会直接从test.txt中读取输入。如果想把输出结果也存到文件中（这在输出结果比较多的时候尤其有用，因为直接输出到屏幕上可能会来不及看到输出，或看不全所有的输出），例如，可以这样执行：

C:>myprog > test.out

这样我们就可以在执行后，用一个文本编辑器打开输出文件，慢慢阅读和分析输出结果。

如果把输入和输出的重定向结合起来，也可以这样执行：

C:>myprog < test.txt > test.out

2、输出调试信息

在调试时，很多同学往往首先想到的是使用开发环境所提供的调试功能：设置断点、单步执行、查看和修改变量，甚至改变程序的流程。不可否认，使用开发环境所提供的调试功能的确很方便，但当你过分依赖于这些集成工具时，你可能忽略了很多更有效的手段：仔细地分析、充分的信息。

当我们发现程序没有按照自己预期得那样工作时，不要急于跟踪甚至修改程序，而是应该首先仔细对程序的逻辑、语句、表达式进行检查和分析，尽可能使程序在表达上更简洁、更干净。如果实在难以发现问题所在，也不必急于借助于集成工具去跟踪程序的运行。早期的程序员在调试程序时经常会在程序中加入输出调试信息的语句或过程，用以观察程序的运行过程，分析程序的运行逻辑，这种调试手段即使在今天也仍然是非常有效的。

输出的调试信息要尽量容易阅读，格式清楚，在必要的时候，可以借助工具程序或自己编写的程序对输出信息进行处理，以帮助分析问题。

3、发现线索

调试的目的就是要分析错误发生的原因，寻找线索。盲目的调试只会浪费时间。

调试中的技巧很多，这里提出几条基本原则：

首先是要使错误可重现，要设法保证能够使错误按照自己的意愿重复出现。对于不知道什么时候会冒出来的错误，分析起来会困难得多！

缩小导致错误的输入，设法构造出最小的又能保证错误出现的输入，这样可以减少变化的可能性，使分析范围更集中。经常可以采用二分选择的方法来选择输入，就是舍掉一半输入，看看错误是否会出现，如果不出现，则选择另一半输入，如此反复，并不断缩小导致错误的输入。

4、构造测试数据和测试程序

在题目中所给出的测试样例只是一小组测试数据，这虽然通常是我们用来测试程序的第一组数据，但却是远远不够的。我们应该根据题意自行构造更多的测试数据，尤其是一些边界状态的测试数据（数据极大、数据极小、数据量极多、数据量极少、预期出现极端结果等情况）。

边界测试数据可以用于检查程序中是否存在边界错误，设计有缺陷的程序，在处理边界测试数据时往往容易暴露出错误。但如果没有发生明显的运行错误，就需要对结果的正确性进行验证。

有些测试数据可以通过手工计算求出结果，再与程序的计算结果相对比，而也有些问题，可以通过构造测试程序来进行验证。

测试程序通常是用确定可靠的算法编写的解题程序，但不须考虑时间和空间的消耗，用测试程序对测试数据进行求解，用计算结果与待测试程序的计算结果进行对比。

以题1041--纯素数问题为例，我们可以用最简单的穷举法进行求解，也许这样的解法是不被接受的，因为效率太低，但这个解法却可以用作我们的测试程序，甚至——有同学索性在本地先用这个程序把结果算出来，再写一个程序直接输出结果——居然也被接受了！

ACM/ICPC竞赛其实就是算法设计和编码的竞赛，熟悉各种常用算法和算法设计策略并能灵活运用是非常必要的。

这里对几种在竞赛中经常用到的算法设计策略做一简单的介绍。

1、穷举法

穷举法是最基本的算法设计策略，其思想是列举出问题所有的可能解，逐一进行判别，找出满足条件的解。

穷举法的运用关键在于解决两个问题：

如何列举所有的可能解；

如何判别可能解是否满足条件；

在运用穷举法时，容易出现的问题是可能解过多，导致算法效率很低，这就需要对列举可能解的方法进行优化。

以题1041--纯素数问题为例，从1000到9999都可以看作是可能解，可以通过对所有这些可能解逐一进行判别，找出其中的纯素数，但只要稍作分析，就会发现其实可以大幅度地降低可能解的范围。根据题意易知，个位只可能是3、5、7，再根据题意可知，可以在3、5、7的基础上，先找出所有的二位纯素数，再在二位纯素数基础上找出三位纯素数，最后在三位纯素数的基础上找出所有的四位纯素数。

2、分治法

分治法也是应用非常广泛的一种算法设计策略，其思想是将问题分解为若干子问题，从而可以递归地求解各子问题，再综合出问题的解。

分治法的运用关键在于解决三个问题：

确定分治规则，即如何分解问题。

确定终结条件，即问题分解到什么状态时可以直接求解。

确定归纳方法，即如何由子问题的解得到原问题的解。这一步并不总是需要的，因为对某些问题来说，并不需要对子问题的解进行复杂的归纳。

我们熟知的如汉诺塔问题、折半查找算法、快速排序算法等都是分治法运用的典型案例。

以题1045--Square Coins为例，先对题意进行分析，可设一个函数f(m, n)等于用面值不超过n²的货币构成总值为m的方案数，则容易推导出：

f(m, n) = f(m-0*n*n, n-1)+f(m-1*n*n, n-1)+f(m-2*n*n, n-1)+...+f(m-k*n*n, n-1)
这里的k是币值为n²的货币最多可以用多少枚，即k=m/(n*n)。

也很容易分析出，f(m, 1) = f(1, n) = 1

对于这样的题目，一旦分析出了递推公式，程序就非常好写了。所以在动手开始写程序之前，分析工作做得越彻底，逻辑描述越准确、简洁，写起程序来就会越容易。

3、动态规划法

动态规划法多用来计算最优问题，动态规划法与分治法的基本思想是一致的，但处理的手法不同。动态规划法在运用时，要先对问题的分治规律进行分析，找出终结子问题，以及子问题向父问题归纳的规则，而算法则直接从终结子问题开始求解，逐层向上归纳，直到归纳出原问题的解。

动态规划法多用于在分治过程中，子问题可能重复出现的情况，在这种情况下，如果按照常规的分治法，自上向下分治求解，则重复出现的子问题就会被重复地求解，从而增大了冗余计算量，降低了求解效率。而采用动态规划法，自底向上求解，每个子问题只计算一次，就可以避免这种重复的求解了。

动态规划法还有另外一种实现形式，即备忘录法。备忘录的基本思想是设立一个称为备忘录的容器，记录已经求得解的子问题及其解。仍然采用与分治法相同的自上向下分治求解的策略，只是对每一个分解出的子问题，先在备忘录中查找该子问题，如果备忘录中已经存在该子问题，则不须再求解，可以从备忘录中直接得到解，否则，对子问题递归求解，且每求得一个子问题的解，都将子问题及解存入备忘录中。

例如，在题1045--Square Coins中，可以采用分治法求解，也可以采用动态规划法求解，即从f(m, 1)和f(1, n)出发，逐层向上计算，直到求得f(m, n)。

在竞赛中，动态规划和备忘录的思想还可以有另一种用法。有些题目中的可能问题数是有限的，而在一次运行中可能需要计算多个测试用例，可以采用备忘录的方法，预先将所有的问题的解记录下来，然后输入一个测试用例，就查备忘录，直接找到答案输出。这在各问题之间存在父子关系的情况下，会更有效。例如，在题1045--Square Coins中，题目中已经指出了最大的目标币值不超过300，也就是说问题数只有300个，而且各问题的计算中存在重叠的子问题，可以采用动态规划法，将所有问题的解先全部计算出来，再依次输入测试用例数据，并直接输出答案。

4、回溯法

回溯法是基于问题状态树搜索的求解法，其可适用范围很广。从某种角度上说，可以把回溯法看作是优化了的穷举法。回溯法的基本思想是逐步构造问题的可能解，一边构造，一边用约束条件进行判别，一旦发现已经不可能构造出满足条件的解了，则退回上一步构造过程，重新进行构造。这个退回的过程，就称之为“回溯”。

回溯法在运用时，要解决的关键问题在于：

如何描述局部解。

如何扩展局部解和回溯局部解。

如何判别局部解。

回溯法的经典案例也很多，例如全排列问题、N后问题等。

5、贪心法

贪心法也是求解最优问题的常用算法策略，利用贪心法策略所设计的算法，通常效率较高，算法简单。贪心法的基本思想是对问题做出目前看来最好的选择，即贪心选择，并使问题转化为规模更小的子问题。如此迭代，直到子问题可以直接求解。

基于贪心法的经典算法例如：哈夫曼算法、最小生成树算法、最短路径算法等。

但是，贪心法的运用是有条件的，必须能够证明贪心选择能够导出最优解，且转化出的子问题与原问题是同性质的问题，才能使用贪心法求解。

一个比较经典的贪心法求解的问题就是找硬币问题：有1、2、5、10、20、50、100七种面值的硬币，要支付指定的金额，问怎么支付所用的硬币个数最少。这是一个非常日常化的问题，凭直觉我们会想到，尽可能先用大面值的硬币，这就是“贪心选择”，而在这个问题上，这个贪心选择也是正确的。

6、限界剪枝法

限界剪枝法是求解较复杂最优问题的一种算法策略，与回溯法类似的是，限界剪枝法也是在问题状态空间树上进行搜索，但回溯法是搜索一般解，而限界剪枝法则是搜索最优解。限界剪枝法的基本思想是通过找出权值函数的上下界函数，以下界函数来指导搜索的方向，以上界函数来帮助剪除一些不可能含有最优解的分枝。

关于算法和算法策略的讨论是一个非常庞大的话题，几乎每个问题点都能扩展出一大堆可讨论的内容和案例。我实在不知道该怎样用简短的几篇文字就能够把这个话题说透，这里只能蜻蜓点水地对竞赛中经常用到的几种策略做一极为简略的介绍。

也许我们可以在以后的文章中，针对具体的题目进行算法和策略的分析，效果可能会更好。

<algorithm>无疑是STL中最大的一个头文件，它是由一大堆模板函数组成的。

下面列举出<algorithm>中的模板函数：

adjacent_find / binary_search / copy / copy_backward / count / count_if / equal / equal_range / fill / fill_n / find / find_end / find_first_of / find_if / for_each / generate / generate_n / includes / inplace_merge / iter_swap / lexicographical_compare / lower_bound / make_heap / max / max_element / merge / min / min_element / mismatch / next_permutation / nth_element / partial_sort / partial_sort_copy / partition / pop_heap / prev_permutation / push_heap / random_shuffle / remove / remove_copy / remove_copy_if / remove_if / replace / replace_copy / replace_copy_if / replace_if / reverse / reverse_copy / rotate / rotate_copy / search / search_n / set_difference / set_intersection / set_symmetric_difference / set_union / sort / sort_heap / stable_partition / stable_sort / swap / swap_ranges / transform / unique / unique_copy / upper_bound

如果详细叙述每一个模板函数的使用，足够写一本书的了。还是来看几个简单的示例程序吧。

示例程序之一，for_each遍历容器：

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

int Visit(int v) // 遍历算子函数
{
    cout << v << " ";
    return 1;
}

class MultInt // 定义遍历算子类
{
private:
    int factor;
public:
    MultInt(int f) : factor(f)
    {
    }
    void operator()(int &elem) const
    {
        elem *= factor;
    }
};

main()
{
    vector<int> L;
    for (int i=0; i<10; i++) L.push_back(i);
    for_each(L.begin(), L.end(), Visit);
    cout << endl;
    for_each(L.begin(), L.end(), MultInt(2));
    for_each(L.begin(), L.end(), Visit);
    cout << endl;
    return 1;
}

程序的输出结果为：

0 1 2 3 4 5 6 7 8 9
0 2 4 6 8 10 12 14 16 18

示例程序之二，min_element/max_element，找出容器中的最小/最大值：

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

main()
{
    vector<int> L;
    for (int i=0; i<10; i++) L.push_back(i);
    vector<int>::iterator min_it = min_element(L.begin(), L.end());
    vector<int>::iterator max_it = max_element(L.begin(), L.end());
    cout << "Min is " << *min_it << endl;
    cout << "Max is " << *max_it << endl;
    return 1;
}

程序的输出结果为：

Min is 0
Max is 9

示例程序之三，sort对容器进行排序：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Print(vector<int> &L)
{
    for (vector<int>::iterator it=L.begin(); it!=L.end(); it++)
        cout << *it << " ";
    cout << endl;
}
main()
{
    vector<int> L;
    for (int i=0; i<5; i++) L.push_back(i);
    for (int i=9; i>=5; i--) L.push_back(i);
    Print(L);
    sort(L.begin(), L.end());
    Print(L);
    sort(L.begin(), L.end(), greater<int>()); // 按降序排序
    Print(L);
    return 1;
}

程序的输出结果为：

0 1 2 3 4 9 8 7 6 5
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

示例程序之四，copy在容器间复制元素：

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
main( )
{
    // 先初始化两个向量v1和v2
    vector <int> v1, v2;
    for (int i=0; i<=5; i++) v1.push_back(10*i);
    for (int i=0; i<=10; i++) v2.push_back(3*i);

    cout << "v1 = ( " ;
    for (vector <int>::iterator it=v1.begin(); it!=v1.end(); it++)
        cout << *it << " ";
    cout << ")" << endl;

    cout << "v2 = ( " ;
    for (vector <int>::iterator it=v2.begin(); it!=v2.end(); it++)
        cout << *it << " ";
    cout << ")" << endl;

    // 将v1的前三个元素复制到v2的中间
    copy(v1.begin(), v1.begin()+3, v2.begin()+4);

    cout << "v2 with v1 insert = ( " ;
    for (vector <int>::iterator it=v2.begin(); it!=v2.end(); it++)
        cout << *it << " ";
    cout << ")" << endl;
    
    // 在v2内部进行复制，注意参数2表示结束位置，结束位置不参与复制
    copy(v2.begin()+4, v2.begin()+7, v2.begin()+2);

    cout << "v2 with shifted insert = ( " ;
    for (vector <int>::iterator it=v2.begin(); it!=v2.end(); it++)
        cout << *it << " ";
    cout << ")" << endl;
    return 1;
}

程序的输出结果为：

v1 = ( 0 10 20 30 40 50 )
v2 = ( 0 3 6 9 12 15 18 21 24 27 30 )
v2 with v1 insert = ( 0 3 6 9 0 10 20 21 24 27 30 )
v2 with shifted insert = ( 0 3 0 10 20 10 20 21 24 27 30 )

在STL的头文件<map>中定义了模板类map和multimap，用有序二叉树来存贮类型为pair<const Key, T>的元素对序列。序列中的元素以const Key部分作为标识，map中所有元素的Key值都必须是唯一的，multimap则允许有重复的Key值。

可以将map看作是由Key标识元素的元素集合，这类容器也被称为“关联容器”，可以通过一个Key值来快速确定一个元素，因此非常适合于需要按照Key值查找元素的容器。

map模板类需要四个模板参数，第一个是键值类型，第二个是元素类型，第三个是比较算子，第四个是分配器类型。其中键值类型和元素类型是必要的。

map的基本操作有：

1、定义map对象，例如：

map<string, int> m;

2、向map中插入元素对，有多种方法，例如：

m[key] = value;
[key]操作是map很有特色的操作，如果在map中存在键值为key的元素对，则返回该元素对的值域部分，否则将会创建一个键值为key的元素对，值域为默认值。所以可以用该操作向map中插入元素对或修改已经存在的元素对的值域部分。

m.insert( make_pair(key, value) );
也可以直接调用insert方法插入元素对，insert操作会返回一个pair，当map中没有与key相匹配的键值时，其first是指向插入元素对的迭代器，其second为true；若map中已经存在与key相等的键值时，其first是指向该元素对的迭代器，second为false。

3、查找元素对，例如：

int i = m[key];
要注意的是，当与该键值相匹配的元素对不存在时，会创建键值为key的元素对。

map<string, int>::iterator it = m.find(key);
如果map中存在与key相匹配的键值时，find操作将返回指向该元素对的迭代器，否则，返回的迭代器等于map的end()（参见vector中提到的begin和end操作）。

4、删除元素对，例如：

m.erase(key);
删除与指定key键值相匹配的元素对，并返回被删除的元素的个数。

m.erase(it);
删除由迭代器it所指定的元素对，并返回指向下一个元素对的迭代器。

看一段简单的示例代码：

程序执行的输出结果为：

MyTestMap[2] = No.2
MyTestMap[2] = No.2 After modification
Map contents :
No.1
No.2 After modification
No.3
No.4
No.5

再看一段简单的示例代码：

#include <iostream>
#include <map>
using namespace std;
main()
{
    map<string, int> m;
    m["one"] = 1;
    m["two"] = 2;
    // 几种不同的insert调用方法
    m.insert(make_pair("three", 3));
    m.insert(map<string, int>::value_type("four", 4));
    m.insert(pair<string, int>("five", 5));

    string key;
    while (cin>>key)
    {
        map<string, int>::iterator it = m.find(key);
        if (it==m.end())
        {
            cout << "No such key!" << endl;
        }
        else
        {
            cout << key << " is " << it->second << endl;
            cout << "Erased " << m.erase(key) << endl;
        }
    }
    return 1;
}

stack(栈)和queue(队列)也是在程序设计中经常会用到的数据容器，STL为我们提供了方便的stack(栈)的queue(队列)的实现。

准确地说，STL中的stack和queue不同于vector、list等容器，而是对这些容器的重新包装。这里我们不去深入讨论STL的stack和queue的实现细节，而是来了解一些他们的基本使用。

1、stack

stack模板类的定义在<stack>头文件中。

stack模板类需要两个模板参数，一个是元素类型，一个容器类型，但只有元素类型是必要的，在不指定容器类型时，默认的容器类型为deque。

定义stack对象的示例代码如下：

stack<int> s1;
stack<string> s2;

stack的基本操作有：

入栈，如例：s.push(x);

出栈，如例：s.pop();注意，出栈操作只是删除栈顶元素，并不返回该元素。

访问栈顶，如例：s.top()

判断栈空，如例：s.empty()，当栈空时，返回true。

访问栈中的元素个数，如例：s.size()

下面是用string和stack写的解题1064--Parencoding的程序。

#include <iostream>
#include <string>
#include <stack>
using namespace std;
main()
{
    int n;
    cin >> n;
    for (int i=0; i<n; i++)
    {
        int m;
        cin >> m;
        string str;
        int leftpa = 0;
        for (int j=0; j<m; j++)  // 读入P编码，构造括号字符串
        {
            int p;
            cin >> p;
            for (int k=0; k<p-leftpa; k++) str += '(';
            str += ')';
            leftpa = p;
        }
        stack<int> s;
        for (string::iterator it=str.begin(); it!=str.end(); it++)
        {   // 构造M编码
            if (*it=='(')
                s.push(1);
            else
            {
                int p = s.top(); s.pop();
                cout << p << " ";
                if (!s.empty()) s.top() += p;
            }
        }
        cout << endl;
    }
    return 1;
}

2、queue

queue模板类的定义在<queue>头文件中。

与stack模板类很相似，queue模板类也需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque类型。

定义queue对象的示例代码如下：

queue<int> q1;
queue<double> q2;

queue的基本操作有：

入队，如例：q.push(x); 将x接到队列的末端。

出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。

访问队首元素，如例：q.front()，即最早被压入队列的元素。

访问队尾元素，如例：q.back()，即最后被压入队列的元素。

判断队列空，如例：q.empty()，当队列空时，返回true。

访问队列中的元素个数，如例：q.size()

3、priority_queue

在<queue>头文件中，还定义了另一个非常有用的模板类priority_queue(优先队列）。优先队列与队列的差别在于优先队列不是按照入队的顺序出队，而是按照队列中元素的优先权顺序出队（默认为大者优先，也可以通过指定算子来指定自己的优先顺序）。

priority_queue模板类有三个模板参数，第一个是元素类型，第二个容器类型，第三个是比较算子。其中后两个都可以省略，默认容器为vector，默认算子为less，即小的往前排，大的往后排（出队时序列尾的元素出队）。

定义priority_queue对象的示例代码如下：

priority_queue<int> q1;
priority_queue< pair<int, int> > q2;  // 注意在两个尖括号之间一定要留空格。
priority_queue<int, vector<int>, greater<int> > q3; // 定义小的先出队

priority_queue的基本操作与queue相同。

初学者在使用priority_queue时，最困难的可能就是如何定义比较算子了。

如果是基本数据类型，或已定义了比较运算符的类，可以直接用STL的less算子和greater算子——默认为使用less算子，即小的往前排，大的先出队。

如果要定义自己的比较算子，方法有多种，这里介绍其中的一种：重载比较运算符。优先队列试图将两个元素x和y代入比较运算符(对less算子，调用 x<y，对greater算子，调用x>y)，若结果为真，则x排在y前面，y将先于x出队，反之，则将y排在x前面，x将先出队。

看下面这个简单的示例：

#include <iostream>
#include <queue>
using namespace std;
class T
{
public:
    int x, y, z;
    T(int a, int b, int c):x(a), y(b), z(c)
    {
    }
};
bool operator < (const T &t1, const T &t2)
{
    return t1.z < t2.z;  // 按照z的顺序来决定t1和t2的顺序
}
main()
{
    priority_queue<T> q;
    q.push(T(4,4,3));
    q.push(T(2,2,5));
    q.push(T(1,5,4));
    q.push(T(3,3,6));

    while (!q.empty())
    {
        T t = q.top(); q.pop();
        cout << t.x << " " << t.y << " " << t.z << endl;
    }
    return 1;
}

输出结果为(注意是按照z的顺序从大到小出队的)：

3 3 6
2 2 5
1 5 4
4 4 3

再看一个按照z的顺序从小到大出队的例子：

#include <iostream>
#include <queue>
using namespace std;
class T
{
    public:
    int x, y, z;
    T(int a, int b, int c):x(a), y(b), z(c)
    {
    }
};
bool operator > (const T &t1, const T &t2)
{
    return t1.z > t2.z;
}
main()
{
    priority_queue<T, vector<T>, greater<T> > q;
    q.push(T(4,4,3));
    q.push(T(2,2,5));
    q.push(T(1,5,4));
    q.push(T(3,3,6));

    while (!q.empty())
    {
        T t = q.top(); q.pop();
        cout << t.x << " " << t.y << " " << t.z << endl;
    }
    return 1;
}

输出结果为：

4 4 3
1 5 4
2 2 5
3 3 6

如果我们把第一个例子中的比较运算符重载为：

bool operator < (const T &t1, const T &t2)
{
    return t1.z > t2.z;  // 按照z的顺序来决定t1和t2的顺序
}

则第一个例子的程序会得到和第二个例子的程序相同的输出结果。

再回顾一下用优先队列实现的题1067--Ugly Numbers的代码：

#include <iostream>
#include <queue>
using namespace std;
typedef pair<unsigned long int, int> node_type;
main( int argc, char *argv[] )
{
    unsigned long int result[1500];
    priority_queue< node_type, vector<node_type>, greater<node_type> > Q;
    Q.push( make_pair(1, 3) );
    for (int i=0; i<1500; i++)
    {
        node_type node = Q.top();
        Q.pop();
        switch(node.second)
        {
        case 3: Q.push( make_pair(node.first*2, 3) );
        case 2: Q.push( make_pair(node.first*3, 2) );
        case 1: Q.push( make_pair(node.first*5, 1) );
        }
        result[i] = node.first;
    }
    int n;
    cin >> n;
    while (n>0)
    {
        cout << result[n-1] << endl;
        cin >> n;
    }
    return 1;
}

字符串是程序中经常要表达和处理的数据，我们通常是采用字符数组或字符指针来表示字符串。STL为我们提供了另一种使用起来更为便捷的字符串的表达方式：string。string类的定义在头文件<string>中。

string类其实可以看作是一个字符的vector，vector上的各种操作都可以适用于string，另外，string类对象还支持字符串的拼合、转换等操作。

下面先来看一个简单的例子：

#include <iostream>
#include <string>
using namespace std;
main()
{
    string s = "Hello! ", name;
    cin >> name;
    s += name;
    s += '!';
    cout << s << endl;
    return 1;
}

再以题1064--Parencoding为例，看一段用string作为容器，实现由P代码还原括号字符串的示例代码片段：

int m;
cin >> m; // P编码的长度
string str; // 用来存放还原出来的括号字符串
int leftpa = 0; // 记录已出现的左括号的总数
for (int j=0; j<m; j++)
{
    int p;
    cin >> p;
    for (int k=0; k<p-leftpa; k++) str += '(';
    str += ')';
    leftpa = p;
}