Czj's Blog

第五讲-数据结构与字符串

发表于 更新于 分类于 ，
本文字数： 9.9k 阅读时长 ≈ 9 分钟

作业链接

[蓝桥杯] 第五讲：数据结构与字符串 - 题单 - 洛谷 | 计算机科学教育新生态

AC 代码

P3367 【模板】并查集 - 洛谷

集合的合并与查询，无法从集合中删除元素。

fa[i] = j 表示 i 的祖先节点为 j，对于任意节点 x，若 fa[x] 相同则说明这些 x 属于同一个集合。

采用路径压缩写法的 find()，每次调用的复杂度可以认为是均摊的 \(O(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
26
27
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+9;
int n,m,z,fa[N],a,b;
// 路径压缩
int find(int x)
{
    if(x!=fa[x]) fa[x] = find(fa[x]); // 让所有节点直接指向祖先节点
    return fa[x];
}
int main()
{
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=n;i++) fa[i] = i;
    while(m--)
    {
        cin>>z>>a>>b;
        if(z==1) fa[find(a)] = find(b);
        else
        {
            if(find(a)==find(b)) cout<<"Y"<<endl;
            else cout<<"N"<<endl;
        }
    }
    return 0;
}

P8686 [蓝桥杯 2019 省 A] 修改数组 - 洛谷

题目中要求的将重复出现的数字不断 +1 直到未出现过，暴力做法的复杂度为 \(O(n)\)，但使用并查集的思想：认为相同元素为一个集合，每次将需要修改的元素赋值为祖先节点即可，复杂度为 \(O(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
26
27
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1e5 + 9;
int p[N], a[N];

int find(int x) {
	if (p[x] != x) {
		p[x] = find(p[x]);
	}
	return p[x];
}

int main() {
	cin >> n;

	for (int i = 0; i < N; i++)p[i] = i;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i] = find(a[i]);
		p[a[i]] = a[i] + 1;
	}
	for (int i = 0; i < n; i++) {
		cout << a[i] << ' ';
	}
	return 0;
}

P1168 中位数 - 洛谷

本题为堆的应用：对顶堆求中位数（第(n/2)小元素）

顾名思义，对顶堆中使用大小根堆构成对顶的结构

对于大根堆，可以视为一个上窄下宽的金字塔，塔尖是最大的元素 对于小根堆，可以视为一个下窄上宽的金字塔，塔尖是最小的元素 将小根堆叠在大根堆上，就形成了对顶堆（上大下小）

简单比较两个堆的堆顶可知：当小根堆的堆顶大于大根堆的堆顶时，小根堆的所有元素都大于大根堆的所有元素。因此只需要保证大根堆的大小为 k，并且大根堆的堆顶始终小于小根堆的堆顶，即可以通过大根堆的堆顶求出第 k 小的元素了。

在保持堆的性质时向堆中插入元素的复杂度为 \(O(logn)\)，查询堆顶的复杂度 \(O(1)\)，本题中需要插入 \(n\) 个数字，总的复杂度为 \(O(nlogn)\)。

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
#include <bits/stdc++.h>
using namespace std;
int n, x;
priority_queue<int> big;
priority_queue<int, vector<int>, greater<int>> small;

int main() {
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		small.push(x);
		//保证大根堆中有 i/2 个元素
		while (big.size() <= (i / 2)) {
			x = small.top();
			small.pop();
			big.push(x);
		}
		//调整大小至小根堆的顶不小于大根堆的顶
		while (big.size() && small.size() && big.top() > small.top()) {
			int a = big.top(), b = small.top();
			big.pop(), small.pop();
			big.push(b), small.push(a);
		}

		if (i & 1) {
			//第奇数个
			cout << big.top() << '\n';
		}
	}
	return 0;
}

P8755 [蓝桥杯 2021 省 AB2] 负载均衡 - 洛谷

首先可以想到为每台计算机用一个数组维护其得到的任务，然后根据时序模拟判断是否可以释放被占用的资源，但这样就需要 \(O(n)\) 的复杂度来寻找可以释放的资源。每个时刻都需要检查所有计算机，总的时间复杂度为 \(O(nm)\) 再观察题目发现，输入的数据是按时间单调变化的，因此我们可以改用堆来维护每台计算机分到的任务，每次只需要检查堆顶即可找到最可能结束的任务，复杂度降低为 \(O(mlogn)\)。

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;
int n, m;
const int N = 2e5+9;
int v[N]; // 每个电脑可用的资源
struct inf {
	int time, val; // 时刻，资源量
	// 重载运算符
	bool operator>(const inf &other) const {
		return time > other.time;
	}
};
// 由于本题给出保证时间是递增的，可以用小根堆维护需要返还的资源
priority_queue<inf, vector<inf>, greater<inf>> q[N];
int a, b, c, d, now;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	while (m--) {
		cin >> a >> b >> c >> d;
		// 检查当前机器是否有可以返还的资源
		while (q[b].size()) {
			auto t = q[b].top();
			if (t.time <= a) {
				v[b] += t.val;
				q[b].pop();
			} else break;
		}
		if (v[b] >= d) {
			v[b] -= d;
			cout << v[b] << endl;
			q[b].push({a + c, d});
		} else {
			cout << -1 << endl;
		}
	}
	return 0;
}

