南的个人博客

遇事不决，但问春风

C++训练

发表于 更新于 分类于
C++

C++方法

类成员函数

类成员函数定义在外部时候，单独使用范围解析运算符 :: 来定义

[详细链接](C++ 类成员函数 | 菜鸟教程 (runoob.com))

image-20250226160051442

C++万能头文件

1
#include <bits/stdc++.h>

STL

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
vector,变长数组，倍增的思想
	size() 返回元素个数
	empty() 判断是否为空
	clear() 清空
	front()/back() 
	push_back()/pop_back()
	begin()/end();
	支持比较运算
	
	
pair<int,int> 存储一个二元组
	first，第一个元素
	second，第二个元素
	支持比较运算，以first为第一关键字，以second为第二关键字（字典排序）
	可以使用pair<int,pair<int,string>> 存储三个数

string，字符串，
	substr(a,b), 返回从a开始，返回b个字符
	c_str() 返回起始地址
	size()/length()
	empty()
	clear()
	
	
queue，队列 ， queue<int> q
	size()
	empty()
	push(), 队尾插入一个元素
	front(),返回队头元素
	back(),返回队尾元素
	pop()， 弹出队头元素
	
	
priority_queue,优先队列，默认是大根堆 priority_queue<int> heap
	push(),插入一个元素
	top(), 返回堆顶元素
	pop(); 弹出堆顶元素
	
	
stack，栈，
	size()
	empty()
	push(), 栈顶插入一个元素
	top(),	返回栈顶元素
	pop()	弹出栈顶元素
	
	
deque,双端队列,deque<int> q 效率低
	size() 返回元素个数
	empty() 判断是否为空
	clear() 清空
	front()/back() 
	push_back()/pop_back()
	push_front()/pop_front()
	begin()/end()
	
set,map,multiset,multimap,基于平衡二叉树（红黑树），动态维护有序序列
	size()
	empty()
	clear()
	begin()/end() 
	
	set/multiset set中没有重复的数，mul可以有重复的数
		insert() 插入一个数
		find() 查找一个数
		count() 返回某一个数的个数
		erase()
			(1) 输入是一个数x，删除所有x   O(k + logn)
			(2) 输入一个迭代器，删除这个迭代器
		lower_bound()/upper_bound()
			lower_bound(x) 返回大于等于x的最小的数的迭代器
			upper_bound(x) 返回大于x的最小的数的迭代器
	map/multimap
		insert()  插入的数是一个pair
		erase()  输入的参数是pair或者迭代器
		find()
		可以像数组一样用map
		lower_bound()/upper_bound()
		
		
unordered_set,unordered_map,unordered_multiset,unordered_multimap,哈希表
	和上面类似，增删改查时间复杂度是 O(1)
	不支持lower_bound()/upper_bound()
	
	
bitset,压位
	bitset<10000> S;
	~,&,|,^
	>>, <<
	==, !=
	
	count() 返回有多少个1
	any() 判断是否至少有一个1
	none() 判断是否全是0
	
	set() 把所有位置变为1
	set(k,v) 将第k位变成v
	reset() 把所有位变为0
	flip() 等价于~
	flip(k) 把第k位取反

代码

快排

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+10;

// 快速排序-基于分治算法

int n;
int q[N];

// 划分算法
int partition(int a[], int l ,int r){
    int mid;
    while(l < r){
        mid = a[l];
        while(a[r] >= mid && l < r) r--;
        a[l] = a[r];
        while(a[l] < mid && l < r) l++;
        a[r] = a[l];
    }

    a[l] = mid;
    
    
    return l;
}

void Qsort(int a[], int l, int r){
    if(l < r){
        int mid = partition(a,l,r);
        Qsort(a,l,mid-1);
        Qsort(a,mid+1,r);
    }
    return ;
}

int main(){

    cin >> n;
    for(int i =  0; i < n; i++) cin >> q[i];

    Qsort(q,0,n-1);
    for(int i = 0;i < n;i ++) cout << q[i];
    
    return 0;
}

归并排序

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+10;

int n;
int q[N];
int b[N]; // 辅助数组

