当前位置:首页 >> 理学 >> ACM竞赛辅导之STL

ACM竞赛辅导之STL


第 01 篇 ACM/ICPC 竞赛之基础篇 一、ACM/ICPC 竞赛的特点 ACM/ICPC(国际大学生程序设计竞赛)是以算法设计为主的程序设计竞赛,并不涉及具体 的应用技术。

ACM/ICPC 竞赛以组队形式参赛,每个参赛队由三名队员组成,共同使用一台计算机解题。 通常每场比赛的试题为 6 至 10 题,根据各队的完成题数和罚时进行排名。题目提交通过称 为完成,从比赛开始到提交成功所用的时间为题目的基础罚时,另外,一道题目每提交失败 一次,将增加 20 分钟罚时。也就是说,参赛队要尽可能用最快的速度、最少的失败次数, 解决最多的题目。 二、输入和输出处理 试题一般采用标准输入和输出方式读取输入和产生输出, 在题目中会详细描述输入和输出的 格式和值域范围,所写的程序一定要严格遵守题目指定的输入输出格式。 在比赛试题的输入和输出处理上,针对一些常见的情形,有一些常用的方法。 1、多测试用例的输入和输出 有些试题在一次输入中只包含一个测试用例,也就是说,程序每运行一次,只算一道题。也 有些试题在一次输入中包含多个测试用例,也就是说,程序每运行一次,要计算多道题。

对多用例输入, 通常会先输入要计算的用例的个数, 然后依次输入每个测试用例的输入数据, 但程序并不需要等到所有的测试用例都计算完后再输出所有测试用例的计算结果, 而是可以 读入一个测试用例,输出一个结果,再读入一个测试用例,再输出一个结果。因此对多用例 输入的试题,可以用这样的输入模式: 以 C++为例: int n; cin >> n; for (int i=0; i<n; i++) { 读入测试用例数据 计算

输出计算结果 } 2、单测试用例输入的结束判断 对单用例输入,最主要的问题是如何知道输入什么时候结束。 有些试题会指定某种特殊的输入值作为输入的结束标志, 这种情况比较容易处理, 只须在读 入后,判断一下读入的内容是否为约定结束值即可。 有些试题并不指定特殊的输入值,而是以 EOF(文件结束标志)作为结束标志。如果从文 件流读入,当读到文件尾时,输入返回 EOF。如果从键盘读入时,在 Windows 的终端中, 是以 Ctrl+Z 表示 EOF。对于这种情况,可以用这样的输入模式: 以 C++为例: int m, n; // 假设要连续输入一组整数对 while (cin>>m>>n) { 处理整数对(m, n) } 以 C 语言为例: int m, n; while (scanf("%d%d", &m, &n)==2) { 处理整数对(m, n) } 三、数据结构的设计 很多试题中已经给出了数据量的上限, 因此可以很方便地以数组的方式定义数据结构。 但也 要注意到有些题目中没有明确指出数据上限时,切不可盲目定义数组大小。

例如在题 1070(多项式求和)中,并未说明输入多项式的项数,对这种情况就不宜用数组

方式来表示多项式了——除非你的运气足够好, 所开辟的数组大小能够经受所有的测试用例 的考验。 除了使用一般的数组或链表结构外,对使用 C++的选手来说,STL 也是一大利器,充分运 用可以有效提高编程的效率和正确性。 四、测试用例的考虑 在试题中通常会给出测试用例的样例, 这通常会被我们用来测试自己的程序, 而且很多选手 往往在正确计算出测试用例样例时,会认为自己的程序是正确的。

其实测试用例的样例只是测试用例的个例, 实际用于测试的测试用例往往会涵盖各种极限情 况和边界情况,而且有时测试用例的数量还会比较大,甚至会重复测试同一个测试用例。因 此我们的程序能够通过样例测试, 未必能够通过所有的测试用例的测试, 一方面要全面考虑 所有可能的极限情况和边界情况,一方面程序要有足够的效率。 第 02 篇 ACM/ICPC 竞赛之 STL 简介 一、关于 STL STL(Standard Template Library,标准模板库)是 C++语言标准中的重要组成部分。STL 以模 板类和模板函数的形式为程序员提供了各种数据结构和算法的精巧实现, 程序员如果能够充 分地利用 STL,可以在代码空间、执行时间和编码效率上获得极大的好处。

