Vijos P1911 珠心算测验【序列处理】

描述

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

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

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

格式

输入格式

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

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

输出格式

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

样例1

样例输入1

4
1 2 3 4

样例输出1

限制

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

提示

由 1+2=3，1+3=4，故满足测试要求的答案为 2。注意，加数和被加数必须是集合中的两个不同的数。

来源

NOIP2014 普及组

问题链接：Vijos P1911 珠心算测验

问题分析：

穷举法实现，方法上没有什么技术含量。

如何去除重复计数是关键，通常是使用一个标记数组。

因为给出的正整数不超过10000，需要将其作为一个条件来用。

程序说明：

数组flag[]用于标记可能的和。开始时，对于输入的正整数i，设置flag[i]为1。对于和sum，只有flag[sum]=1时才计数，计数后flag[sum]置为0。

使用运算符“,”（逗号），可以使得程序变得简短。

参考链接：（略）

AC的C++程序如下：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100;
const int N2 = 10000;

int a[N];
int flag[N2 + 1];

int main()
{
    int n;

    memset(flag, 0, sizeof(flag));

    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> a[i];
        flag[a[i]] = 1;
    }

    int ans = 0;
    for(int i=0; i<n; i++)
        for(int j=0; j<i; j++)
            if(a[i] + a[j] <= N2 && flag[a[i] + a[j]])
                ans++, flag[a[i] + a[j]] = 0;

    cout << ans << endl;

    return 0;
}