P3374 【模板】树状数组 1 - 洛谷

通过 lowbit 操作，可以在 \(log\) 的复杂度内得到区间和

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
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
const int N = 5e5 + 9;
int tr[N], n, m, k, a, b, x;

void add(int st, int k) {
	for (int i = st; i <= n; i += lowbit(i)) {
		tr[i] += k;
	}
}

int sum(int st) {
	int ans = 0;
	for (int i = st; i >= 1; i -= lowbit(i)) {
		ans += tr[i];
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		add(i, x);
	}
	while (m--) {
		cin >> k >> a >> b;
		if (k == 1) {
			add(a, b);
		} else cout << sum(b) - sum(a - 1) << endl;
	}
	return 0;
}

P8613 [蓝桥杯 2014 省 B] 小朋友排队 - 洛谷

通过树状数组可以实现动态前缀和

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;
#define lowbit(x) ((x)&(-x))
//用树状数组的 动态修改 特性来实现从前往后看和从后往前看
const int N = 1e6 + 9;
//这里的tr[x] = y表示身高为x的小朋友出现了y次
int tr[N], h[N], n;
typedef long long ll;
ll ans, sum[N];
ll query(int x) {
	int res = 0;
	//从当前值往前检查，看其前面有多少个数
	for (int i = x; i; i -= lowbit(i)) {
		res += tr[i];
	}
	return res;
}
//增加要从当前位置向后传递贡献
void add(int x) {
	for (int i = x; i <= N; i += lowbit(i)) tr[i]++;
}

int main() {
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> h[i], h[i]++;//h[i]可能是0，又lowbit(0) = 0，因此出现0会死循环
	//从前向后遍历，记录第i个小朋友 之前 有多少人比他高
	for (int i = 0; i < n; i++) {
		sum[i] = query(N) - query(h[i]);//用前缀和的思想找到比h[i]大的数的个数

		//把这个数加到其中，这个顺序保证了每个数在求sum[i]的时候，只关注了在其前面的那些数
		add(h[i]);
	}
	//清空树状数组
	memset(tr, 0, sizeof tr);
	//从后向前遍历，记录第i个小朋友 之后 有多少人比他矮
	for (int i = n - 1; i >= 0; i--) {
		sum[i] += query(h[i] - 1);//直接查询[0,h[i]-1]的之间的人数
		//照例加进去，让这个人影响之前的人
		add(h[i]);
	}
	//此时sum中保存的就是 第i个小朋友前面比他高的人数加上后面比他矮的人数，由冒泡排序可知，这个值就是最小的交换次数
	for (int i = 0; i < n; i++) {
		ans += sum[i] * (sum[i] + 1) / 2;//10^5相乘会超过int
	}
	cout << ans << 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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// 归并排序求逆序对
ll x, n, ans;
const int N = 1e5+9;
struct node {
	ll h, w;
} a[N], tmp[N];

void merge_sort(node *q, int l, int r) {// l 和 r 都是可以取到的
	if (l >= r)return; // 只剩下一个数字了，自然有序
	int mid = (l + r) >> 1;
	merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r) {
		if (q[i].h <= q[j].h) {
			q[i].w += j - (mid + 1); // 贡献交换次数
			tmp[k++] = q[i++];
		} else {
			q[j].w +=  (mid + 1) - i;
			tmp[k++] = q[j++];
		}
	}
	// 下述 while 只有一个会成立
	/*
	先放右边的。
	因为如果有右边的还没放，说明左边的已经放好了，
	并且右边的大于左边的，由于原先就在右边，因此不会产生逆序贡献
	*/
	while (j <= r)tmp[k++] = q[j++];
	// 如果该 while 执行，说明左边有大的，其逆序了，会产生贡献
	while (i <= mid) {
		q[i].w += j - (mid + 1);
		tmp[k++] = q[i++];
	}
	// 放回原位
	for (int i = l, j = 0; j < k; i++, j++) {
		q[i] = tmp[j];
	}
	return ;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		a[i] = {x, 0};
	}
	// 传地址
	merge_sort(a, 0, n - 1);
	for (int i = 0; i < n; i++) {
//		cout << a[i].w << " " << ans << endl;
		ans += a[i].w*(a[i].w + 1) / 2;
	}
	cout << ans;
	return 0;
}

P3372 【模板】线段树 1 - 洛谷

