7 条题解

  • 0
    @ 2024-9-8 19:10:15

    J4C 消えた夏の夢

    思路

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

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

    复杂度

    时间复杂度:

    O(n)O(n)

    空间复杂度:

    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;
    }
    
    • -1
      @ 2024-11-24 8:08:44

      X3C

      「RiOI-4」消えた夏の夢

      思路

      显然,一个数字只会被选 11 次或 00 次,证明如下:

      令当前数为 XX,序列中某个数字为 aia_i

      那么第一次选时 XX 会变成 X+aiX + a_iaia_i 会变成 ai-a_i

      第二次选时 X+aiX + a_i 会变成 X+aiai=XX + a_i - a_i \xlongequal {} Xai-a_i 会变成 aia_i

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

      所以每个数字只会被选 11 次或 00 次。

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

      复杂度

      时间复杂度:

      O(N)O(N)

      空间复杂度:

      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;
      }
      
      • -1
        @ 2024-9-28 16:38:34

        J4C 消えた夏の夢题解

        思路

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

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

        复杂度

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

        空间复杂度: 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;
        }
        
        • -1
          @ 2024-9-8 18:06:21

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

          思路

          超级大水题。

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

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

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

          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;
          }
          
          • -2
            @ 2024-10-4 15:04:49

            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)O(n)吧,这个不重要,毕竟解题就是个枚举没得说

            • -2
              @ 2024-9-19 12:48:38

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

              • -3
                @ 2024-10-4 20:15:57

                标题

                思路

                解题方法

                复杂度

                时间复杂度:

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

                空间复杂度:

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

                Code

                • 1

                信息

                ID
                48
                时间
                1000ms
                内存
                512MiB
                难度
                2
                标签
                递交数
                432
                已通过
                281
                上传者