[NOIP 2014 普及组] 珠心算测验

题意

给出 n 个互不相同的正整数，问其中有多少个数可以表示成集合中另外两个不同数的和。

思路

n <= 100，可以直接枚举两个加数。

先把所有数放进集合 values，这样可以快速判断一个和是否出现在原集合中。

枚举所有 i < j 的数对，计算：

text

1total = numbers[i] + numbers[j]

如果 total 在 values 中，说明这个数满足要求。因为同一个目标数可能由多组加数得到，所以用集合 can_be_sum 保存满足条件的目标数，最后输出集合大小。

这题是点对枚举和集合判重练习，不创建额外 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：使用 list(map(int, input().split())) 读取数组。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：for i in range(n) 和 for j in range(i + 1, n) 枚举无序点对。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：set 适合做成员判断和去重。
total in values 判断和是否存在，can_be_sum.add(total) 避免重复计数。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13n = int(input())
numbers = list(map(int, input().split()))
values = set(numbers)

can_be_sum = set()

for i in range(n):
    for j in range(i + 1, n):
        total = numbers[i] + numbers[j]
        if total in values:
            can_be_sum.add(total)

print(len(can_be_sum))

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

int a[105];        // 原数组
bool exist[20005]; // exist[sum] = true 表示 sum 可以由两个不同数相加得到
int n, ans;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    // 枚举所有 i < j 的数对
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            exist[a[i] + a[j]] = true;
        }
    }
    // 统计哪些数在 exist 中
    for (int i = 1; i <= n; i++) {
        if (exist[a[i]]) ans++;
    }
    cout << ans;
    return 0;
}

Pythonic 写法

集合推导：

python

1
2
3
4n = int(input())
a = list(map(int, input().split()))
s = set(a)
print(len({a[i] + a[j] for i in range(n) for j in range(i + 1, n) if a[i] + a[j] in s}))

复杂度

枚举数对需要 $O(n^2)$ 次，集合查询均摊 $O(1)$ 。空间复杂度是 $O(n)$ 。

总结

这题不能统计“有多少种加法”，而是统计“有多少个数能被表示”。用集合保存答案，可以自然避免重复。

[NOIP 2014 普及组] 珠心算测验

目录

题意

思路

Python 知识

代码

Pythonic 写法

复杂度

总结