线段树是一种节点中保存区间信息的树，可以做到 \(log\) 复杂度的区间操作

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
#include <bits/stdc++.h>
using namespace std;
/*
  区间修改，区间查询
 */
const int N = 1e5 + 9;
typedef long long ll;
struct node {
	int l, r;
	ll sum;
	int lazy;//懒标记相当于记账，把原本应该下传的更新先存起来，之后再操作


} tr[N * 4];
ll w[N];
ll n, m, k, op, x, y;

void pushup(int u) {
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u) {
	if (tr[u].lazy) {
		//左子树
		tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].lazy;
		tr[u << 1].lazy += tr[u].lazy;
		//右子树
		tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].lazy;
		tr[u << 1 | 1].lazy += tr[u].lazy;
		//清除父节点的lazy
		tr[u].lazy = 0;
	}
}

void build(int u, int l, int r) {
	if (l == r) tr[u] = {l, r, w[l], 0};
	else {
		tr[u] = {l, r};//默认初始lazy为0，因此不赋值也行
		int mid = (l + r ) >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
}

void update(int u, int x, int y, int k) {
	if (tr[u].l >= x && tr[u].r <= y) {
		//该节点完全在更新的区间里
		tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
		tr[u].lazy += k;//更新懒标记
		return ;
	}
	//当前节点比更新区间更宽，则要分裂到左右子树中继续更新
	int mid = (tr[u].l + tr[u].r) >> 1;
	pushdown(u);//将父节点的懒标记下传
	//mid是下取整
	if (x <= mid) update(u << 1, x, y, k);
	if (y > mid) update(u << 1 | 1, x, y, k);
	pushup(u);
}

ll query(int u, int x, int y) {
	if (x <= tr[u].l && tr[u].r <= y) {
		return tr[u].sum;
	}
	int mid = (tr[u].l + tr[u].r) >> 1;
	pushdown(u);//先更新可能存在的懒标记，避免下面查询时出错

	ll sum = 0;
	if (x <= mid) sum += query(u << 1, x, y);
	if (y > mid) sum += query(u << 1 | 1, x, y);

	return sum;
}



int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> w[i];
	build(1, 1, n);
	while (m--) {
		cin >> op;
		if (op == 1) {
			cin >> x >> y >> k;
			update(1, x, y, k);
		} else {
			cin >> x >> y;
			cout << query(1, x, y) << endl;
		}
	}
	return 0;
}

P3375 【模板】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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+9;
char s[N],p[N];
int ne[N];
int main()
{
    cin.tie(0);
    cout.tie(0);
    cin>>s+1>>p+1;
    int plen = 1;
    //用字符串p生成ne数组
    for(int i =2 ,j = 0;p[i];i++)
    {
        while(j&&p[i] != p[j+1]) j = ne[j];
        if(p[i]==p[j+1]) j++;
        ne[i] = j;
        plen++;
    }
    //kmp搜索
    for(int i = 1,j = 0;s[i];i++)
    {
        while(j&& s[i] != p[j+1]) j = ne[j];//配对失败
        if(s[i]==p[j+1]) j++;//配对成功
        if(j==plen)//如果模式串p匹配完成
        {
            cout<<i-j+1<<endl;
            j = ne[j];
        }
    }
    for(int i = 1;p[i];i++) cout<<ne[i]<<" ";
    return 0;
}

P3370 【模板】字符串哈希 - 洛谷

手写哈希函数

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
#include <bits/stdc++.h>
using namespace std;
int n, ans;
string s;
const int N = 1e4 + 9;
typedef unsigned long long ull;
ull base = 131;
ull a[N];
int hs(string s) {
	ull ans = 0;
	for (int i = 0; i < s.size(); i++) {
		ans = ans * base + (s[i] - '0');
	}
	return ans;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		a[i] = hs(s);
	}
	sort(a, a + n);
	for (int i = 0; i < n - 1; i++) {
		if (a[i] == a[i + 1])continue;
		ans++;
	}
	cout << ans + 1;
	return 0;
}

P8630 [蓝桥杯 2015 国 B] 密文搜索 - 洛谷

使用 unordered_map 这个 STL 的模板，可以便捷地实现对字符串的哈希

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
// 密码是被打乱的，排序复原
unordered_map<string, int> mp;
string s, str;
int n, ans;
int main() {
	cin >> str >> n;
	while (n--) {
		cin >> s;
		sort(s.begin(), s.end());
		mp[s]++; // 排序后计数
	}
	// 密码的长度为 8 位
	for (int i = 0; i < (int)str.size() - 8; i++) {
		string tmp = str.substr(i, 8); // 从第 i 位往后取长度为 8 的子串
		// 资料不能直接排序，每次切出来后排序是为了与密码对比
		sort(tmp.begin(), tmp.end());
		ans += mp[tmp];
	}
	cout << ans;
	return 0;
}