STL 大致可以分为三大类:算法(algorithm)、容器(container)、迭代器(iterator)。 STL 容器是一些模板类, 提供了多种组织数据的常用方法, 例如 vector(向量, 类似于数组)、 list(列表,类似于链表)、deque(双向队列)、set(集合)、map(映象)、stack(栈)、queue(队列)、 priority_queue(优先队列)等,通过模板的参数我们可以指定容器中的元素类型。 STL 算法是一些模板函数,提供了相当多的有用算法和操作,从简单如 for_each(遍历)到 复杂如 stable_sort(稳定排序) 。 STL 迭代器是对 C 中的指针的一般化,用来将算法和容器联系起来。几乎所有的 STL 算法 都是通过迭代器来存取元素序列进行工作的,而 STL 中的每一个容器也都定义了其本身所 专有的迭代器,用以存取容器中的元素。有趣的是,普通的指针也可以像迭代器一样工作。 熟悉了 STL 后,你会发现,很多功能只需要用短短的几行就可以实现了。通过 STL,我们 可以构造出优雅而且高效的代码,甚至比你自己手工实现的代码效果还要好。 STL 的另外一个特点是, 它是以源码方式免费提供的, 程序员不仅可以自由地使用这些代码, 也可以学习其源码,甚至按照自己的需要去修改它。 下面是用 STL 写的题 1067--Ugly Numbers 的代码:

#include <iostream>#include <queue>using namespace std;typedef pair<unsigned long, int> node _type;main(){ unsigned long result[1500]; priority_queue< node_type, vector<node_type>, greate r<node_type> > Q; Q.push( make_pair(1, 2) ); for (int i=0; i<1500; i++) { node_type node = Q.to p(); Q.pop(); switch(node.second) { case 2: Q.push( make_pair(node.first*2, 2) ); case 3: Q.push( make_pair(node.first*3, 3) ); case 5: Q.push( make_pair(node.first*5, 5) ); } result[i] = node.first; } int n; cin >> n; while (n>0) { cout << result[n-1] << endl; cin >> n; } return 1;} 在 ACM 竞赛中, 熟练掌握和运用 STL 对快速编写实现代码会有极大的帮助。 二、使用 STL 在 C++标准中,STL 被组织为以下的一组头文件(注意,是没有.h 后缀的!: ) algorithm / deque / functional / iterator / list / map memory / numeric / queue / set / stack / utility / vector 当我们需要使用 STL 的某个功能时,需要嵌入相应的头文件。但要注意的是,在 C++标准 中,STL 是被定义在 std 命名空间中的。如下例所示: #include <stack> main() { std::stack<int> s; s.push(0); ... return 1; } 如果希望在程序中直接引用 STL,也可以在嵌入头文件后,用 using namespace 语句将 std 命名空间导入。如下例所示: #include <stack> using namespace std; main() {

stack<int> s; s.push(0); ... return 1; } STL 是 C++语言机制运用的一个典范,通过学习 STL 可以更深刻地理解 C++语言的思想和 方法。 在本系列的文章中不打算对 STL 做深入的剖析, 而只是想介绍一些 STL 的基本应用。 有兴趣的同学,建议可以在有了一些 STL 的使用经验后,认真阅读一下《C++ STL》这本 书(电力出版社有该书的中文版) 。 第 03 篇 ACM/ICPC 竞赛之 STL--pair STL 的<utility>头文件中描述了一个看上去非常简单的模板类 pair,用来表示一个二元组或 元素对,并提供了按照字典序对元素对进行大小比较的比较运算符模板函数。 例如,想要定义一个对象表示一个平面坐标点,则可以: pair<double, double> p1; cin >> p1.first >> p1.second;

pair 模板类需要两个参数:首元素的数据类型和尾元素的数据类型。pair 模板类对象有两个 成员:first 和 second,分别表示首元素和尾元素。 在<utility>中已经定义了 pair 上的六个比较运算符:<、>、<=、>=、==、!=,其规则是先比 较 first,first 相等时再比较 second,这符合大多数应用的逻辑。 当然,也可以通过重载这几个运算符来重新指定自己的比较逻辑。 除了直接定义一个 pair 对象外,如果需要即时生成一个 pair 对象,也可以调用在<utility>中 定义的一个模板函数:make_pair。make_pair 需要两个参数, 分别为元素对的首元素和尾元素。 在题 1067--Ugly Numbers 中, 就可以用 pair 来表示推演树上的结点, first 表示结点的值, 用 用 second 表示结点是由父结点乘以哪一个因子得到的。 #include <iostream> #include <queue> using namespace std;

