Codeforces Round #556 (Div. 2) （A - E题解）

50 阅读 0 评论 33 点赞

我是靠谱客的博主老实盼望，最近开发中收集的这篇文章主要介绍Codeforces Round #556 (Div. 2) （A - E题解），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A.Stock Arbitraging

贪心选最小最大就可以了。

B. Tiling Challenge

模拟暴力就可以了。

C. Prefix Sum Primes

这个题因为只有 1 和 2，所以我们贪心一下，如果加 1 是质数的话，那么就加 1，否则优先使用 2.

D.Three Religions

首先预处理出来一个 idx 数组，代表从 i 这个位置开始，字母 c 第一次出现的位置在哪里？

f[i][j][k] 代表三个子字符串分别用到 i， j ，k 这几个位置，在母串中最短表示。
以第一子字符为例。
然后每加入一个新字母就要更新
f[i][j][k] = min(f[i][j][k],idx[f[i-1][j][k]][c])
然后其他两个子串都要从 0 开始更新。

下面两个子串同理，也都这样更新。
然后判断 f[len[0]][len[1]][len[2]] 的值是不是小于n，

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+100;
bool vis[N];
int n,m,a[5],p[N/10],cnt;
void Get_prime(int nn){
    vis[1] = 1;
    for (int i = 2; i < nn; ++i){
        if (!vis[i]) p[cnt++] = i;
        for (int j = 0; j < cnt && i*p[j] < nn; ++j){
            vis[i*p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}

int main(){
    scanf("%d",&n);
    Get_prime(N-50);
    for (int i = 0; i < n; ++i){
        scanf("%d",&m);
        a[m]++;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i){
        if (a[1] && a[2]){
            if (vis[ans+1]==0) printf("1 "),a[1]--,ans++; else printf("2 "),a[2]--,ans+=2;
        }else if (a[2]){
            printf("2 "); a[2]--; ans+=2;
        } else {
            printf("1 "); a[1]--; ans++;
        }
    }


    return 0;
}

E. Tree Generator™

这里有解释。

https://blog.csdn.net/weixin_43980799/article/details/89740942

顺便说一下，为什么那样可以保持 abc 是有序的。因为当前区间是从两个子区间推过来的，

然后两个子区间分别有自己的两个子区间，所以相当于有四个区间，

#include<bits/stdc++.h>
#define ls (now << 1)
#define rs (now << 1 | 1)
using namespace std;
const int N = 2e5+100;
char s[N];
int n,m,t[N];
int a[N*4],b[N*4],ab[N*4],ba[N*4],aba[N*4],tag[N*4];

void pushup(int now){
    a[now] = max(a[ls],a[rs]);
    b[now] = min(b[ls],b[rs]);
    ab[now] = max(ab[ls],max(ab[rs],a[ls]-2*b[rs]));
    ba[now] = max(ba[ls],max(ba[rs],a[rs]-2*b[ls]));
    aba[now] = max(max(aba[ls],aba[rs]),max(ab[ls]+a[rs],ba[rs]+a[ls]));
}
void build(int now, int l, int r){
    if (l+1==r){
        a[now] = b[now] = t[l];
        ab[now] = ba[now] = -t[l]; return;
    }
    int mid = (l + r) >> 1;
    build(ls,l,mid); build(rs,mid,r);
    pushup(now);
}
void down(int now, int val){
    a[now] += val; b[now]+= val; ab[now] -= val; ba[now] -= val;tag[now] += val;
}
void pushdown(int now){
    down(ls,tag[now]); down(rs,tag[now]);
    tag[now] = 0;
}
void Insert(int now, int l, int r, int a, int b, int val){
    if (a <= l && b >= r-1){
        down(now,val); return;
    }
    int mid = (l + r) >> 1;
    pushdown(now);
    if (a < mid) Insert(ls,l,mid,a,b,val);
    if (b >= mid) Insert(rs,mid,r,a,b,val);
    pushup(now);
}
int main(){
    int x,y,z;
    scanf("%d%d",&n,&m);
    n = n*2-2;
    scanf("%s",s+1);
    for (int i = 1; i <= n; ++i)
        if (s[i] == '(') t[i] = t[i-1] + 1; else t[i] = t[i-1]-1;
    build(1,1,n+1);

    printf("%dn",aba[1]);
    for (int i = 0; i < m; ++i){
        scanf("%d%d",&x,&y);
        if (x > y) swap(x,y);
        if (s[x] == '(') z = -2; else z = 2;
        Insert(1,1,n+1,x,y-1,z);
        swap(s[x],s[y]);
        printf("%dn",aba[1]);
    } 
    return 0;
}
/*
5 5
(((())))
3 4
5 6
3 6
2 5

6 4
(((())()))
6 7
5 4
6 4
7 4

*/