285484026

Codeforces Round #556
Div2.A:Stock Arbitraging题解:简单题#include<bits/stdc++.h&g...
扫描右侧二维码阅读全文
04
2019/05

Codeforces Round #556

Div2.A:Stock Arbitraging

题解:简单题

#include<bits/stdc++.h> 

using namespace std;

int n,m,r,Min = 2147483647,Max;

int main(){
    scanf("%d %d %d",&n,&m,&r);
    int x;
    
    for(int i = 1;i <= n;++i){
        scanf("%d",&x);
        Min = min(x,Min);
    }
    for(int i = 1;i <= m;++i){
        scanf("%d",&x);
        Max = max(x,Max);
    }
    if(Max < Min){
        printf("%d\n",r);
    }
    else {
        int tmp = r / Min;
        r = r % Min;
        r += Max*tmp;
        printf("%d\n",r);
    }
    return 0; 
}

Div2.B:Tiling Challenge

题解:直接从左往右能填就填,然后判断是不是全部被填了。(QAQ考试没写FST了,我的分TAT)

#include <bits/stdc++.h>

using namespace std;

int n;
char s[55][3];
bool flag;

inline bool check(int x,int y)
{
    if(s[x][y] == '.' && s[x+1][y] == '.' && s[x][y+1] =='.'&&s[x-1][y]=='.'&&s[x][y-1]=='.') return true;
    else return false;
    
}

int main()
{
    scanf("%d",&n);

    for(int i = 0;i < n;i++) scanf("%s",s[i]);
    
    bool flag = true;
    
    for(int i = 1;i < n-1;i++)
    {
        for(int j = 1;j < n-1;j++)
        {
            if(check(i,j)){
                s[i][j] = '#';
                s[i+1][j] = '#';
                s[i][j+1] = '#';
                s[i-1][j] = '#';
                s[i][j-1] =    '#';                
            }
        }

    }
    
    for(int i = 0;i < n;i++)
        for(int j = 0;j < n;j++)
            if(s[i][j] == '.')
                flag = false;
            
    
    if(flag) printf("YES"); 
    else printf("NO");
    return 0;
}

Div2.C|Div1.A:Prefix Sum Primes

题意:给你N个数,每个数都是1或者2.现在让你求一个排列,使得这个排列的前缀和数组 拥有最多的素数。

题解:考虑除了2以外所有的质数都是奇数,所以我先把2放在第一个,而且是从3开始有奇质数,这样我后面放奇数个1可以产生尽量多的质数,并且这样的话前缀和是奇数,并且是从3开始产生,然后最后放2,也可以保证前缀和是奇数,可以产生尽量多的质数,最后放1

#include <bits/stdc++.h>

const int MAXN = 2000005;

using namespace std;

int n,a[MAXN],cnt[3];

int main()
{
    scanf("%d",&n);
    
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        ++cnt[a[i]];
    }
        
    if(cnt[2] != 0) {
        printf("2 ");
        --cnt[2];
    }
    int tmp = 0;
    
    if(cnt[1]%2) tmp = cnt[1];
    else tmp = cnt[1] - 1;

    for(int i = 1;i <= tmp;i++) printf("1 ");
    
    if(cnt[1]) cnt[1] -= tmp;
    
    for(int i = 1;i <= cnt[2];i++) printf("2 ");
        
    if(cnt[1]) printf("1 ");
    return 0;
}

Div2.D|Div1.B:Three Religions

题意:给你一个长度为N的T字符串(N<=10W),然后有$S_1,S_2,S_3$三个字符串,每次操作为添加或者删除一个S字符串末尾字符,问你能不能在T字符串中找出不相交的三个子序列等于$S_1,S_2,S_3$三个字符串(字符串长度短于250)

题解:设fi[k]:$S_1字符串匹配i个字符S_2字符串匹配j个字符S_3字符串匹配k个字符最后一个使用的T字符串中字符的位置$,然后每次删除字符就直接把对应S字符串长度减短就好了。添加字符则需要使用nxt数组[来自序列自动机],设nxti表示在大于等于i位置j字符出现的第一个位置。

