ACM課程內容筆記(I)
2020/8/30
此檔案發布在博客園
視頻來源于 https://www.bilibili.com/video/BV1pE411E7RV?p=1
檔案格式: txt
如有紕漏敬請斧正
<Using fake-markdown 1.0.0>
C++ 與 STL
1.C++標準語法
(1) cin慢于scanf
讀10E5以上的資料應當使用scanf,cin會導致TLE(超時)
(2) C++ 語法特性
a. 動態分配記憶體
不支持變長陣列
平時寫題可以不釋放記憶體
b. 參考
用于簡化指標的代碼
c. 函式多載
d. struct
允許加入建構式
2.C++標準庫
(1)概述
<vector> <string> <algorithm> <queue> <stack> <set> <functional> <complex>
(2)回顧C標準庫
a. cstring
size_t strlen(const char *str) 獲取字串長度
strcmp() 字串比較
strcpy() 字串拷貝
memset()暴力清空
逐位元組填寫
1 memset(str,0,sizeof(str));//使用0填充整個str 2 memset(str,-1-sozeof(str));//見DP 3 memset(i,0x3f3f3f3f,sizeof(i))//使用最大值填充i
memcpy()暴力拷貝
b.cmath
c.cstdlib
qsort()
不常用，快速排序，速度真的快（真香！）
rand()
malloc()
free()
d.ctime
time(0)
從1970年到現在的秒數，用于srand(time(0))
clock()
程式啟動到目前位置的秒數
用于計時，單位為ms，
e.cctype
isdigit()
isalpha()
判斷是不是數字/字符
(3)vector
1.宣告
可變長度陣列
vector<int> arr1(100);
可以把vector看成鏈表
vector<int> arr1;
2.push_back()在最后加入元素
3.vector的遍歷
迭代器(iterator)
一種指標，通過迭代器可以獲得每個元素，用法和普通指標相同
vector<int>::iterator p = arr1.begin();
4.常見操作
size(); //元素個數
clear(); //清空陣列
empty(); //判斷陣列是否為空
begin(); //回傳首元素迭代器
end(); //回傳末元素迭代器
erase(iterator i); //洗掉i迭代器所在處的元素
push_back(...); //向陣列后面添加元素
pop_back(); //洗掉最后一個元素
(4)string
字串
可以看成vector<char>...
1.string 包含了vector的操作
2.常見操作
.length()
.size()
.insert(1,"aaa")
.insert(str.begin(),'a')
.c_str()
.append(another_str) 將another_str拼接到后面
.compare(another_str) 即strcmp(str,another_str)
(5)algorithm
提供了很多演算法
1.sort()
復雜度:O(nlogn)
1 int arr[]={2,4,1,5,4} 2 int n = 5; 3 sort(arr,arr+n); 4 sort(begin,end,cmpMethod)
（cmpMethod 排序依據)
內部排序是按小于關系來的
e.g.
1 bool cmp(Point a,Point b) 2 { 3 if(a.x != b.x) 4 { 5 return a.x<b.x 6 } 7 return a.y<b/y 8 }
也可以多載運算子
2.min()
3.max()
4.min_element()
5.max_element()
6.nth_element(begin,pos,end) 對第n小（從0開始算）的數放到第n個位置，部分快排
7.swap()
8.reverse()
9.unique()
要先sort,用于“線段樹和樹狀陣列”
int newLength = unique(arr.begin(),arr.end())-arr.begin();
10.lower_bound()
upper_bound()
二分查找，排好序的陣列中找到位置
lower查找下界
upper查找上界
(6)stack
后進先出
(7)queue
佇列，先進先出
priority_queue
優先佇列
(8)set
集合，在O(logn)的時間內查找、洗掉、添加某個元素
自帶去重
unordered_set
可以重復元素
(9)map
map 映射
pair 配對
unordered_map
(10)bitset
表示二進制，可以用下標訪問，也可以進行位運算
(11)funcational
配合priority_queue
(12)complex
復數類
(13)一鍵包含
#include <bits/stdc++.h>
** vs不能用
內容見附件
3.參考
https://www.cplusplus.com
4.細節
(1) 1s時限能進行的操作大概為1e8
(2) G++在輸出double不能用%lf，用%f
(3) 注意多組用例EOF、初始化
(4) const INF = 0x3f3f3f3f
5.stdc++.h
1 // C
2 #ifndef _GLIBCXX_NO_ASSERT
3 #include <cassert>
4 #endif
5 #include <cctype>
6 #include <cerrno>
7 #include <cfloat>
8 #include <ciso646>
9 #include <climits>
10 #include <clocale>
11 #include <cmath>
12 #include <csetjmp>
13 #include <csignal>
14 #include <cstdarg>
15 #include <cstddef>
16 #include <cstdio>
17 #include <cstdlib>
18 #include <cstring>
19 #include <ctime>
20
21 #if __cplusplus >= 201103L
22 #include <ccomplex>
23 #include <cfenv>
24 #include <cinttypes>
25 #include <cstdalign>
26 #include <cstdbool>
27 #include <cstdint>
28 #include <ctgmath>
29 #include <cwchar>
30 #include <cwctype>
31 #endif
32
33 // C++
34 #include <algorithm>
35 #include <bitset>
36 #include <complex>
37 #include <deque>
38 #include <exception>
39 #include <fstream>
40 #include <functional>
41 #include <iomanip>
42 #include <ios>
43 #include <iosfwd>
44 #include <iostream>
45 #include <istream>
46 #include <iterator>
47 #include <limits>
48 #include <list>
49 #include <locale>
50 #include <map>
51 #include <memory>
52 #include <new>
53 #include <numeric>
54 #include <ostream>
55 #include <queue>
56 #include <set>
57 #include <sstream>
58 #include <stack>
59 #include <stdexcept>
60 #include <streambuf>
61 #include <string>
62 #include <typeinfo>
63 #include <utility>
64 #include <valarray>
65 #include <vector>
66
67 #if __cplusplus >= 201103L
68 #include <array>
69 #include <atomic>
70 #include <chrono>
71 #include <condition_variable>
72 #include <forward_list>
73 #include <future>
74 #include <initializer_list>
75 #include <mutex>
76 #include <random>
77 #include <ratio>
78 #include <regex>
79 #include <scoped_allocator>
80 #include <system_error>
81 #include <thread>
82 #include <tuple>
83 #include <typeindex>
84 #include <type_traits>
85 #include <unordered_map>
86 #include <unordered_set>
87 #endif
View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/260.html
標籤：C++
上一篇：【C/C++編程筆記】掌握C++標準庫，您將成為更搶手的C++程式員
下一篇：【C++初級技能書】0.序