《信息学奥赛NOIP标准模板库入门》由会员分享，可在线阅读，更多相关《信息学奥赛NOIP标准模板库入门（77页珍藏版）》请在金锄头文库上搜索。
1、STL入门STLStandardTemplateLibrary（标准模板库），惠普实验室开发的一系列软件的统称。STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。STL在C+标准中，STL被组织为下面的13个头文件：、和。容器（container）经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入。STL容器对最常用的数据结构
2、提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。容器部分主要由,和组成。Vector简介Vector是一种动态数组，是基本数组的类模板。vector的存储是自动管理的，按需扩张收缩。需要头文件或头文件其内部定义了很多基本操作，包括插入、删除、访问等，使用起来十分方便。在开启O2优化的情况下，Vector的访问速度甚至能够快过一般的数组，在STL的日益普及下，Vector必将被广泛应用。Vector的定义与赋值如图，Vector既然是一类数组，那它就能够当做数组定义、使用、赋值。Vector中可以定义的类型不限，既可以是int、char这样的类型，
3、也可以是结构体，甚至是Vector。Vector的Size与Push_back操作Push_back(x)是Vector的成员函数，它能够在Vector的末尾加入一个元素x。Size()也是Vector的成员函数，其返回值是Vector中的元素个数。注意，访问不在Vector中的位置是未定义的行为。Vector的Begin、End与iterator在每种STL容器中都定义了自己的迭代器类型。迭代器(iterator)是一种检查容器内元素并遍历元素的数据类型。迭代器相当于一种指针，是容器中一个元素的地址，(*迭代器)才会指向具体的元素。迭代器的+、-运算被重载过，详见下页实例。Begin(),E
4、nd()是Vector的成员函数，返回值分别是Vector中首个元素的迭代器和Vector中末尾元素向后一位的迭代器。Vector元素的遍历结合实例，我们可以进一步理解iterator的使用方式。下面的循环中i+也可以改写为i+=1或i=i+1，可以理解为将i指向下一个位置。Vector应用存图N个点，M条边，点数不超过100000，边数不超过1000000,再求图上的一些东西。如何存这幅图？邻接矩阵,空间复杂度O(n2)，遍历时间复杂度O(n2)，BOOM！邻接表,空间复杂度O(m)，遍历时间复杂度O(m)，有一定代码量要求，不适合新手。介于两者之间，用fij表示i点出去的第j条边空间复杂度
5、O(n2)遍历时间复杂度O(m)。虽然图整体较为稀疏，但由于不知道每个点最多有几条边，故还是需要预开100000*100000的空间BOOMVector应用谁的孙子最多给定一棵树，其中1号节点是根节点，问哪一个节点的孙子节点最多，有多少个。（孙子节点，就是儿子节点的儿子节点。）【输入要求】第一行一个整数N（N100000），表示树节点的个数。此后N行，第i行包含一个整数Ci，表示i号节点儿子节点的个数，随后共Ci个整数，分别表示一个i号节点的儿子节点。Vector应用谁的孙子最多【输出要求】一行两个整数，表示孙子节点最多的节点，以及其孙子节点的个数，如果有多个，输出编号最小的。【输入样例】52
6、23140150【输出样例】11Vector的Insert操作Insert(x,y)是Vector的成员函数，其中，x是一个迭代器，y是一个具体的值。Insert(x,y)在x对应的元素之前插入了一个值为y的元素。Vector的Erase操作Erase(x),Erase(x,y)是Vector的成员函数，其中，x,y是迭代器。分别能够删除x处的元素或区间x,y)内的元素。由于Vector的分块存储方式，Erase的复杂度为O(Log(size()。Vector的Clear操作Clear()是Vector的成员函数，使用后将Vector的Size()设置为0。然而，我们看到，Clear之后，元素
7、并没有被删除，空间也没有释放。因此，Clear是O(1)的。vector应用链表操作给定一个N个数的数组，M次操作，每次操作为下列操作之一。求最后的数组。操作1：在第X个数之后插入一个数Y。操作2：删除第X个数。【输入要求】第一行两个整数N，M（N，M100000）含义见试题描述。第二行N个整数，表示原来的数组。vector应用链表操作接下来M行，每行第一个数OPT，表示操作类型。对于操作1，接下来两个数X，Y，含义见题面描述，保证0X当前数的个数，若X=0，表示在数组开头插入。对于操作2，接下来一个数X，含义见题面描述，保证1X当前数的个数。【输出要求】输出若干个数，表示最后的数组。vect
8、or应用链表操作【输入样例】53123451162122【输出样例】6345Algorithm库函数在Vector的应用Sort(x,y)对于区间x,y)实现了排序。同样，它也可以用于Vector。类似地，Reverse(x,y)对区间x,y)实现了翻转。它同样能够作用在Vector中。vector之sort应用排序给定N个数组，要求先对这N个数组分别进行排序，然后再根据N的数组的字典序对这N个数组进行排序。输出排序的结果。【输入要求】第一行一个整数N，表示数组数。接下来N（N1000）行，每一行先包含一个整数SUM（SUM1000），表示数组的大小，接下来SUM个整数，表示数组中的一个元素。
9、vector之sort应用排序输出要求】共N行，每行表示一个数组。【输入样例】413112213231【输出样例】11 21 2 33vector之reverse应用序列翻转给定一个N个数的数组，M次操作。每次操作将数组的一段翻转，求最后的数组。【输入要求】第一行两个整数N，M（N，M1000）含义见试题描述。第二行N个整数，表示原来的数组。接下来M行，每行两个整数X，Y（1XYN），表示翻转区间X,Y。vector之reverse应用序列翻转【输出要求】一行N个整数，表示操作后的数组。【输入样例】52123452445【输出样例】14352在Vector中删除某关键字的元素Remove移动指
10、定区间中的元素直到所有“不删除的”元素在区间的开头（相对位置和原来它们的一样）。它返回一个指向最后一个的下一个“不删除的”元素的迭代器。所以，我们用前面讲到的Erase即可删除某关键字的元素Vector的比较Vector重载了比较运算符，比较的结果是字典序比较的结果。所谓字典序比较，就是类似于字符串的比较，按位比较，有结果则结束。SET的基本用法的基本用法set是STL中一种标准关联容器，封装了一种高效的平衡检索二叉树红黑树。set是用来存储同一数据类型的集合，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。支持O(log(size)复杂度的插入、删除、查找操作。虽然存在一定
11、的常数，但开启O2优化后效率非常高。set不支持插入重复的元素。若要插入重复元素可使用multiset，其用法与set几乎完全相同。set中数元素的值不能直接被改变。set的构造直接用类似STL其他容器的方式构造Set。Set中的元素可以是任意类型的，但是由于需要排序，所以元素必须有一个序，即大小的比较关系。set的赋值如图，c+11中，set可以像数组一样赋初值，但是赋值完成后set中的元素是自动排好序的。set没有尾部插入函数push_back()，元素的插入一般使用insert进行动态检索插入。a.insert(x)-在集合中a中插入元素x，x的类型必须与set的元素类型一致。如果插入的
12、元素在set中已存在则会忽略。set的begin、end与iterator迭代器(iterator)是一种检查容器内元素并遍历元素的数据类型。set的迭代器是封装了元素节点的指针，(*迭代器)才会指向具体的元素。set的迭代器仅支持+和，不支持+=和=。这意味着无法快速定位到set中的第k个元素。Begin(),End()是set的成员函数，返回值分别是set中首个元素的迭代器和set中末尾元素向后一位的迭代器。set的输出set不能像数组的输出那样使用下标输出，需要使用迭代器依次遍历。使用迭代器时，要写成it!=a.end()；输出的是*it。set的begin()和rbegin()set中
13、的元素总是保持单调递增。因此：begin()返回的迭代器指向set中的最小值；rbegin()返回的迭代器指向set中的最大值。set的end()和rend()set中的元素总是保持单调递增。end()返回的迭代器指向set中的最后元素的后一个位置；rend()返回指向集合中第一个元素的前一个位置的迭代器set的end()和rend()set中的元素总是保持单调递增。end()返回的迭代器指向set中的最后元素的后一个位置；rend()返回指向集合中第一个元素的前一个位置的迭代器set中size、empty和clearSize()是set的成员函数，其返回值一个无符号整数，表示set中元素的个
14、数。时间复杂度O(1)。empty()返回一个bool类型，表示set是否为空。时间复杂度O(1)。clear()清除set中的所有元素。时间复杂度O(size)。set应用random明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成去重与排序的工作。set应用random输入要求第1行为1个正整数，表示所生成的随机数的个数：N(N100)第2行有N个用空格隔开的
15、正整数，为所产生的随机数。输出要求第1行为1个正整数M，表示不相同的随机数的个数。第2行为M-1个用空格隔开的正整数(行尾没有多余的空格)，为从小到大排好序的不相同的随机数。set应用random输入样例102040326740208930040015输出样例8152032406789300400set中的erase操作用erase(x)删除元素。其中x可以是具体的数或迭代器。删除set中不存在的元素会被忽略。erase(iterator)删除迭代器iterator指向的元素erase(first,second)删除迭代器first,second)之间的元素erase(key_value)删除
16、键值key_value的元素set中的find操作find(x)返回x元素的迭代器，如果找不到x就返回end()的迭代器。set应用sumx考虑一组n个不同的正整数a1,a2,.,an，它们的值在1到1000000之间。给定一个整数x。写一个程序sumx计算这样的数对个数(ai,aj)，1=ij=n并且ai+aj=x。输入要求标准输入的第一行是一个整数n(1=n=1000000)。第二行有n个整数表示元素。第三行是一个整数x(1=x=2000000)。输出要求输出一行包含一个整数表示这样的数对个数。set应用sumx输入样例951271091231113输出样例3知识点及提示不同的和为13的数
17、对是(12,1),(10,3)和(2,11)。lower_bound和upper_boundlower_bound(x)返回set中大于等于x的最小元素的迭代器。upper_bound(x)返回set中大于x的最小元素的迭代器。如果找不到也会返回end()的迭代器。multisetmultiset和set的定义和成员函数都相同。multiset和set的区别是：set插入的元素不能相同，但是multiset可以相同。如果删除元素x,那么在定义的比较关系下和x相等的所有元素都会被删除。count(x)：set能返回或者，multiset是有多少个返回多少个。multiset应用dec给定N个数A
18、i，以及一个正整数C，问有多少对i,j，满足Ai-Aj=C。输入要求第一行输入两个空格隔开的整数N和C第2至N+1行每行包含一个整数Ai输出要求输出一个数表示答案。multiset应用dec输入样例5321425输出样例3PAIR的基本用法pair是一种模版类型，又称二元组。每个pair可以存储两个值。这两种值无限制。也可以将自己写的struct的对象放进去，或者可以说pair是一个二元组的结构体，定义完成的pair类型可以用在多种场合。定义，例如：pairp;pairp;PAIR的基本用法pair是一种模版类型，又称二元组。pairp;pairp;pairchar,pairp;/也可以这样定
19、义一个三元组pair的使用pair的赋值paira;方式一：make_pair(233,a);方式二：a.first=233;a.second=a;这两种方式都可以实现对a的赋值，建议用方式一pair的使用pair的使用赋值完成后使用第一关键字要用a.first表示,第二关键字用a.second表示支持以first为第一关键字，second为第二关键字的比较函数(,=,=,!=)pair应用买蛋糕2今天是路路的生日，生日蛋糕自然是少不了。路路的朋友们一起去蛋糕店来买蛋糕，可是等一行人到了蛋糕店之后，发现那里是人山人海啊-_-。这下可把店家给急坏了，因为人数过多，需求过大，所以人们要等好长时间才
20、能拿到自己的蛋糕。由于每位客人订的蛋糕都是不同风格的，所以制作时间也都不同。老板为了最大限度的使每位客人尽快拿到蛋糕，因此他需要安排一个制作顺序，使每位客人的平均等待时间最少。这使他发愁了，于是他请你来帮忙安排一个制作顺序，使得每位客人的平均等待时间最少。pair应用买蛋糕2输入要求输入有两行。第一行是一个整数n，表示有n种蛋糕等待制作（1n100）。第二行有n个数，第i个数表示第i种蛋糕的制作时间。输出要求输出包括一行，有n个整数，整数间用空格隔开，行末没有空格，是蛋糕的制作顺序，每个数即是蛋糕的编号。pair应用买蛋糕2输入样例845331467输出样例53416278MAP&MULTIM
21、AP基本用法Map是STL的一个关联容器，它提供一对一的数据处理能力，map不允许重复元素。其中第一个称为关键字key，每个关键字只能在map中出现一次，第二个称为该关键字的值value，元素的次序由它们的key决定，和value无关。MAP&MULTIMAP基本用法map内部自建一颗红黑树，这颗树具有对数据自动排序的功能，所以map根据元素的key自动对元素进行排序。这么一来，根据已知的key搜寻某个元素时，时间复杂度为O(1)，而根据已知value搜寻元素时，性能就很糟糕。可起到hash表的作用。Map的功能自动建立Keyvalue的对应。key和value可以是任意你需要的类型。根据ke
22、y值快速查找记录。快速插入Key-Value记录。快速删除记录。根据Key修改value记录。遍历所有记录。Map的定义需要头文件或构造函数：mapa;map对象是模板类，需要关键字和存储对象两个模板参数。例如mapa;这样就定义了一个用int作为索引,并拥有相关联的指向string的指针。Map的赋值Map赋值的两种方法：用insert函数插入pair数据、用数组方式插入数据。以上两种用法的区别:用insert函数插入数据，在数据的插入上涉及到map关键字的唯一性这个概念。即当map中有这个关键字时，insert操作无效的。用数组方式它可以覆盖以前该关键字对应的值。时间复杂度皆为O(logn
23、)。Map的Begin、End与iteratormap的迭代器(iterator)是一种检查容器内元素并遍历元素的数据类型。Begin(),End()是map的成员函数，返回值分别是map中首个元素的迭代器和末尾元素向后一位的迭代器。map的迭代器仅支持+和。时间复杂度O(1)Map的输出map的单个value可以像数组那样使用下标输出。要输出所有元素需要使用迭代器依次遍历。输出it-first对应的关键字key输出it-second对应的为其value。Map的rbegin()和rend()Map中的元素总是保持单调递增。begin()返回的迭代器指向map中的最小key值；rbegin()
24、返回的迭代器指向map中的最大key值。Map中的元素总是保持单调递增。end()返回的迭代器指向Map中的最后元素的后一个位置；rend()返回指向Map中第一个元素的反向迭代器Map的反序遍历map中size、empty和clearSize()是map的成员函数，其返回值一个无符号整数，表示map中元素的个数。时间复杂度O(1)。empty()返回一个bool类型，表示map是否为空。时间复杂度O(1)。clear()清除Map中的所有元素。时间复杂度O(size)。Map应用count有n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现
25、在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。【输入要求】输入包含n+1行：第1行是整数n，表示自然数的个数。第2到n+1行每行一个自然数。Map应用count【输出要求】从小到大输出若干行，每行为一个数字和它出现的次数。【数据范围】n300000Map应用count【输入样例】8242451002100【输出样例】2342511002Map应用drawer期末考试即将来临，小T由于同时肩负了学习、竞赛、班团活动等多方面的任务，一直没有时间好好整理他的课桌抽屉，为了更好地复习，小T首先要把课桌抽屉里的书分类整理好。小T的抽屉里堆着N本书，每本书的封面上都印有学科名
26、称，学科名称用一个字符串表示，如语文学科的书封面上都印有“chinese”。现在，你的任务是帮助小T找出哪个学科的书最多？Map应用drawer输入数据输入文件第一行包含一个自然数N（0N1000）表示抽屉中书的总数。接下来N行每行包含一本书的学科名称，学科名称是一个长度不超过15的由小写英文字母组成的字符串。输出数据输出文件仅有一行包含一个字符串，表示最多的那种书的学科名称。数据保证答案一定是唯一的。Map应用drawer【输入样例】5englishchinesephysicschinesechinese输出样例】chineseMap中的countcount()用来查找Map中某个某个键值出
27、现的次数，这个函数在Map只可能出现0或1次。Map中的find()find(x)返回x元素的迭代器，如果找不到x就返回end()的迭代器。时间复杂度皆为O(logn)lower_bound和up_boundlower_bound(x)返回Map中key大于等于x的最小元素的迭代器，时间复杂度皆为O(logn)。upper_bound(x)返回Map中key大于x的最小元素的迭代器。如果找不到也会返回end()的迭代器。Map中的erase操作用erase(x)删除一个元素。其中x可以是具体的数或迭代器。删除Map中不存在的元素会被忽略。a.erase(begin(),end()效果和a.cl
28、ear()相同时间复杂度O(n)Map应用matchn个不同的字符串，每个字符串对应一个数字。q次询问一个字符串对应什么数字。【输入要求】第1行n，q。第2到n+1行，每行一个字符串和一个数字，中间用一个空格隔开。第n+2到n+q+1行，每行一个询问的字符串。【输出要求】q行，每行一个数字【数据范围】n,q20000每个字符串的长度30Map应用match【输入样例】53fs3fwe34838fdeewerwer54irjfhid888847hhhh1000000000847hhhhfs3fwe【输出样例】013MULTIMAP基本用法multimap简介&功能multimap与map类似，操作大部分也与map一样。所不同的是它允许重复键。即一个关键词可以有很多不同的值。这些值按插入的时间顺序排列。multimap和map的区别在multimap中没有定义运算符，因此，multimap进行插入的时候，只能利用insert()函数进行插入。使用find(x)查找返回每种关键词的所有元素的第一个元素的迭代器。multimap和map的区别指定关键词的遍历：equal_range(x)返回一对iterator的pair，表示关键词x的位置的区间（左闭右开）。这个函数其实map也有。也可用lower_bound和upper_bound实现。