#include <bits/stdc++.h>

const int MAXN = 1000000,MAXM = 260;

using namespace std;

int n,m,a,b,c;
int f[MAXM][MAXM][MAXM],nxt[MAXN][6],A[MAXN],B[MAXN],C[MAXN];
char s[MAXN];

inline void init() 
{
    scanf("%d %d",&n,&m);
    scanf("%s",s+1);
    
    for(int i = 0;i < 26;i++)
        nxt[n+1][i] = nxt[n+2][i] = n + 1;
    
    for(int i = n;i >= 0;i--){
        for(int j = 0;j < 26;j++) nxt[i][j] = nxt[i+1][j];
        if(i) nxt[i][s[i]-'a'] = i;
    }
}

int main()
{
    freopen("1.in","r",stdin);
    init();
    
    int x;char opt[5];
    while(m--)
    {
        scanf("%s",opt);
        if(opt[0] == '+')
        {
            scanf("%d",&x);
            scanf("%s",opt);
            if(x == 1){
                A[++a] = opt[0] - 'a';
                for(int i = 0;i <= b;i++)
                    for(int j = 0;j <= c;j++){
                        f[a][i][j] = nxt[f[a-1][i][j]+1][A[a]];
                        if(i) f[a][i][j] = min(f[a][i][j],nxt[f[a][i-1][j]+1][B[i]]);
                        if(j) f[a][i][j] = min(f[a][i][j],nxt[f[a][i][j-1]+1][C[j]]);
                    }
            }        
            if(x == 2){
                B[++b] = opt[0] - 'a';
                for(int i = 0;i <= a;i++)
                    for(int j = 0;j <= c;j++){
                        f[i][b][j] = nxt[f[i][b-1][j]+1][B[b]];
                        if(i) f[i][b][j] = min(f[i][b][j],nxt[f[i-1][b][j]+1][A[i]]);
                        if(j) f[i][b][j] = min(f[i][b][j],nxt[f[i][b][j-1]+1][C[j]]);
                    }    
            }
            if(x == 3){
                C[++c] = opt[0] - 'a';
                for(int i = 0;i <= a;i++)
                    for(int j = 0;j <= b;j++){                
                    f[i][j][c] = nxt[f[i][j][c-1]+1][C[c]];
                    if(i) f[i][j][c] = min(f[i][j][c],nxt[f[i-1][j][c]+1][A[i]]);
                    if(j) f[i][j][c] = min(f[i][j][c],nxt[f[i][j-1][c]+1][B[j]]);                    
                }
            }
            if(f[a][b][c] <= n) printf("YES\n");
            else printf("NO\n");
        }
        else {
            scanf("%d",&x);
            if(x == 1) a--;
            if(x == 2) b--;
            if(x == 3) c--;
            if(f[a][b][c] <= n) printf("YES\n");
            else printf("NO\n");                        
        }
    }
    
    return 0;
}

Div2.E|Div1.C:Tree Generator™
题意:给你一颗括号表达式树,问你这颗树的直径为多大,然后每次操作交换括号表达式中两个括号的位置,问你改变以后的括号表达式树的直径

题解:根据dfs的性质可以知道每有一个'('则树的深度+1,每有一个')'则树的深度-1,设d[x]为序列第x位置的深度,显然d[x]=sumx,所以树的直径问题就被巧妙的转化为max{d[z]+d[x]-2*d[y]}(x<=y<=z)至于怎么求取则需要用线段树来维护

数组含义:

sum[o]:区间和
T[o][0]:区间max(sum[z]+sum[x]-2*sum[y])

T[o][1]:区间max(sum[x]) 
T[o][2]:区间min(sum[x])

T[o][3]:区间max(sum[x]-2sum[y]) 
T[o][4]:区间max(sum[z]-2sum[y])

