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

J4C 消えた夏の夢题解

思路

贪心，显然选了负数之后，还要再选一次（不然就没必要选），此时答案没增加减少，不优。

所以遇到正数就取了，且只取一次。

复杂度

时间复杂度: $O(n)$

空间复杂度: $O(n)$

Code

#include <bits/stdc++.h>
using namespace std;

long long n, p;

int main() {
	scanf("%lld%lld", &n, &p);
	for (int x ; n-- ; )
		scanf("%d", &x), p += max(0, x);
	printf("%lld\n", p);
	return 0;
}

「RiOI-4」消えた夏の夢题解

思路

超级大水题。

根据题目描述，我们可以很容易的想到，只要把所有的正数与原数加上即可。

因为加上一个负数会让 $x$ 的值变小，且就算再加一次也只是与上一次操作抵消，不会产生贡献，所以不需要处理负数。

思路有了，代码就很好写了。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,p,b;
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	{
		cin>>b;
		if(b>0) p+=b;
	}
	cout<<p;
	return 0;
}

标题

思路

解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

J4C 消えた夏の夢

思路

一开始看的时候吓了一跳还以为又是什么动规贪心，结果仔细一看又吓了一跳…… 怎么说呢，观察样例可以知道，直接把所有正整数和原本的数加起来就好了。。。

解题方法

代码奉上：

#include<iostream>
using namespace std;
int main(){
long long int a,b;
cin>>a>>b;
long long int tmp;
while(a--){
    cin>>tmp;
    if(tmp>0)b+=tmp;
}
cout<<b;
return 9;
}

空间复杂度/时间复杂度

都$O(n)$吧，这个不重要，毕竟解题就是个枚举没得说

{ #include<bits/stdc++.h> using namespace std; #define int long long int a[1000005]; signed main() { int n,p; cin>>n>>p; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); for(int i=1;i<=n;i++) { p+=a[i]; if(a[i]<0) { a[i]=-a[i]; p+=a[i]; } else a[i]=-a[i]; } cout<<p; return 0; } }

J4C 消えた夏の夢

思路

既然需要最大值，那么不要加负数即可，把整数累加后加上 $p$ 即可，记得开 long long。

加了负数也没用，加上后为了最大还要加上相反数，不如不加。

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
	long long n,s;
	cin >> n >> s;
	for (int i = 1;i <= n;i++) 
	{
		cin >> a[i];
		if (a[i] > 0) s = s + a[i];
	}
	cout << s;
    return 0;
}