WHUST 2017 Div.2 Day 3.5 C++ 标准模版库

Size: px

Start display at page:

Download "WHUST 2017 Div.2 Day 3.5 C++ 标准模版库"

柴笋叶
4 years ago
Views:

1 标准模版库标准模版库集训队郭松集训队郭松标准模版库

2 标准模版库纲介绍算法竞赛中, 需要到的知识命名空间代码框架实参类型模版函数简介模版类简介集训队郭松标准模版库

3 标准模版库介绍算法竞赛中, 需要到的知识算法竞赛中, 需要到的知识标准命名空间 std 集训队郭松标准模版库

4 标准模版库介绍算法竞赛中, 需要到的知识算法竞赛中, 需要到的知识标准命名空间 std 模版函数集训队郭松标准模版库

5 标准模版库介绍算法竞赛中, 需要到的知识算法竞赛中, 需要到的知识标准命名空间 std 模版函数模版类集训队郭松标准模版库

6 标准模版库介绍命名空间命名空间中引了命名空间的概念集训队郭松标准模版库

7 标准模版库介绍命名空间命名空间中引了命名空间的概念的标准函数都在标准命名空间 std 中集训队郭松标准模版库

8 标准模版库介绍命名空间命名空间中引了命名空间的概念的标准函数都在标准命名空间 std 中对命名空间的了解只需要做到知道有这东西即可集训队郭松标准模版库

9 标准模版库介绍命名空间命名空间中引了命名空间的概念的标准函数都在标准命名空间 std 中对命名空间的了解只需要做到知道有这东西即可在 #include 语句之后加上 using namespace std; 即可集训队郭松标准模版库