数组初始化:

sum[o] = d[x]
T[o][1] = T[o][2] =  d[x];
T[o][3] = T[o][4] = -d[x];//d[x]-2*d[x]=-d[x]
T[o][0] = 0;

数组维护:

int l = o<<1,r = o<<1|1;
sum[o] = sum[l] + sum[r];
T[o][0] = max(
             T[l][0],X,Y,Z均在左区间
             T[r][0] X,Y,Z均在右区间
             );
T[o][0] = max(T[o][0],
max(
T[l][3]+sum[l]+T[r][1],X,Y在左区间,Z在右区间
T[l][1]-sum[l]+T[r][4] X在左区间,Y,Z在右区间
));
    
T[o][1] = max(T[l][1],sum[l]+T[r][1]);
T[o][2] = min(T[l][2],sum[l]+T[r][2]);
    
T[o][3] = max(T[l][3],    sum[x]-2sum[y]均在左区间
max(
T[r][3]-sum[l],           sum[x]-2sum[y]均在右区间但是需要加上前缀和+sum[l]-2sum[l] =-sum[l]
T[l][1]-2*(T[r][2]+sum[l] sum[x]在左区间sum[y]在右区间
)));
T[o][4] = max(T[l][4],    sum[z]-2sum[y]均在左区间
max(
T[r][4]-sum[l],           sum[z]-2sum[y]均在右区间但是需要加上前缀和+sum[l]-2sum[l] =-sum[l]
T[r][1]+sum[l]-2*T[l][2]  sum[z]在左区间sum[y]在右区间
));
#include <bits/stdc++.h>

const int MAXN = 1000000;

using namespace std;

int n,q,cx;
int T[MAXN][5],sum[MAXN],d[MAXN];
char s[MAXN];

inline void init(int o,int x){
    sum[o] = T[o][1] = T[o][2] = d[x];
    T[o][3] = T[o][4] = -d[x];
    T[o][0] = 0;
} 

inline void update(int o){
    int l = o<<1,r = o<<1|1;
    sum[o] = sum[l] + sum[r];
    T[o][0] = max(T[l][0],T[r][0]);
    T[o][0] = max(T[o][0],max(
        T[l][3] + sum[l] + T[r][1],//X Y/Z
        T[l][1] - sum[l] + T[r][4] //X/Y Z
        )
    );
    
    T[o][1] = max(T[l][1],sum[l]+T[r][1]);
    T[o][2] = min(T[l][2],sum[l]+T[r][2]);
    
    T[o][3] = max(T[l][3],max( T[r][3]-sum[l] , T[l][1]-2*(T[r][2]+sum[l]) ));
    T[o][4] = max(T[l][4],max( T[r][4]-sum[l] , T[r][1]+sum[l]-2*T[l][2] ) );
}

void build(int o,int l,int r){
    if(l == r){init(o,l);return;}
    int m = l + r >> 1;
    build(o<<1,l,m);
    build(o<<1|1,m+1,r);
    update(o);
}

void modify(int o,int l,int r){
    if(l == r){init(o,l);return;}
    int m = l + r >> 1;
    if(cx <= m) modify(o<<1,l,m);
    else modify(o<<1|1,m+1,r);
    update(o);
}

int main()
{
    //freopen("1.in","r",stdin);
    
    scanf("%d %d",&n,&q);
    
    n = 2*(n-1);
    
    scanf("%s",s+1);
    
    for(int i = 1;i <= n;i++)
        if(s[i] == '(') d[i] = 1;
        else d[i] = -1;
    
    build(1,1,n);
    printf("%d\n",T[1][0]);
    
    int x,y;
    while(q--){
        scanf("%d %d",&x,&y);
        swap(d[x],d[y]);
        cx = x;modify(1,1,n);
        cx = y;modify(1,1,n);
        printf("%d\n",T[1][0]);
    }
    
    return 0;
}
Last modification:May 4th, 2019 at 11:37 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment