题解：SP20979 UCBINTC - Good

题意简述

给定一个由

N

个整数构成的序列

A

，求满足

A_i =A_x + A_y + A_z

且

z ≤y≤x<i

的

i

个数。

思路

使用哈希集合 unordered_set 来优化查找过程，其中：

p：存储已经遍历过的元素
q：存储所有两数之和（来自已遍历元素）

对于每个

A_i

，检查是否存在

x \in \text{p}

使得

A_i - x \in \text{q}

。如果存在，则

A_i

是好元素。最后更新数据结构，将

A_i

加入 p，将

A_i

与 p 中所有元素的和加入 q。

代码实现

时间复杂度：

O(N^2)

。

CPP

#include<bits/stdc++.h>
using namespace std;
signed main()
{
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	unordered_set<int> p, q;
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		//检查 a[i] 是否是好元素
		for (auto x : p) {
			if (q.count(a[i] - x)) {
				cnt++;
				break;
			}
		}
		//更新数据结构
		p.insert(a[i]);
		for (auto y : p) {
			q.insert(a[i] + y);
		}
	}
	cout << cnt;
	return 0;
}

题解：SP20979 UCBINTC - Good

文章操作

题解：SP20979 UCBINTC - Good

题意简述

思路

代码实现

相关推荐

评论

题解：SP20979 UCBINTC - Good