// 归并排序
void merge(int a[],int l, int mid, int r){
    // 进入该函数时，l-mid有序，mid-r有序，将这两个部分合并即可
    for(int h = l ;h <= r ; h ++) b[h] = a[h];
    
    int i,j,k;
    for( i = l , j = mid+1,k = l ; i <= mid && j <= r ; k++){
        if(b[i] <= b[j]) a[k] = b[i ++];
        else a[k] = b[j ++];
    }


    while(i <= mid) a[k++] = b[i ++];
    while(j <= r) a[k ++] = b[j ++];

}

void merge_sort(int a[],int l,int r){
    if(l< r){
        int mid = l + r >> 1;
        merge_sort(a,l, mid);
        merge_sort(a,mid+1,r);
        merge(a,l,mid,r);
    }
}


int main(){

    cin >> n;
    for( int i = 0 ;i < n;i ++) cin >> q[i];

    merge_sort(q,0,n-1);

    for(int i = 0 ;i < n; i++) cout << q[i] << " ";


    return 0;
}

二分

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;

const int N = 1e6 + 10;

int n,m;
int q[N];

int main(){

    cin >> n >> m;
    for(int i = 0 ;i < n;i ++) cin >> q[i];

    while( m --){
        int x;
        cin >> x;

        int l = 0 , r = n -1;
        while(l < r){ // 左边界
            int mid = l + r >> 1;
            if(q[mid] >= x) r = mid;
            else l = mid + 1;
        }

        if(q[l] != x) cout << "不存在" << endl;
        else{
            cout << 1 << " " << endl;

            int l = 0 , r = n - 1;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(q[mid] <= x) l = mid;
                else r = mid - 1;
            }
        }
    }

}

单调栈

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
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
int skt[N],tt;
int n;

int main()
{
    cin >> n;

    for(int i = 0 ;i < n;i ++)
    {
        int x;
        cin >> x;
        while(tt && skt[tt] >= x) tt --;
        if(tt) cout << skt[tt] << " ";
        else cout << "-1 ";

        skt[ ++ tt] = x;
    }

    return 0;
}

单链表

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

//head 表示头节点所在下标
// e 表示当前节点的值，该数组所存储的值并不具有先后特性，链表的先后依据ne来判断
// ne 表示当前节点的下一个节点的位置
// idx 存储当前已经用到了哪个点
int head, e[N],ne[N] , idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 将x插入到头节点
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx ++;
}

// 将x插入到下标是k节点后面
void add_to_k(int x,int k)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

// 将下标是k的点后面的点删除
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int m,x;
char op;