typedef pair<unsigned long, int> node_type; main() { unsigned long result[1500]; priority_queue< node_type, vector<node_type>, greater<node_type> > Q; Q.push( make_pair(1, 2) ); for (int i=0; i<1500; i++) { node_type node = Q.top(); Q.pop(); switch(node.second) { case 2: Q.push( make_pair(node.first*2, 2) ); case 3: Q.push( make_pair(node.first*3, 3) ); case 5: Q.push( make_pair(node.first*5, 5) ); } result[i] = node.first; } int n; cin >> n; while (n>0) { cout << result[n-1] << endl; cin >> n; } return 1; } <utility>看上去是很简单的一个头文件,但是<utility>的设计中却浓缩反映了 STL 设计的基 本思想。有意深入了解和研究 STL 的同学,仔细阅读和体会这个简单的头文件, 不失为一种入门的途径。 第 04 篇 ACM/ICPC 竞赛之 STL--vector 在 STL 的<vector>头文件中定义了 vector(向量容器模板类) ,vector 容器以连续数组的方式 存储元素序列,可以将 vector 看作是以顺序结构实现的线性表。 当我们在程序中需要使用动态数组时,vector 将会是理想的选择,vector 可以在使用过程中 动态地增长存储空间。 vector 模板类需要两个模板参数,第一个参数是存储元素的数据类型,第二个参数是存储分 配器的类型,其中第二个参数是可选的,如果不给出第二个参数, 将使用默认的分配器。 下面给出几个常用的定义 vector 向量对象的方法示例: vector<int> s; 定义一个空的 vector 对象,存储的是 int 类型的元素。 vector<int> s(n);

定义一个含有 n 个 int 元素的 vector 对象。 vector<int> s(first, last); 定义一个 vector 对象,并从由迭代器 first 和 last 定义的序列[first, last)中复制初值。 vector 的基本操作有: s[i] 直接以下标方式访问容器中的元素。 s.front() 返回首元素。 s.back() 返回尾元素。 s.push_back(x) 向表尾插入元素 x。 s.size() 返回表长。 s.empty() 当表空时,返回真,否则返回假。 s.pop_back() 删除表尾元素。 s.begin() 返回指向首元素的随机存取迭代器。 s.end() 返回指向尾元素的下一个位置的随机存取迭代器。 s.insert(it, x) 向迭代器 it 指向的元素前插入新元素 val。 s.insert(it, n, x) 向迭代器 it 指向的元素前插入 n 个 x。 s.insert(it, first, last) 将由迭代器 first 和 last 所指定的序列[first, last)插入到迭代器 it 指向的元素前面。 s.erase(it)

删除由迭代器 it 所指向的元素。 s.erase(first, last) 删除由迭代器 first 和 last 所指定的序列[first, last)。 s.reserve(n) 预分配缓冲空间,使存储空间至少可容纳 n 个元素。 s.resize(n) 改变序列的长度,超出的元素将会被删除,如果序列需要扩展(原空间小于 n) ,元素默认 值将填满扩展出的空间。 s.resize(n, val) 改变序列的长度,超出的元素将会被删除,如果序列需要扩展(原空间小于 n) ,将用 val 填满扩展出的空间。 s.clear() 删除容器中的所有的元素。 s.swap(v) 将 s 与另一个 vector 对象 v 进行交换。 s.assign(first, last) 将序列替换成由迭代器 first 和 last 所指定的序列[first, last)。[first, last)不能是原序列中的一 部分。 要注意的是, resize 操作和 clear 操作都是对表的有效元素进行的操作, 但并不一定会改变缓 冲空间的大小。 另外,vector 还有其他一些操作如反转、取反等,不再一下列举。 vector 上还定义了序列之间的比较操作运算符(>, <, >=, <=, ==, !=),可以按照字典序比较两 个序列。 还是来看一些示例代码。输入个数不定的一组整数,再将这组整数按倒序输出,如下所示: #include <iostream> #include <vector> using namespace std; main() { vector<int> L; int x; while (cin>>x) L.push_back(x);

