[NOIP2014]珠心算测试

题目描述

珠心算老师随机生成一个由 $n$ 个互不相同正整数组成的集合，问其中有多少个数恰好等于集合中另外两个（不同的）数之和。

输入格式：第一行一个整数 $n$ ；第二行 $n$ 个正整数，用空格隔开。输出格式：一个整数，表示答案。

样例输入：4 与 1 2 3 4；样例输出：2（由 $1+2=3$ 、 $1+3=4$ ；两个加数必须不同，故 $2+2=4$ 不算）。

数据范围： $3 \le n \le 100$ ，每个正整数不超过 $10000$ 。

思路

枚举所有两个不同数的组合（每个数只与它后面的数配对）把和收进一个集合，答案就是原集合与和集合的交集大小。注意统计的是"数"的个数而不是等式的个数，多个数对凑出同一个和只算一次。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-10-02 10:41
# update_at: 2026-10-02 10:41

import sys


def count_two_sum_numbers(nums: list[int]) -> int:
    """统计集合中能表示为另两个不同数之和的数的个数。"""
    numbers = set(nums)
    # 枚举所有“两个不同数”的组合求和；多个组合凑出同一个和只算一个目标值
    sums = {a + b for i, a in enumerate(nums) for b in nums[i + 1:]}
    return len(numbers & sums)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    nums = [next(data) for _ in range(n)]
    print(count_two_sum_numbers(nums))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
32
33
34
35
36
37
38
39/**
 * 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-10-06 15:14
 * update_at: 2026-10-06 15:14
 */

#include <cstdio>
#include <set>
using namespace std;

typedef long long ll;

const int MAXN = 105;

ll n;               // 集合中数的个数
ll a[MAXN];         // a[i] 表示集合里的第 i 个数（保证互不相同）
set<ll> sum_set;    // 收集所有“两个不同的数”的和，set 自动去重

int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);

    // 枚举无序组合：每个数只与它后面的数配对，天然保证两个加数不同
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            sum_set.insert(a[i] + a[j]);

    // 统计有多少个数落在和集合里；同一个数哪怕能凑出多次也只算一个
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        if (sum_set.count(a[i]) > 0)
            ans++;

    printf("%lld\n", ans);
    return 0;
}

[NOIP2014]珠心算测试

目录

题目描述

思路

参考代码