CSP-J题解合集

题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。

珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。 

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。

他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？  

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

输入格式

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

第二行有 $n$ 个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数（均不超过 $10000$）。

输出格式

输出共一行，包含一个整数，表示测验题答案。

数据范围

$3 \\le n \\le 100$

输入样例：

4
1 2 3 4

输出样例：

2

算法

(暴力枚举) $O(n^3)$

直接枚举，开桶计算是否满足条件。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=120,M=10020;
int n,cnt;
int a[N],t[M];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(a[i]+a[j]==a[k])
                    t[k]=1;
    for(int i=0;i<=10000;i++)  
        if(t[i])
            cnt++;
    cout<<cnt;
}