for (int i=L.size()-1; i>=0; i--) cout << L[i] << " "; cout << endl; return 1; } 第 04 篇 ACM/ICPC 竞赛之 STL--vector 在 STL 的<vector>头文件中定义了 vector(向量容器模板类) ,vector 容器以连续数组的方式 存储元素序列,可以将 vector 看作是以顺序结构实现的线性表。 当我们在程序中需要使用动态数组时,vector 将会是理想的选择,vector 可以在使用过程中 动态地增长存储空间。 vector 模板类需要两个模板参数,第一个参数是存储元素的数据类型,第二个参数是存储分 配器的类型,其中第二个参数是可选的,如果不给出第二个参数, 将使用默认的分配器。 下面给出几个常用的定义 vector 向量对象的方法示例: vector<int> s; 定义一个空的 vector 对象,存储的是 int 类型的元素。 vector<int> s(n); 定义一个含有 n 个 int 元素的 vector 对象。 vector<int> s(first, last); 定义一个 vector 对象,并从由迭代器 first 和 last 定义的序列[first, last)中复制初值。 vector 的基本操作有: s[i] 直接以下标方式访问容器中的元素。 s.front() 返回首元素。 s.back() 返回尾元素。 s.push_back(x) 向表尾插入元素 x。 s.size() 返回表长。 s.empty()

当表空时,返回真,否则返回假。 s.pop_back() 删除表尾元素。 s.begin() 返回指向首元素的随机存取迭代器。 s.end() 返回指向尾元素的下一个位置的随机存取迭代器。 s.insert(it, x) 向迭代器 it 指向的元素前插入新元素 val。 s.insert(it, n, x) 向迭代器 it 指向的元素前插入 n 个 x。 s.insert(it, first, last) 将由迭代器 first 和 last 所指定的序列[first, last)插入到迭代器 it 指向的元素前面。 s.erase(it) 删除由迭代器 it 所指向的元素。 s.erase(first, last) 删除由迭代器 first 和 last 所指定的序列[first, last)。 s.reserve(n) 预分配缓冲空间,使存储空间至少可容纳 n 个元素。 s.resize(n) 改变序列的长度,超出的元素将会被删除,如果序列需要扩展(原空间小于 n) ,元素默认 值将填满扩展出的空间。 s.resize(n, val) 改变序列的长度,超出的元素将会被删除,如果序列需要扩展(原空间小于 n) ,将用 val 填满扩展出的空间。 s.clear() 删除容器中的所有的元素。 s.swap(v) 将 s 与另一个 vector 对象 v 进行交换。 s.assign(first, last)

将序列替换成由迭代器 first 和 last 所指定的序列[first, last)。[first, last)不能是原序列中的一 部分。 要注意的是, resize 操作和 clear 操作都是对表的有效元素进行的操作, 但并不一定会改变缓 冲空间的大小。 另外,vector 还有其他一些操作如反转、取反等,不再一下列举。 vector 上还定义了序列之间的比较操作运算符(>, <, >=, <=, ==, !=),可以按照字典序比较两 个序列。 还是来看一些示例代码。输入个数不定的一组整数,再将这组整数按倒序输出,如下所示: #include <iostream> #include <vector> using namespace std; main() { vector<int> L; int x; while (cin>>x) L.push_back(x); for (int i=L.size()-1; i>=0; i--) cout << L[i] << " "; cout << endl; return 1; } 第 05 篇 ACM/ICPC 竞赛之 STL--iterator 简介 iterator(迭代器)是用于访问容器中元素的指示器,从这个意义上说,iterator(迭代器)相当于 数据结构中所说的“遍历指针”,也可以把 iterator(迭代器)看作是一种泛化的指针。 STL 中关于 iterator(迭代器)的实现是相当复杂的, 这里我们暂时不去详细讨论关于 iterator(迭 代器)的实现和使用,而只对 iterator(迭代器)做一点简单的介绍。 简单地说,STL 中有以下几类 iterator(迭代器): 输入 iterator(迭代器),在容器的连续区间内向前移动,可以读取容器内任意值; 输出 iterator(迭代器),把值写进它所指向的容器中; 前向 iterator(迭代器),读取队列中的值,并可以向前移动到下一位置(++p,p++); 双向 iterator(迭代器),读取队列中的值,并可以向前向后遍历容器; 随机访问 iterator(迭代器), 可以直接以下标方式对容器进行访问,vector 的 iterator(迭代器) 就是这种 iterator(迭代器); 流 iterator(迭代器),可以直接输出、输入流中的值; 每种 STL 容器都有自己的 iterator(迭代器)子类,下面先来看一段简单的示例代码:

