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

知识点

枚举、集合、去重

解题思路

枚举两个不同下标i<j，将a[i]+a[j]加入集合。随后逐个检查原数组中有多少个数在集合内。

正确性说明

每对不同元素恰好被枚举一次，集合记录所有可表示为两个不同元素之和的值。对每个原数组元素只判定一次，故不会因不同分拆方案重复计数。

易错点

必须用两个不同下标；题目原数组值互不相同；统计符合条件的数的个数，而不是表示方案数。

复杂度

构造哈希集合期望时间O(n²)，查询期望O(n)，额外空间O(n²)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;vector<int>a(n);for(int &x:a)cin>>x;unordered_set<int>s;
    for(int i=0;i<n;++i)for(int j=i+1;j<n;++j)s.insert(a[i]+a[j]);
    int ans=0;for(int x:a)ans+=s.count(x);cout<<ans<<'\n';
}