Codeforces Round #622 (Div. 2)

A - Fast Food Restaurant

一个比较复杂的模拟。不知道有没有贪心的做法。

struct Node {
    int a, b, c;
} cnt[7];
 
void test_case() {
    int A, B, C;
    scanf("%d%d%d", &A, &B, &C);
    int ans = 0;
    for(int i = 0; i < (1 << 7); ++i) {
        if(__builtin_popcount(i) > ans) {
            int a = 0, b = 0, c = 0;
            for(int x = 0; x < 7; ++x) {
                if(i & (1 << x)) {
                    a += cnt[x].a;
                    b += cnt[x].b;
                    c += cnt[x].c;
                }
            }
            if(a <= A && b <= B && c <= C)
                ans = __builtin_popcount(i);
        }
    }
    printf("%d\n", ans);
}

    cnt[0] = {1, 0, 0};
    cnt[1] = {0, 1, 0};
    cnt[2] = {0, 0, 1};
    cnt[3] = {1, 1, 0};
    cnt[4] = {0, 1, 1};
    cnt[5] = {1, 0, 1};
    cnt[6] = {1, 1, 1};
}

C1 - Skyscrapers (easy version)

见下。

C2 - Skyscrapers (hard version)

题意：给一个n(<=5e5)个数字的数字序列，表示每个点能取到的最大值。求构造一个和最大的peek，例如：1 2 3 2 1是一个peek，10 6 6也是一个peek。准确来说，就是存在一个最高的位置，然后向两侧递减。

题解：乍一看好像做过，搞个前缀最小值和后缀最小值，但是仔细推细节的时候发现是单调栈的题，用单调栈可以维护出以某个点为结束时使得前缀部分不下降的最大值。存下前缀和后缀的最大值就可以找到那个peek的位置，然后再用一次单调栈找到peek位置时单调栈的形状，根据单调栈的形状还原出序列。

int m[500005];
int ansm[500005];
ll prefixsum[500005];
ll suffixsum[500005];
int sta[500005], top;

void test_case() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &m[i]);
    top = 0;
    sta[top] = 0;
    for(int i = 1; i <= n; ++i) {
        while(top && m[sta[top]] >= m[i])
            --top;
        prefixsum[i] = prefixsum[sta[top]] + 1ll * (i - sta[top]) * m[i];
        sta[++top] = i;
    }
    top = 0;
    sta[top] = n + 1;
    for(int i = n; i >= 1; --i) {
        while(top && m[sta[top]] >= m[i])
            --top;
        suffixsum[i] = suffixsum[sta[top]] + 1ll * (sta[top] - i) * m[i];
        sta[++top] = i;
    }
    /*for(int i = 1; i <= n; ++i)
        printf("%lld%c", prefixsum[i], " \n"[i == n]);
    for(int i = 1; i <= n; ++i)
        printf("%lld%c", suffixsum[i], " \n"[i == n]);*/
    top = 0;
    ll ans = suffixsum[1], pos = 1;
    for(int i = 1; i < n; ++i) {
        ll tmp = prefixsum[i] + suffixsum[i + 1];
        if(tmp > ans) {
            ans = tmp;
            pos = i + 1;
        }
    }
    //printf("pos=%d\n", pos);

    top = 0;
    for(int i = 1; i < pos; ++i) {
        while(top && m[sta[top]] >= m[i])
            --top;
        sta[++top] = i;
    }
    for(int i = 1, j = 1; i < pos; ++i) {
        if(j <= top && i > sta[j])
            ++j;
        assert(j <= top);
        ansm[i] = m[sta[j]];
    }

    top = 0;
    for(int i = n; i >= pos; --i) {
        while(top && m[sta[top]] >= m[i])
            --top;
        sta[++top] = i;
    }
    for(int i = n, j = 1; i >= pos; --i) {
        if(j <= top && i < sta[j])
            ++j;
        assert(j <= top);
        ansm[i] = m[sta[j]];
    }

    for(int i = 1; i <= n; ++i)
        printf("%d%c", ansm[i], " \n"[i == n]);
}

Codeforces Round #622 (Div. 2)

原文：https://www.cnblogs.com/KisekiPurin2019/p/12395939.html