#include <iostream> #include <vector> using namespace std; main() { vector<int> s; for (int i=0; i<10; i++) s.push_back(i); for (vector<int>::iterator it=s.begin(); it!=s.end(); it++) cout << *it << " "; cout << endl; return 1; } vector 的 begin()和 end()方法都会返回一个 vector::iterator 对象,分别指向 vector 的首元素位 置和尾元素的下一个位置(我们可以称之为结束标志位置) 。 对一个 iterator(迭代器)对象的使用与一个指针变量的使用极为相似,或者可以这样说,指针 就是一个非常标准的 iterator(迭代器)。 再来看一段稍微特别一点的代码: #include <iostream> #include <vector> using namespace std; main() { vector<int> s; s.push_back(1); s.push_back(2); s.push_back(3); copy(s.begin(), s.end(), ostream_iterator<int>(cout, " ")); cout <<endl; return 1; } 这 段 代 码 中 的 copy 就 是 STL 中 定 义 的 一 个 模 板 函 数 , copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));的意思是将由 s.begin()至 s.end()(不含 s.end())所指定的序列复制到标准输出流 cout 中,用" "作为每个元素的间隔。也就是说,这 句话的作用其实就是将表中的所有内容依次输出。 iterator(迭代器)是 STL 容器和算法之间的“胶合剂”,几乎所有的 STL 算法都是通过容器的 iterator(迭代器)来访问容器内容的。只有通过有效地运用 iterator(迭代器),才能够有效地运 用 STL 强大的算法功能。

第 06 篇 ACM/ICPC 竞赛之 STL--string 字符串是程序中经常要表达和处理的数据, 我们通常是采用字符数组或字符指针来表示字符 串。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; } 看下面这个简单的示例: #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? { } }; 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 的顺序从大到小出队的): 336 225 154 443 再看一个按照 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? { } }; 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; } 输出结果为: 443 154 225 336 如果我们把第一个例子中的比较运算符重载为: 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; } 第 08 篇 ACM/ICPC 竞赛之 STL--map 在 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 所指定的元素对,并返回指向下一个元素对的迭代器。 看一段简单的示例代码: #include<map>#include<iostream> using namespace std; typedef map<int, string, less<int> > M_ TYPE;typedef M_TYPE::iterator M_IT;typedef M_TYPE::const_iterator M_CIT; int main(){ M_ TYPE MyTestMap; MyTestMap[3] = "No.3"; MyTestMap[5] = "No.5"; MyTestMap[1] = "No.1"; MyTestMap[2] = "No.2"; MyTestMap[4] = "No.4"; M_IT it_stop = MyTestMap.find(2); cout << " MyTestMap[2] = " << it_stop->second << endl; it_stop->second = "No.2 After modification"; cou t << "MyTestMap[2] = " << it_stop->second << endl; cout << "Map contents : " << endl; for(M_C IT it = MyTestMap.begin(); it != MyTestMap.end(); it++) { cout << it->second << endl; } return 0 ;} 程序执行的输出结果为: 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; } 第 09 篇 ACM/ICPC 竞赛之 STL--algorithm <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 / inpla ce_merge / iter_swap / lexicographical_compare / lower_bound / make_heap / max / max_element / merge / min / min_element / mismatch / next_permutation / nth_element / partial_sort / partial_s ort_copy / partition / pop_heap / prev_permutation / push_heap / random_shuffle / remove / remov e_copy / remove_copy_if / remove_if / replace / replace_copy / replace_copy_if / replace_if / reve rse / 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_ra nges / 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; } 程序的输出结果为: 0123456789 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; } 程序的输出结果为: 0123498765 0123456789 9876543210 示例程序之四,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 ) 第 10 篇 ACM/ICPC 竞赛之算法策略 ACM/ICPC 竞赛其实就是算法设计和编码的竞赛, 熟悉各种常用算法和算法设计策略并能灵 活运用是非常必要的。 这里对几种在竞赛中经常用到的算法设计策略做一简单的介绍。 1、穷举法 穷举法是最基本的算法设计策略,其思想是列举出问题所有的可能解,逐一进行判别,找出 满足条件的解。 穷举法的运用关键在于解决两个问题: 如何列举所有的可能解; 如何判别可能解是否满足条件; 在运用穷举法时,容易出现的问题是可能解过多,导致算法效率很低,这就需要对列举可能

