1、不定数组（vector）单县第一中学2017级信息学奥林匹克竞赛知识选讲一、定义 Vector是一个不定数组，其大小可根据需要随时变动，可定义为一维数组，或者二维数组，甚至多维。数据库为#include 定义如下：1一维：vector vec;/定义了一个名为vec 的一维数组 2二维：vectorvec10;/定义了一个第一 维为10，二维动态 的数组二、使用 数组插入元素：数组插入元素：vec.push_back(同类型量);作用是在vector的末尾插入新元素；2.insert()第一个参数为迭代器，作用为在迭代器前面插入新元素；3.assign(5,1)向vector中加入5个1，同时
2、清除掉以前的元素。二、使用 数组删除元素：1.pop_back()删除最后一个元素。2.erase（）删除指定位置元素。（其中的参数要是指针变量，比如begain(),end(),以及迭代器值），例如vec.erase(vec.begin()+2);删除第3个元素 3.clear（）清除所有元素。4.empty（）判断该数组是否为空二、使用 访问数组：1.front()访问第一个元素（第一个元素的值而不是地址！begin()相反）2.back()访问最后一个元素（最后一个元素的值而不是地址！end()相反）3.size()数组的元素个数三、使用范例#include#includeusing n
3、amespace std;int main()vector a;for(int i=1;i=100;i+)a.push_back(i);couta.size()=1;i-)couta.back();a.pop_back();coutna.size();return 0;集合（set）单县第一中学2017级信息学奥林匹克竞赛知识选讲一、定义 set的特点是：会对集合中的元素根据键值自动排序，而且不允许集合中有重复元素 头文件：#include set中的函数：声明：set 名称 例如：sets1;begin()返回指向第一个元素的迭代器迭代器 end()返回指向最后一个元素的迭代器迭代器二、迭代
4、器迭代器 关于迭代器：声明：set:iterator 名称 访问迭代器指向元素时使用 *名称 需要注意的是：迭代器只能自增，不能+1或者-1或者其他操作迭代器的类型要与定义的set类型相同三、使用 常用的函数：begin()返回set容器的第一个元素的地址 end()返回set容器的最后一个元素地址 clear()删除set容器中的所有的元素 empty()判断set容器是否为空 max_size()返回set容器可能包含的元素最大个数 size()返回当前set容器中的元素个数 erase(it)删除迭代器指针it处元素使用样例#include#include using namespace
5、 std;int main()set s;s.insert(1);s.insert(2);s.insert(3);s.insert(1);coutset 的 size 值为：s.size()endl;coutset 的 maxsize的值为：s.max_size()endl;coutset 中的第一个元素是：*s.begin()endl;coutset 中的最后一个元素是:*s.end()endl;s.clear();if(s.empty()coutset 为空！endl;coutset 的 size 值为：s.size()endl;coutset 的 maxsize的值为：s.max_siz
6、e()endl;return 0;三、使用 1.count():用来查找set中某个元素出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。2.find():用来查找set中某个元素出现的位置。如果找到，就返回这个元素的迭代器，如果这个元素不存在，则返s.end()。(最后一个元素的下一个位置，s为set的变量名)使用样例#include#include using namespace std;int main()set s;set:iterator it;/创建一个他对应的迭代器 s.insert(1);s.inse
7、rt(2);s.insert(3);s.insert(1);coutset 中 1 出现的次数是：s.count(1)endl;coutset 中 4 出现的次数是：s.count(4)endl;it1=st1.find(4);/查找数据 if(it1!=st1.end()/如果找到就输出数据 cout *it1 endl;return 0;三、使用/遍历数据，用迭代器遍历数据for(set:iterator it=s.begin();it!=s.end();+it cout *it endl;/这里用到了set中的元素已经从小到大排好序的性质使用样例#include#includeusing
8、 namespace std;seta;int main()int b;for(int i=1;ib;a.insert(b);for(set:iterator i=a.begin();i!=a.end();i+)cout*iendl;return 0;三、使用（结构体）struct Info string name;double score;bool operator (const Info&a)const/重载“”即可。return a.score score;int main()set s;Info info;/插入三个元素 info.name=Jack;info.score=80;s.i
9、nsert(info);info.name=Tom;info.score=99;s.insert(info);info.name=Steaven;info.score=60;s.insert(info);set:iterator it;for(it=s.begin();it!=s.end();it+)cout (*it).name :(*it).score endl;return 0;运行结果：Tom:99Jack:80Steaven:60四、其他函数库删除函数erase();根据元素的值删除元素不能根据第几个元素进行删除插入元素：insert();clear()-清除所有元素 count()
10、-返回某个值元素的个数 empty()-如果集合为空，返回true equal_range()-返回集合中与给定值相等的上下限的两个迭代器 find()-返回一个指向被查找到元素的迭代器 get_allocator()-返回集合的分配器 lower_bound()-返回指向大于（或等于）某值的第一个元素的迭代器 key_comp()-返回一个用于元素间值比较的函数 max_size()-返回集合能容纳的元素的最大限值rbegin()-返回指向集合中最后一个元素的反向迭代器 rend()-返回指向集合中第一个元素的反向迭代器 size()-集合中元素的数目 swap()-交换两个集合变量 upp
11、er_bound()-返回大于某个值元素的迭代器 value_comp()-返回一个用于比较元素间的值的函数映射（map）单县第一中学2017级信息学奥林匹克竞赛知识选讲一、定义 Map就是从键（key）到值（value）的映射。因为重载了运算符，map像是数组的高级版。头文件：#include 定义：例如：map a/建立一个char到int的映射a 使用样例#include#include using namespace std;mapdate;int main()date7月30日=730;coutdate7月30日;return 0;二、使用 常用语句：begin（）返回map头部迭代
12、器 end（）返回尾部迭代器 clear（）清空所有元素 erase（）删除一个元素 find（）查找一个元素 empty（）如果为空则返回true size（）返回map大小 count（elem）返回某个元素个数三、例题题目是这样的：给出一串数以及一个数字 C，要求计算出所有 A-B=C 的数对 的个数。（注意：不同位置的数字一样的数对算不同的数对）Input Format第一行包括 2 个非负整数 N 和 C，中间用空格隔开。第二行有 N 个整数，中间用空格隔开，作为要求处理的那串数。Output Format输出一行，表示该串数中包含的所有满足 A-B=C 的数对的个数。Sample
13、Input4 11 1 2 3Sample Output3Data Limit对于 50%的数据，N=2000；对于 100%的数据，N=200000。例题分析 咱们定义一个map桶：mapm;这个桶的用法（就是普通的桶的用法）：mi表示数字i出现的次数。如果我们用普通数组，那么根据题意，我们定义的数组的成员个数至少为2147483647，就是长整型的最大值。而map为什么不会超呢？因为map是映射，它那个中括号里的数字只是一个键（这说起来很复杂）唉，口头表达能力不行，简单了说吧，就是说map你没有定义过某个键，它就不会占用空间，当你去映射一个没有访问过的键时，它会自动返回0。等于是说map桶
14、去除了所有的空桶所占的空间。那么这题中我们只会用到=200000个桶。代码展示（缺少头文件）map m;/咱们的map桶 int n;long c,num200005;int main()scanf(%d%ld,&n,&c);/n个数字，c是差值 int ans=0,i=n;while(i-)scanf(%d,&numi);mnumi+;/装到桶里去 i=n;if(c0)/特判0 while(i-)ans+=mnumi+c;else while(i-)ans=ans+mnumi+c-1;/当c为0时每个数字还得排掉自己呢 printf(%d,ans);return 0;三、例题（UVa 156
15、-反片语）输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重拍，得到输入文本中的另外一些单词。在判断是否满足条件时，字母不区分大小写，但在输出时应保留输入中的大小写，按字典序进行排序（所有大写字母在所有小写字母的前面）。Sample input：ladder came tape soon leader acme RIDE lone Dreis peat ScAlE orb eye Rides dealer NotE derail LaCeS drIed noel dire Disk mace Rob dries#Sample output：Disk NotE derail drIe
16、d eye ladder soon 试题分析 整体思路：1.写一个标准化函数（实现大写字母转换为小写（tolower（）函数），单词排序。注意使用const是为了不改变s的初值）2.两个vector容器（words，ans），一个map容器（cnt）words存储所有的单词map存储标准化后对应单词以及出现次数的值，相当于一个表格。words经过查表map，把对应的符合值给ans 代码无课后习题（map）加法模板单县第一中学2017级信息学奥林匹克竞赛知识选讲代码展示#includeusing namespace std;template struct pointt x,y;point(t x=0,t y=0):x(x),y(y);template point operator+(const point&a,const point&b)return point(a.x+b.x,a.y+b.y);template ostream&operator(ostream&out,const point&p)out(p.x,p.y);return out;int main()point a(1,2),b(3,4);point c(1.1,2.2),d(3.3,4.4);couta+b c+dn;return 0;谢谢观看