int main()
{
    cin >> m;
    init();
    while(m --)
    {
        cin >> op;
        if(op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if(op == 'D')
        {
            cin >> x;
            if(!x) head = ne[head]; // x 为 0时，删除头节点
            remove(x-1);
        }
        else if(op == 'I')
        {
            int k;
            cin >> k;
            cin >> x;
            add_to_k(x,k-1);
            
        }
    }

    for(int i = head; i != -1 ; i = ne[i]) cout << e[i] << " ";

    cout << endl;

    return 0;
}

滑动窗口

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n,k;
int a[N],q[N]; // a 存放数组元素， q表示队列，队列存放的是元素i在数组a中的下标



int main()
{
    cin >> n >> k;
    for(int i = 0 ; i < n;i ++) cin >> a[i];
    int hh = 0,tt = -1;

    for(int i = 0 ;i < n;i ++)
    {
        // 判断队头是否滑出窗口
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        while(hh <= tt && a[q[tt]] >= a[i]) tt --;

        q[ ++ tt] = i;

        if(i >= k -1 ) cout << a[q[hh]] <<" ";
    }

    cout << ' ';
    cout << endl;
    hh = 0 , tt = -1;
    for(int i = 0 ;i < n;i ++)
    {
        // 判断队头是否滑出窗口
        if(hh <= tt && i - k + 1 > q[hh]) hh ++;
        while(hh <= tt && a[q[tt]] <= a[i]) tt --;

        q[ ++ tt] = i;

        if(i >= k -1 ) cout << a[q[hh]] <<" ";
    }

    cout << ' ';

    return 0;
}

KMP

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
#include <bits/stdc++.h>

using namespace std;

const int N = 10010,M = 100010;

int n,m;
char p[N],s[M];
int ne[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;

    for(int i = 2 , j = 0 ; i <= n ;i ++)
    {
        while(j && p[i] != p[i + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }

    for(int i = 1 ,j = 0 ;i <= m ;i ++)
    {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j ++;
        if(j == n)
        {
            // 匹配成功
            cout << i -n << " ";
            j = ne[j];
        }

    }

    return 0;
}

模拟散列表

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
#include <bits/stdc++.h>

using namespace std;

const int N = 100003;

int h[N],e[N],ne[N],idx;

void insert(int x)
{
    int k = (x % N + N) % N;
    
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++;
}

bool find(int x)
{
    int k = (x % N + N) % N;
    for(int i = h[k]; i != -1; i = ne[i])
        if(e[i] == x)
            return true;
    
    return false;
}

int main()
{

    int n;
    cin >> n;
    memset(h,-1,sizeof h); // 清空指针

    while(n --)
    {
        char op[2];
        int x;
        cin >> op >> x;

        if(op[0] == 'I') insert(x);
        else 
        {
            if(find(x)) cout << "Yes"<< endl;
            else cout << "No" << endl;
        }
    }

    return 0;
}

模拟散列表（开放寻址）

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
#include <bits/stdc++.h>

using namespace std;

const int N = 200003;
const int null = 0x3f3f3f3f;

int h[N];



// 若x在表中，则返回x位置；反之，返回x应该在的位置
int find(int x)
{
    int k = (x % N + N) % N;

    while(h[k] != null && h[k] != x)
    {
        k ++;
        if(k == N) k = 0;
    }

    return k;

}

int main()
{

    int n;
    cin >> n;
    memset(h,0x3f,sizeof h); // 清空指针

    while(n --)
    {
        char op[2];
        int x;
        cin >> op >> x;
        
        int k = find(x);
        if(op[0] == 'I') h[k] = x;
        else 
        {
            if(h[k] != null) cout << "Yes"<< endl;
            else cout << "No" << endl;
        }
    }

    return 0;
}

字符串哈希

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
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ULL;

const int N = 10010,P = 131;

int n,m;
char str[N];
ULL h[N],p[N]; // h表示某一个前缀的哈希值 p表示当前位置p进制的数

ULL get(int l ,int r)
{
    return h[r] - h[l-1] * p[r-l + 1];
}

int main()
{
    cin >> n >> m >> str + 1;

    p[0] = 1;

    for(int i = 1 ;i <= n;i ++)
    {
        p[i] = p[i-1] * P ;
        h[i] = h[i - 1] * P + str[i];
    }

    while(m --)
    {
        int l1,r1,l2,r2;
        cin >> l1 >> r1 >> l2 >> r2;

        if(get(l1,r1) == get(l2,r2)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    

    return 0;
}

Tire

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
52
53
#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int son[N][26],cnt[N],idx;//下标是0的点，既是根节点，又是空节点
char str[N];

// 插入操作
void insert(char str[])
{
    int p = 0;
    for(int i = 0 ;str[i];i ++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];

    }
    cnt[p] ++;

}

// 查询操作
int query(char str[])
{
    int p = 0;
    for(int i = 0 ; str[i];i ++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n;
    cin >> n;

    while(n --)
    {
        char op[2];
        cin >> op >> str;
        if(op[0] == 'I') insert(str);
        else cout << query(str) << endl;
    }

    return 0;
}

并查集

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;

const int N = 10010;

int n,m;
int p[N],size[N];

// 返回x的祖宗节点 + 路径压缩
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{

    cin >> n >> m;

    for(int i = 0 ;i < n;i ++) p[i] = i;

    while(m --)
    {
        char op[5];
        int a,b;
        cin >> op >> a >> b;

        if(op[0] == 'M') p[find(a)] = find(b);
        else 
        {
            if(find(a) == find(b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }

    return 0;
}

区间合并

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
52
53
54
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N = 100010;

int n;
vector<PII> segs;

void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(),segs.end());

    int st = -2e9, ed = -2e9;
    for(auto seg : segs)
    {
        if(ed < seg.first) // 如果左端点小于维护的右端点，表明维护的区间段已经结束，更改维护的区间
        {
            if(st != -2e9) res.push_back({st,ed});
            st = seg.first,ed = seg.second;
        }
        else
        {
            ed = max(ed,seg.second);
            // st = min(st,seg.first);  按照first从左到右进行便利，不会出现这种情况
        }
    }

    if(st != -2e9) res.push_back({st,ed});

    segs = res;
}

int main()
{
    cin >> n;

    for(int i = 0 ;i < n ;i ++)
    {
        int l,r;
        cin >> l >> r;
        segs.push_back({l,r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;
}

区间化

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>

using namespace std;

const int N = 300010;

typedef pair<int,int> PII;

int n,m;
int a[N],s[N];

// 存储的离散化的值
vector<int> alls;
vector<PII> add,query;

// 二分寻找x所在alls中的位置
int find(int x)
{
    int l = 0 , r = alls.size() - 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return r + 1;
}

int main()
{
    cin >> n >> m;

    for(int i = 0 ;i < n;i ++)
    {
        int x,c;
        cin >> x >> c;
        add.push_back({x,c});

        alls.push_back(x);
    }

    for(int i = 0 ;i < m;i ++)
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l,r});

        alls.push_back(l);
        alls.push_back(r);
    }

    // 去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    // 处理插入
    for(auto item : add)
    {
        int x = find(item.first);
        a[x] += item.second;
    }

    // 预处理前缀和
    for( int i = 1 ;i <= alls.size() ;i ++)
    {
        s[i] = s[i - 1] + a[i];
    }

    //处理询问
    for(auto item : query)
    {
        int l = find(item.first);
        int r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

连通块的数量

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
#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int n,m;
int p[N],size[N];

// 返回x的祖宗节点 + 路径压缩
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{

    cin >> n >> m;

    for(int i = 0 ;i < n;i ++) p[i] = i ,size[i] = 1;

    while(m --)
    {
        char op[5];
        int a,b;
        cin >> op ;

        if(op[0] == 'C'){
            cin >> a >> b;
            if(find(a) == find(b)) continue;
            size[find(b)] += size[find(a)];
            p[find(a)] = find(b);
        } 
        else if(op[1] == '1')
        {
            cin >> a >> b;
            if(find(a) == find(b)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        else 
        {
            cin >> a;
            cout <<  size[find(a)] << endl;
        }
    }

    return 0;
}

最长连续不重复子序列

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
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n;
int a[N],s[N];

// 最长连续不重复子序列
int main()
{

    cin >> n;
    for(int i = 0 ;i < n;i ++) cin >> a[i];

    int res = 0;

    for(int i = 0,j = 0 ;i < n; i ++)
    {
        s[a[i]]++;
        while(s[a[i]] > 1)
        {
            s[a[j]] --;
            j ++;
        }

        res = max(res,i - j + 1);
    }

    cout << res << endl;

    return 0;
}

堆

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;

const int N = 10010;

int n,m;
int h[N],size;

void down(int u)
{
    int t = u;
    if(u*2 <= size && h[u*2] < h[t]) t = u*2;
    if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u* 2 + 1;
    if(u != t)
    {
        swap(h[u],h[t]);
        down(t);
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1 ;i <= n;i ++) cin >> h[i];
    size = n;

    for(int i = n / 2 ;i ;i --) down(i);

    while(m --)
    {
        cout << h[1] << " ";
        h[1] = h[size];
        size --;
        down(1);
    }


    return 0;
}

DFS

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
#include <bits/stdc++.h>

using namespace std;

const int N = 10;

int n;
int path[N];
bool visited[N];

void dfs(int u)
{
    if(u == n)
    {
        for(int i = 0 ;i < n; i ++) cout << path[i] <<" ";
        cout << endl;
        return;
    }

    for(int i = 1 ;i <= n;i ++)
    {
        if(!visited[i])
        {
            path[u] = i;
            visited[i] = true;
            dfs(u+1);
            visited[i] = false;
        }
    }

}


// 全排列
int main()
{
    cin >> n;
    dfs(0);
    return 0;
}