解的方法进行优化。 以题 1041--纯素数问题为例,从 1000 到 9999 都可以看作是可能解,可以通过对所有这些可 能解逐一进行判别,找出其中的纯素数,但只要稍作分析,就会发现其实可以大幅度地降低 可能解的范围。根据题意易知,个位只可能是 3、5、7,再根据题意可知,可以在 3、5、7 的基础上,先找出所有的二位纯素数,再在二位纯素数基础上找出三位纯素数,最后在三位 纯素数的基础上找出所有的四位纯素数。 2、分治法 分治法也是应用非常广泛的一种算法设计策略, 其思想是将问题分解为若干子问题, 从而可 以递归地求解各子问题,再综合出问题的解。 分治法的运用关键在于解决三个问题: 确定分治规则,即如何分解问题。 确定终结条件,即问题分解到什么状态时可以直接求解。 确定归纳方法,即如何由子问题的解得到原问题的解。这一步并不总是需要的,因为对某些 问题来说,并不需要对子问题的解进行复杂的归纳。 我们熟知的如汉诺塔问题、折半查找算法、快速排序算法等都是分治法运用的典型案例。 以题 1045--Square Coins 为例,先对题意进行分析,可设一个函数 f(m, n)等于用面值不超过 n2 的货币构成总值为 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 是币值为 n2 的货币最多可以用多少枚,即 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、限界剪枝法 限界剪枝法是求解较复杂最优问题的一种算法策略, 与回溯法类似的是, 限界剪枝法也是在 问题状态空间树上进行搜索,但回溯法是搜索一般解,而限界剪枝法则是搜索最优解。限界 剪枝法的基本思想是通过找出权值函数的上下界函数, 以下界函数来指导搜索的方向, 以上 界函数来帮助剪除一些不可能含有最优解的分枝。 关于算法和算法策略的讨论是一个非常庞大的话题, 几乎每个问题点都能扩展出一大堆可讨 论的内容和案例。 我实在不知道该怎样用简短的几篇文字就能够把这个话题说透, 这里只能 蜻蜓点水地对竞赛中经常用到的几种策略做一极为简略的介绍。 也许我们可以在以后的文章中,针对具体的题目进行算法和策略的分析,效果可能会更好。 第 11 篇 ACM/ICPC 竞赛之调试 在写程序时,调试程序也是一个重要的环节。怎样才能够更有效地调试程序,发现并修正错 误呢? 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竞赛之新人向导

清华大学ACM集训队培训资料... 10页 免费 ACM竞赛辅导之STL 27页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

STL_in_ACM

STL in ACM 3页 1财富值 ACM中STL的应用 29页 2财富值 ACM竞赛与STL 31页 2财富值 ACM竞赛辅导之STL 27页 免费 06_ACM数据结构与STL 28页 2财富值 STL...

STL-ACM常用函数

(next_permutation(myVec.begin(), myVec.end())); ACM/ICPC 竞赛之 STL 简介 一、关于 STL STL(Standard Template Library,标准模板库)是 C++语言标准中的...

STL in ACM

ACM竞赛辅导之STL 27页 免费 ACM竞赛与STL 31页 2财富值 STL in ACM 24页 2财富值 STL-ACM常用函数 22页 8财富值 06_ACM数据结构与STL 28页 2财富值如...

acm常用STL函数库

} Set 常用函数:跟其他容器的函数差不多,好像都通 用 c++ stl 容器 set ...ACM竞赛辅导之STL 27页 免费 06_ACM数据结构与STL 28页 5下载券 stl常用...

ACM竞赛模板

ACM竞赛模板_计算机软件及应用_IT/计算机_专业资料。一、最短路 ①DJK #define...p2,p4)) return 1; return 0;//两线段不相交返回 false } 五、STL 函数 ...

ACM中STL的应用

STL | 全排列函数next_permutation STL 中专门用于排列的函数(可以处理存在重复...2012 ACM STL编程及应用 113页 免费 ACM竞赛辅导之STL 27页 免费 STL-ACM常用...

2011年ACM大赛真题试题

2011年ACM大赛真题试题_电脑基础知识_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档2011年ACM大赛真题试题_电脑基础知识_IT/计算机_专业资料。重庆市第二...

ACM竞赛之输入输出

ACM竞赛之输入输出_计算机软件及应用_IT/计算机_专业资料。ACM以下内容来源于互联网。 在 ACM 程序设计竞赛中,一道题目的所有测试数据是放在一个文本文件中,选 手...

ACM竞赛之新人向导

ACM竞赛简介和入门 5页 2财富值 ACM竞赛STL 31页 2财富值 上大ACM讲义 9...程序清单等参考资料,试题的解答提交裁判称为运行,每一次运行会被 判为正确或者...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com