10 标准模版库介绍代码框架代码框架 { #include <bits/stdc++.h> using namespace std; int main() return 0; } 集训队郭松标准模版库

11 标准模版库介绍代码框架代码解释在 bits/stdc++.h 头件包含了所有的头件, 在算法竞赛中你可以随意使, 但请不要在算法竞赛之外的场合使集训队郭松标准模版库

12 标准模版库介绍代码框架代码解释在 bits/stdc++.h 头件包含了所有的头件, 在算法竞赛中你可以随意使, 但请不要在算法竞赛之外的场合使在算法竞赛中, 我们推荐使 scanf printf 作为输输出语句, 它们有更的效率集训队郭松标准模版库

13 标准模版库介绍代码框架代码解释在 bits/stdc++.h 头件包含了所有的头件, 在算法竞赛中你可以随意使, 但请不要在算法竞赛之外的场合使在算法竞赛中, 我们推荐使 scanf printf 作为输输出语句, 它们有更的效率标准新增了很多新的语法, 在这暂时不介绍, 在后遇到的时候结合实际的代码介绍集训队郭松标准模版库

14 标准模版库介绍实参代码中引了实参的概念, 这意味着你可以不那么多指针如你可以这样在函数中交换两个外部变量 void swap (int& a, int& b) { int t; t = a; a = b; b = t; } { int main() int a = 3, b = 4; swap(a, b); // a = 4, b = 3 } 使法很简单, 在想使实参的参数前加上 & 即可集训队郭松标准模版库

15 标准模版库介绍类型标准中, 引了 auto 类型, 来让编译器动猜测数据类型, 在不便写数据类型, 或数据类型很的时候很管 auto a = 1; // a is an int auto b = a; // b is an int auto c; // 错误, 法猜测类型注意类型猜测规则可能与你想的不样, 请在可以完全确定变量的数据类型的时候使它集训队郭松标准模版库

16 标准模版库模版函数简介模版函数我们使的原因就是其提供了丰富的模版函数, 这些函数多包含于头件中, 如果要在别的地使, 只需要 #include<algorithm> 的模版函数很多, 我们只介绍算法竞赛中常的种集训队郭松标准模版库

17 标准模版库模版函数 swap 交换两个元素定义 void swap (T& a, T& b); 注意参数表的 T 表任意类型, 同个字表同种类型即这要求两个元素类型相同集训队郭松标准模版库

18 标准模版库模版函数法 int a = 1, b = 2; swap(a, b); // a = 2, b = 1 int c = 1; double d = 2.; swap(c, d); // 编译错误,c d 类型不同 int e = 1; swap(e, 2); // 编译错误, 常数不能转为实参类型集训队郭松标准模版库

19 标准模版库模版函数 sort 对数组进排序, 效率为 ( ) 定义 void sort (RandomAccessIterator first, RandomAccessIterator last); void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); 注意 RandomAccessIterator 随机访问迭代器, 你可以理解为指针 Compare 较器, 你可以理解为函数指针 sort 如果不定义较器, 则按照从小到的顺序排序 sort 的排序范围是左闭右开的集训队郭松标准模版库

20 标准模版库模版函数法 int a[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; sort(&a[0], &a[10]); // a: 法 bool cmp(int a, int b) { return a > b; } int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; sort(&a[0], &a[10], cmp); // a: 集训队郭松标准模版库

21 标准模版库模版函数 min / max 返回者中较的个定义 T& min (const T& a, const T& b); T& max (const T& a, const T& b); 集训队郭松标准模版库

22 标准模版库模版函数法 cout << min(1,2) << \n ; // 1 cout << min(2,1) << \n ; // 1 cout << min( a, z ) << \n ; // a cout << min(3.14,2.72) << \n ; // 2.72 min(1, 2ll); // 编译错误, 类型不符集训队郭松标准模版库

23 标准模版库模版类简介模版类我们使的另原因即是其提供了量的基本数据结构, 对于解决简单的题它们分有, 这些数据结构有变长数组队列栈堆集合映射等等集训队郭松标准模版库

24 标准模版库模版类映射 map 定义了这样的种操作, 即储存键值对, 并持在 () 时间内返回给定的键对应的值的功能声明 map< 键类型, 值类型 > XXX; 集训队郭松标准模版库

25 标准模版库模版类使 map<char, string> mymap; mymap[ a ]= AAA ; mymap[ b ]= BBB ; mymap[ c ]=mymap[ b ]; cout << mymap[ a ] << \n ; // AAA cout << mymap[ b ] << \n ; // BBB cout << mymap[ c ] << \n ; // BBB cout << mymap[ d ] << \n ; // ( 空 ) 集训队郭松标准模版库

26 标准模版库模版类使 map<char, string> mymap; mymap[ a ]= AAA ; map<char, string>::iterator x = mymap.find( a ); cout << x->first << << x->second << \n ; // a AAA map<char, string>::iterator y = mymap.find( b ); cout << (y == mymay.end()) << \n ; // 1 注意这样查找, 如碰到空元素不会创建集训队郭松标准模版库

27 标准模版库模版类队列 queue 提供了与基本数据结构的队列功能致的队列声明 queue< 值类型 > XXX; 集训队郭松标准模版库

28 标准模版库模版类使 queue<int> myqueue; myqueue.push(5); myqueue.push(6); myqueue.front(); // 5 myqueue.size(); // 2 while (!myqueue.empty()) { cout << myqueue.front() << ; myqueue.pop(); } // 5 6 集训队郭松标准模版库

29 标准模版库模版类集合 set 提供了与数学中的集合功能致的集合, 带排序与去重声明 set< 值类型 > XXX; 集训队郭松标准模版库

30 标准模版库模版类遍历 set<int> myset; for (int i=5; i >= 1; i--) myset.insert(i*10); for (set<int>::iterator it = myset.begin(); it!= myset.end(); it++) cout << *it << ; // 时间复杂度遍历整个集合的复杂度是 () 集训队郭松标准模版库

31 标准模版库模版类查找删除 // 假设有 set, 内容为 set<int>::iterator it; it = set.lower_bound(20); // 20 it = set.lower_bound(21); // 30 it = set.upper_bound(20); // 30 it = set.find(35); // it == set.end() it = set.find(30); // *it = 30 set.erase(it); // set: set.erase(10); // set: set.clear(); // set: <empty> 集训队郭松标准模版库

32 标准模版库模版类时间复杂度查找的复杂度是 ( ) 使第种法删除个元素的复杂度是 (1) 使第种法删除个元素复杂度是 ( ) 清空的复杂度是 () 集训队郭松标准模版库

33 标准模版库模版类栈 set 提供了与基本数据结构功能致的栈声明 stack< 值类型 > XXX; 集训队郭松标准模版库

34 标准模版库模版类使 stack<int> mystack; for (int i=0; i<5; ++i) mystack.push(i); cout << Popping out elements... ; while (!mystack.empty()) { cout << << mystack.top(); mystack.pop(); } std::cout << \n ; // Popping out elements 集训队郭松标准模版库

35 标准模版库模版类向量, 变数组 vector 提供了与数组操作类似, 但度可变的数组声明 vector< 值类型 > XXX; 集训队郭松标准模版库

36 标准模版库模版类使 vector<int> myvector; for (int i = 0; i < 10; i++) myvector.push_back(10 - i); myvector.size(); // 10 myvector[3]; // 7 sort(myvector.begin(), myvector.end()); for (int i = 0; i < 10; i++) cout << myvector[i] << ; // 集训队郭松标准模版库

37 标准模版库延伸阅读集训队郭松标准模版库

38 标准模版库延伸阅读别的代码集训队郭松标准模版库

C 1 # include <stdio.h> 2 int main ( void ) { 4 int cases, i; 5 long long a, b; 6 scanf ("%d", & cases ); 7 for (i = 0;i < cases ;i ++) 8 { 9

C 1 # include <stdio.h> 2 int main ( void ) { 4 int cases, i; 5 long long a, b; 6 scanf (%d, & cases ); 7 for (i = 0;i < cases ;i ++) 8 { 9 201 201 21 ( ) 1. C pa.c, pb.c, 2. C++ pa.cpp, pb.cpp Compilation Error long long cin scanf Time Limit Exceeded 1: A 1 B 1 C 5 D RPG 10 E 10 F 1 G II 1 1 201 201 C 1 # include 2 int main ( void