[C++知识库]23次csp认证

1、数组推导

#include<iostream>
#include<cstring>

using namespace std;
const int N=1e5+10;

int n;
int b[N];
int minsum,maxsum;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&b[i]);
    minsum+=b[0];
    maxsum+=b[0];
    for(int i=1;i<n;i++)
    {
        if(b[i]>b[i-1])   minsum+=b[i],maxsum+=b[i];
        else maxsum+=b[i];
    }
    printf("%d\n%d",maxsum,minsum);
    return 0;
}

2、非零段划分

// 70分
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=5*1e5+10;

int n;
int a[N];
int ans;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    
    for(int i=0;i<n;i++)
    {
        int sum=0;
        if(a[i]==0) continue;
        bool flag=true;
        for(int j=0;j<n;j++)
        {
           
            if(a[j]>=a[i])
            {
                if(flag) 
                {   
                    sum++;
                    flag=false;
                }
            }
            else flag=true;
        }
        ans=max(ans,sum);
    }
    printf("%d",ans);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 500010, M = 10010;

int n;
int a[N], cnt[M];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    //unique将所有相邻且相同的元素删掉，返回判重后的下一个位置
    //减去开头位置，就可以返回个数
    n = unique(a + 1, a + n + 1) - (a + 1);
    //处理边界 方便后期比较
    a[0] = a[n + 1] = 0;

    for (int i = 1; i <= n; i ++ )
    {
        int x = a[i - 1], y = a[i], z = a[i + 1];
        if (x < y && z < y) cnt[y] ++ ;
        else if (x > y && z > y) cnt[y] -- ;
    }

    int res = 0, sum = 0;
    //枚举高度 
    //0不需要枚举 都是0只有一个。
    for (int i = M - 1; i; i -- )
    {
        sum += cnt[i];
        res = max(res, sum);
    }

    printf("%d\n", res);
    return 0;
}