P2141 题解

ikunTLE · 2024-12-29 00:00:03 · 题解

题目传送门

思路

用 F_i 代表 i 是否在输入序列 A 中。

首先标记 A 中所有的数字，即 F_{A_i}\gets1，代表 A_i 出现。

然后两层循环 i 和 j 遍历整个序列 A。若 F_{A_i+A_j}=1，说明 A_i+A_j 这个数是可以被另外两个数相加得到的，增加答案个数，并更新 F_{A_i+A_j} 为 0。

最后输出答案个数即可。

注意事项

• 访问数组 F 的最大值 A_i+A_j 为 2\times10^4，注意数组大小。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e2+10,M=2e4+10;
int a[N];
bool flag[M];
int main(){
    int n=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        flag[a[i]]=true;
    }
    int cnt=0;
    for(int i=1;i<n;++i)
        for(int j=i+1;j<=n;++j)
            if(flag[a[i]+a[j]])
                ++cnt,flag[a[i]+a[j]]=false;
    printf("%d\n",cnt);
    return 0;
}