题解：SP20979 UCBINTC - Good

Fake_Cry · 2025-10-07 16:58:20 · 题解

题解：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)。

#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;
}