题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？

最近老师出了一些测验题，请你帮忙求出答案。

输入格式

共两行，第一行包含一个整数 nn，表示测试题中给出的正整数个数。

第二行有 nn 个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。

输出格式

一个整数，表示测验题答案。

输入输出样例

输入               输出
4
1 2 3 4            2

说明/提示

【样例说明】

由 1+2=3,1+3=4，故满足测试要求的答案为 2。

注意，加数和被加数必须是集合中的两个不同的数。

【数据说明】

对于 100% 的数据，3≤n≤100 ，测验题给出的正整数大小不超过 10,000。

这段代码解决了一个问题：给定一个数集，求出能通过两两相加得到的数在原集合中出现了几次。

#include<iostream>
#include<cstdio>
using namespace std;
const int M=20005;
int t[M],g[M];
int n,a[105],ans,maxn;
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
	{
        cin>>a[i];
        g[a[i]]=1;
    }
    for (int i=1;i<n;i++)
	{
        for (int j=i+1;j<=n;j++)
		{
            t[a[i]+a[j]]++;
            maxn=max(maxn,a[i]+a[j]);
        }
    }
    for (int i=1;i<=maxn;i++)
	{
        if (t[i]>0&&g[i]==1) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

代码功能概述：

1. 输入：给定 n 个数的集合 a。
2. 目标：找到所有可以通过集合中两个不同的数相加得到的值，且这些值必须也出现在原集合中。输出这样的值的个数。
3. 输出：输出满足条件的数的个数。

变量解释：

• const int M=20005;：声明了大小为 20005 的数组，这个大小是由于集合中的数最大为 10000（题目中给出的限制），并且两个数相加后最大值不会超过 10000 + 10000 = 20000，因此需要开一个 20005 大小的数组。
• t[M]：用于记录两个数相加得到的某个数在集合中出现的次数，类似于“桶”的作用。
• g[M]：用于标记某个数是否在原集合中。g[i] = 1 表示值为 i 的数存在于集合中，g[i] = 0 表示不存在。
• a[105]：存储输入的数，最大允许 100 个数，因此数组大小为 105。
• ans：用于统计符合要求的数的个数。
• maxn：记录通过两数相加得到的最大值，减少后续的无效遍历。

代码流程详细解析：

输入处理：

cin >> n;
for (int i = 1; i <= n; i++) {
    cin >> a[i];
    g[a[i]] = 1; // 在集合中的数标记为 1
}

读入 n 个数，并将这些数存入数组 a 中。

同时在 g 数组中，将每个输入的数 a[i] 对应的下标位置 g[a[i]] 标记为 1，表示该数存在于集合中。

枚举所有两两相加的数

for (int i = 1; i < n; i++) {
    for (int j = i + 1; j <= n; j++) {
        t[a[i] + a[j]]++;  // 记录两个数相加的结果
        maxn = max(maxn, a[i] + a[j]);  // 记录最大相加结果
    }
}

使用两个循环枚举所有两个数的组合 (a[i], a[j])，将这两个数相加得到的结果 a[i] + a[j] 记录在数组 t 中。t[x]++ 表示值为 x 的数可以通过集合中的两个数相加得到。同时更新 maxn 记录相加结果的最大值，以减少后续的遍历范围。

统计符合要求的数：

for (int i = 1; i <= maxn; i++) {
    if (t[i] > 0 && g[i]) ans++;  // 如果值 i 被加出来并且它也在集合中，则计数
}

遍历 1 到 maxn，如果 t[i] > 0（即有两个数相加等于 i），并且 g[i] == 1（即该值 i 也在原集合中），则计数 ans++。

输出结果：

cout << ans << endl;

示例说明：

假设输入：

复制代码5
1 2 3 4 5

1. 集合：a = {1, 2, 3, 4, 5}，g 数组中 g[1] = 1, g[2] = 1, … g[5] = 1。
2. 枚举所有两两相加的结果：
   • 1 + 2 = 3，1 + 3 = 4，1 + 4 = 5，1 + 5 = 6，…
   • t[3] = 1，t[4] = 1，t[5] = 1，t[6] = 1，…
   • 最大值 maxn = 10。
3. 符合条件的数：3, 4, 5 既能通过相加得到，也在原集合中，所以答案为 3。

总结：

这段代码通过使用数组模拟“桶”的思想，枚举所有可能的两数之和，并统计这些和中哪些数既能通过两数相加得到，又存在于原集合中，最终输出满足条件的数的个数。