P2141 题解

思路

用

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

CPP

#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;
}

文章操作

思路

相关推荐

评论

P2141 题解