Codeforces Round#603(Div. 2) E/F 题解

比赛地址https://codeforces.com/contest/1263


E-Editor

题意:模拟打字,光标可以左移右移或者输入左括号右括号或者小写字母,现在给你操作序列,问每次操作完以后当前输入的字符串最深括号深度如果括号序列是合法的。
思路: 用HDU4699一样的思路去做就好了,维护前缀和,最大最小前缀和一共6个栈,如果括号序列是合法的,最深的括号深度就是前缀和最大的那个,最小前缀和是为了判定是否合法的,因为出现负数就说明不合法,时间复杂度O(n)
代码:

#include
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e6+10;
int n,i,topA=1,topB,a[N],b[N],pre[N],suf[N],f[N],f2[N],f3[N],f4[N];
char s[N];
void update(int x,int val){
    a[x]=val;
    pre[x]=pre[x-1]+a[x];
    f[x]=max(f[x-1],pre[x]);
    f2[x]=min(f2[x-1],pre[x]);
}
int main(){
    read(n);
    scanf("%s",s+1);
    int ans=-1;
    f2[0]=f4[0]=0x3f3f3f3f;
    for (i=1;i<=n;++i){
        if (s[i]=='(') update(topA,1);
        else if (s[i]==')') update(topA,-1);
        else if (s[i]=='L'){
            if (topA>=2){
                b[++topB]=a[topA--];
                suf[topB]=suf[topB-1]+b[topB]*-1;
                f3[topB]=max(f3[topB-1],suf[topB]);
                f4[topB]=min(f4[topB-1],suf[topB]);
            }
        }
        else if (s[i]=='R'){
            ++topA;
            if (topB){
                update(topA,b[topB]);
                topB--;
            }
            else{
                update(topA,0);
            }
        }
        else update(topA,0);

        if (topB==0){
            if (pre[topA]==0 && f2[topA]>=0) ans=f[topA];
            else ans=-1;
        }
        else{
            if (pre[topA]==suf[topB] && f2[topA]>=0 && f4[topB]>=0){
                ans=max(f[topA],f3[topB]);
            }
            else ans=-1;
        }
        printf("%d%c",ans,i==n?'\n':' ');
    }
    return 0;
}

F-Economic Difficulties

题意: 一共n个机器,上下有两棵以1为根的树,叶子节点与机器相连,保证对于任意子树,它管辖的机器的编号是一个连续段,问最多可以删掉多少条边,使得每个机器最少跟一棵树的根节点相连。
思路:重要性质是对于任意子树,它管辖的机器的编号是一个连续段,所以我们可以直接dp,定义dp[i]为前i的节点都能跟根节点相连最多可以删的边数,转移方程就是dp[i]=max(dp[j]+max(upcost(j+1,i),downcost(j+1,i)))cost(l,r)定义的是编号[l,r]不与根节点相连最多可以删掉多少条边,对于cost的话因为有那个性质,所以每个节点管辖的区间可以最多删除节点为根的子树大小条边,这样也不会影响到其他编号的节点,一棵树里删了另一个树没删就行,所以取max,时间复杂度O(n^2)
代码

#include
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=2000+10;
int n,a,i,j,p,dp[N],val[2][N][N],L[2][N],R[2][N],sz[2][N];
vector G[2][N];
void dfs(int u,int tp){
    if (u>1) sz[tp][u]=1;// 根节点往上没有边了
    for (int i=0;i<(int)G[tp][u].size();++i){
        int v=G[tp][u][i];
        dfs(v,tp);
        L[tp][u]=min(L[tp][u],L[tp][v]);
        R[tp][u]=max(R[tp][u],R[tp][v]);
        sz[tp][u]+=sz[tp][v];
    }
    val[tp][L[tp][u]][R[tp][u]]=sz[tp][u];
}
int main(){
    read(n);
    for (i=0;i<2;++i){
        read(a);
        for (j=2;j<=a;++j){
            read(p);
            G[i][p].push_back(j);
        }
        for (j=1;j<=a;++j) L[i][j]=a+1,R[i][j]=0;
        for (j=1;j<=n;++j){
            read(p);
            L[i][p]=R[i][p]=j;
        }
    }
    dfs(1,0),dfs(1,1);
    for (i=1;i<=n;++i){
        for (j=0;j

发表评论

电子邮件地址不会被公开。 必填项已用*标注