没有合适的资源?快使用搜索试试~ 我知道了~
STL(Standard Template Library,标准模板库)是C++语言标准中的重要组成部分。STL以模板类和模板函数的形式为程序员提供了各种数据结构和算法的精巧实现,程序员如果能够充分地利用STL,可以在代码空间、执行时间和编码效率上获得极大的好处。 STL大致可以分为三大类:算法(algorithm)、容器(container)、迭代器(iterator)。
资源推荐
资源详情
资源评论
第01篇 ACM/ICPC 竞赛之基础篇
一、ACM/ICPC 竞赛的特点
ACM/ICPC(国际大学生程序设计竞赛)是以算法设计为主的程序设计竞赛,并
不涉及具体的应用技术。
ACM/ICPC 竞赛以组队形式参赛,每个参赛队由三名队员组成,共同使用一台计
算机解题。通常每场比赛的试题为 6 至 10 题,根据各队的完成题数和罚时进行排
名。题目提交通过称为完成,从比赛开始到提交成功所用的时间为题目的基础罚
时,另外,一道题目每提交失败一次,将增加 20 分钟罚时。也就是说,参赛队要
尽可能用最快的速度、最少的失败次数,解决最多的题目。
二、输入和输出处理
试题一般采用标准输入和输出方式读取输入和产生输出,在题目中会详细描述输
入和输出的格式和值域范围,所写的程序一定要严格遵守题目指定的输入输出格
式。
在比赛试题的输入和输出处理上,针对一些常见的情形,有一些常用的方法。
1、多测试用例的输入和输出
有些试题在一次输入中只包含一个测试用例,也就是说,程序每运行一次,只算
一道题。也有些试题在一次输入中包含多个测试用例,也就是说,程序每运行一
次,要计算多道题。
对多用例输入,通常会先输入要计算的用例的个数,然后依次输入每个测试用例
的输入数据,但程序并不需要等到所有的测试用例都计算完后再输出所有测试用
例的计算结果,而是可以读入一个测试用例,输出一个结果,再读入一个测试用
例,再输出一个结果。因此对多用例输入的试题,可以用这样的输入模式:
以 C++为例:
intn;
cin>>n;
for(inti=0;i<n;i++)
{
读入测试用例数据
计算
输出计算结果
}
2、单测试用例输入的结束判断
对单用例输入,最主要的问题是如何知道输入什么时候结束。
有些试题会指定某种特殊的输入值作为输入的结束标志,这种情况比较容易处理,
只须在读入后,判断一下读入的内容是否为约定结束值即可。
有些试题并不指定特殊的输入值,而是以 EOF(文件结束标志)作为结束标志。
如果从文件流读入,当读到文件尾时,输入返回 EOF。如果从键盘读入时,在
Windows 的终端中,是以 Ctrl+Z 表示 EOF。对于这种情况,可以用这样的输入
模式:
以 C++为例:
intm,n;//假设要连续输入一组整数对
while(cin>>m>>n)
{
处理整数对(m,n)
}
以 C 语言为例:
intm,n;
while(scanf("%d%d",&m,&n)==2)
{
处理整数对(m,n)
}
三、数据结构的设计
很多试题中已经给出了数据量的上限,因此可以很方便地以数组的方式定义数据
结构。但也要注意到有些题目中没有明确指出数据上限时,切不可盲目定义数组
大小。
例如在题 1070(多项式求和)中,并未说明输入多项式的项数,对这种情况就不
宜用数组方式来表示多项式了——除非你的运气足够好,所开辟的数组大小能够
经受所有的测试用例的考验。
除了使用一般的数组或链表结构外,对使用 C++的选手来说,STL 也是一大利器,
充分运用可以有效提高编程的效率和正确性。
四、测试用例的考虑
在试题中通常会给出测试用例的样例,这通常会被我们用来测试自己的程序,而
且很多选手往往在正确计算出测试用例样例时,会认为自己的程序是正确的。
其实测试用例的样例只是测试用例的个例,实际用于测试的测试用例往往会涵盖
各种极限情况和边界情况,而且有时测试用例的数量还会比较大,甚至会重复测
试同一个测试用例。因此我们的程序能够通过样例测试,未必能够通过所有的测
试用例的测试,一方面要全面考虑所有可能的极限情况和边界情况,一方面程序
要有足够的效率。
第 03 篇 ACM/ICPC 竞赛之 STL--pair
STL 的<utility>头文件中描述了一个看上去非常简单的模板类 pair,用来表示一
个二元组或元素对,并提供了按照字典序对元素对进行大小比较的比较运算符模
板函数。
例如,想要定义一个对象表示一个平面坐标点,则可以:
pair<double,double>p1;
cin>>p1.9rst>>p1.second;
pair 模板类需要两个参数:首元素的数据类型和尾元素的数据类型。pair 模板类
对象有两个成员:9rst 和 second,分别表示首元素和尾元素。
在<utility>中已经定义了 pair 上的六个比较运算符:<、>、<=、>=、==、!
=,其规则是先比较 9rst,9rst 相等时再比较 second,这符合大多数应用的逻
辑。
当然,也可以通过重载这几个运算符来重新指定自己的比较逻辑。
除了直接定义一个 pair 对象外,如果需要即时生成一个 pair 对象,也可以调用在
<utility>中定义的一个模板函数:make_pair。make_pair 需要两个参数,
分别为元素对的首元素和尾元素。
在题 1067--UglyNumbers 中,就可以用 pair 来表示推演树上的结点,用 9rst
表示结点的值,用 second 表示结点是由父结点乘以哪一个因子得到的。
#include<iostream>
#include<queue>
usingnamespacestd;
typedefpair<unsignedlong,int>node_type;
main()
{unsignedlongresult[1500];
priority_queue<node_type,vector<node_type>,greater<node_type
>>Q;
Q.push(make_pair(1,2));
for(inti=0;i<1500;i++)
{
node_typenode=Q.top();
Q.pop();
switch(node.second)
{case2:Q.push(make_pair(node.9rst*2,2));
case3:Q.push(make_pair(node.9rst*3,3));
case5:Q.push(make_pair(node.9rst*5,5));
}
result[i]=node.9rst;
}
intn;cin>>n;
while(n>0)
{
cout<<result[n-1]<<endl;
cin>>n;
}
return1;
}
<utility>看上去是很简单的一个头文件,但是<utility>的设计中却浓缩反映了
STL 设计的基本思想。有意深入了解和研究 STL 的同学,仔细阅读和体会这个简
单的头文件,
不失为一种入门的途径。
第02篇 第 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(9rst,last);
定义一个 vector 对象,并从由迭代器 9rst 和 last 定义的序列[9rst,last)中复制
初值。
vector 的基本操作有:
s[i]
直接以下标方式访问容器中的元素。
s.front()
返回首元素。
s.back()
返回尾元素。
s.push_back(x)
向表尾插入元素 x。
s.size()
返回表长。
s.empty()
当表空时,返回真,否则返回假。
s.pop_back()
删除表尾元素。
s.begin()
返回指向首元素的随机存取迭代器。
s.end()
剩余24页未读,继续阅读
资源评论
c929833623
- 粉丝: 1
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功