七段第三课：STL
这篇主要讲了STL中的MAP，SET，MULTISET，BITSET。
Map
定义
你可以理解成是一个下标可以为任意东西的数组。在 $\tt c++$ 中，你可以以如下方式定义一个 $\tt map$ ：
1
| map<typename _Key, typename _Tp>mp;
|
它你可以以如下格式访问它某一个值：
它表示，在 $\tt mp $ 的下标为 $\tt _Key$ 类型的 $x$ 位置存储着 $\tt _Tp$ 类型的 $y$ 。
使用
从某种意义上来讲，$\tt map$ 类型的 $\tt STL$ 可以被称为哈希表。因为它的前面的项没有限制，而之后的也没有限制（只要在对应数据类型范围内）而这一个工具的单次时间复杂度是优秀的 $O(\log n)$ 。
使用的话，除了定义和赋值，还可以以循环的方式查询，而 $\tt map$ 内部的排序默认是按照从小到大排序。（也就是说你可以自定义 $\tt map$ 的排序方式）
$\tt for$ 循环的写法如下：
1
2
3
4
5
6
|
map<int , int >mp;
map<int , int >::iterator *it;
for(it = mp.begin(); it != mp.end(); it++) {
}
|
因为这个变量 $\tt *it$ 其实是一个指针，而指针是没有大小之分，只能相等或不相等，所以，这里 $\tt for$ 的结束条件是 it != mp.end() 。
除此之外，想要知道一个 $\tt map$ 的指针的 $\tt _ Key$ 和 $\tt _Tp$ ，你可以使用 $\tt it.first$ 表示 $\tt _Key$ 的值，$\tt it.second$ 表示 $\tt _ Tp$ 的值。
例题
7段第三课 A - 水果店
题目传送门
显而易见的模拟题，有了上面的知识基础，一定都不难，直接上代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<bits/stdc++.h>
using namespace std;
int n;
map<string , map<string , int > >mp;
void Input() {
cin >> n;
string s, t;
int x;
for(int i = 1; i <= n; i++) {
cin >> s >> t >> x;
mp[t][s] += x;
}
}
void Work() {
for(auto &p : mp) {
cout << p.first << "\n";
for(auto &it : p) {
cout << " |----" << it.first << "(" << it.second << ")\n";
}
}
}
int main() {
ios::sync_with(0);
cin.tie(0), cout.tie(0);
Input();
Work();
return 0;
}
|
Set
接下来要介绍的是 $\tt STL$ 大家族里面的一个大东西 $\tt Set$ 。
定义
$\tt Set$ 顾名思义，就是集合，准确来讲是不可重集合（集合本来就不可重）。它是一个可以在 $O(\log n)$ 的单次时间复杂度做到对于集合内元素自动排序、去重的容器。
想要定义一个 $\tt Set$ 你可以使用如下代码：
它表示一个装着数据类型 $\tt _Key$ 的集合。
使用
这里介绍如下的几个函数：
1
2
3
4
5
6
7
8
9
10
11
12
| set<int >st;
st.insert(x);
st.size();
st.erase(x);
st.erase(*it);
st.find(x);
st.begin();
st.end();
st.lower_bound(x);
st.upper_bound(x);
|
例题
真不幸，没有呢 ~~
MultiSet
定义
这就是 $\tt Set$ 的扩展版本，被称为 $\tt MultiSet$ 可重集合。
定义方式和 $\tt Set $ 一样，记得把 $\tt Set$ 改成 $\tt MultiSet$ 。
1
| multiset<typename _Key>st;
|
表示定义一个装着数据类型 $\tt _Key$ 的集合 $\tt st$ 。
使用
和 $\tt Set$ 几乎一样
1
2
3
4
5
6
7
8
9
10
11
12
| set<int >st;
st.insert(x);
st.size();
st.erase(x);
st.erase(*it);
st.find(x);
st.begin();
st.end();
st.lower_bound(x);
st.upper_bound(x);
|
例题
7段第三课 B - SET
题目传送门
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include<bits/stdc++.h>
using namespace std;
int n;
multiset<int >st;
void Input() {
scanf("%d", &n);
}
void Work() {
string s;
int k;
for(int i = 1; i <= n; i++) {
cin >> s >> k;
if(s == "Push") {
st.insert(k);
}
else {
auto p = st.upper_bound(k);
if(p == st.begin()) {
printf("No Element!\n");
}
else {
p--;
printf("%d\n", *p);
st.erase(p);
}
}
}
}
int main() {
Input();
Work();
return 0;
}
|
BitSet
某些人就要说了，“这什么什么 $\tt bitset$ 不也是什么什么 $\tt set$ 吗，这肯定和 $\tt set$ 没什么区别罢。”
这就大错特错了，这玩意，和 $\tt set$ 关系是真的不大。
定义
使用如下定义定义一个长度为 $N$ 的 $\tt bitset$ 。
表示定义了一个长度为 $N$ 的 $\tt bitset$ 。
使用
$\tt bitset$ 其实本质上是一个 $\tt 01$ 字符集，他会在数字的地方标记为 $\tt 1$ ，没有的地方为 $\tt 0$ 。
1
2
3
4
5
6
7
8
| st.set();
st.reset();
st.flip();
st.set(x);
st.reset(x);
st.flip(x);
st.count();
|
例题
7段第三课 C - BITSET
题目传送门
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using namespace std;
int n;
bitset<1010>st[10010];
void Input() {
scanf("%d", &n);
int k;
for(int i = 1; i <= n; i++) {
scanf("%d", &k);
int a;
for(int j = 1; j <= k; j++) {
scanf("%d", &a);
st[a].set(i, true);
}
}
}
void Work() {
int Q;
scanf("%d", &Q);
int x, y;
while(Q--) {
scanf("%d%d", &x, &y);
if((st[x]&st[y]).any()) {
printf("Yes\n");
}
else {
printf("No\n");
}
}
}
int main() {
Input();
Work();
return 0;
}
|
综合例题
D - 【提高组】第三课：矩形切割
题目传送门
解题思路
模拟即可
题目代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include<bits/stdc++.h>
using namespace std;
int w, h, n;
set<long long >H, V;
multiset<long long >Hx, Vx;
void Input() {
scanf("%d%d%d", &w, &h, &n);
H.insert(0), H.insert(h), Hx.insert(h);
V.insert(0), V.insert(w), Vx.insert(w);
}
void Work() {
char ch;
int x;
while(n--) {
scanf(" %c %d", &ch, &x);
if(ch=='H') {
if(H.find(x) == H.end()) {
H.insert(x);
auto p = H.find(x);
auto l = --p; p++;
auto r = ++p; p--;
p = Hx.find(*r - *l);
Hx.erase(p);
Hx.insert(x - *l), Hx.insert((*r) - x);
}
}
else {
if(V.find(x) == V.end()) {
V.insert(x);
auto p = V.find(x);
auto l = --p; p++;
auto r = ++p; p--;
p = Vx.find(*r - *l);
Vx.erase(p);
Vx.insert(x - (*l)), Vx.insert((*r) - x);
}
}
auto x = Hx.end(); x--;
auto y = Vx.end(); y--;
printf("%lld\n", 1LL * (*x) * (*y));
}
}
int main() {
Input();
Work();
return 0;
}
|
