X3C

「RiOI-4」消えた夏の夢

思路

显然，一个数字只会被选 $1$ 次或 $0$ 次，证明如下：

令当前数为 $X$，序列中某个数字为 $a_i$。

那么第一次选时 $X$ 会变成 $X + a_i$，$a_i$ 会变成 $-a_i$。

第二次选时 $X + a_i$ 会变成 $X + a_i - a_i \xlongequal {} X$，$-a_i$ 会变成 $a_i$。

也就是说，第二次选择一个数等于没选。

所以每个数字只会被选 $1$ 次或 $0$ 次。

那么就可以贪心了。如果 $a_i > 0$，就选它，计算贡献，否则不选它，不计算贡献。

复杂度

时间复杂度:

$O(N)$

空间复杂度:

$O(N)$

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N];
long long ans=0;
signed main(){
    scanf("%d%lld",&n,&ans);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    for(int i=1;i<=n;i++)
        if(a[i]>0)
            ans+=a[i];
    printf("%lld",ans);
    return 0;
}