评测平台及题目

考试代码及其思路50分

## 思路

我们对i节点进行处理

添加（ 不可能构成合法字符串

这时我们要讨论 ）

我们从最后依次取出括号

取出 ) 时：

无法构成，存入栈中

取出 ( 时:

可以构成，但需要进行讨论（类似括号匹配）

栈为空，即无 ) 可以匹配

不可能合法，直接跳出循环（因为后面已经不是合法序列了，不可能增加）

栈不为空，即有未匹配的 )

增加的合法括号+1

这有些难理解，可以尝试在本子上画一下

注意：

这里求出的值为这个括号能创造的值，一定要加上父亲节点本身的值

## 代码

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
int n,fa[500100];
ull f[500100];
char c[500100];
string s[500100];
void pre( ){
    scanf("%d",&n);
    int i;
    getchar( );
    for(i=1;i<=n;i++)
    c[i]=getchar( );
    getchar( );
    fa[1]=1;
    for(i=2;i<=n;i++)
    scanf("%d",&fa[i]);
    f[1]=0;
    s[1]+=c[1];
    return;
}
ull dfs(int k){
    if(f[k]||k==1)return f[k];
    dfs(fa[k]);
    string ss=s[fa[k]];
    char cc=c[k];
    s[k]=ss+cc;
    if(cc=='(')return f[k]=f[fa[k]];
    ull addd=0;
    stack<char>q;
    q.push(cc);
    int i,j;
    for(i=ss.size( )-1;i>=0;i--){
        if(ss[i]=='('){
            if(q.empty( ))break;
            q.pop();
            if(q.empty( ))addd++;
        }else{
            q.push(')');
        }
    }
    return f[k]=f[fa[k]]+addd;
}
int main( ){
    //freopen("brackets.in","r",stdin);
    //freopen("brackets.out","w",stdout);
    pre( );
    ull ans=0;
    int i;
    for(i=1;i<=n;i++)ans=ans xor dfs(i)*i;
    printf("%d\n",ans);
    return 0;
}

算法总结

错误原因：MLE

考试时没考虑MLE，好亏啊qwq

O(nlogn*栈平均深度)

M(十分大,视数据而定)

试后重做

构造思路

在构造算法之前，要分析错误原因：MLE

解释：由于每次循环都会增加一个栈，这大大消耗了内存

那么我们就需要考虑新的方式来完成状态的转移

我们需要优化的是内存复杂度（时间复杂度还行）

那么我们需要用新的数组来代替栈的功能（O（1）时间复杂度之内）

设计状态+转移方程：

我们要求的是新增了多少

由于+‘(‘是不可能构成新的合法序列，于是我们就先考虑+‘)‘的情况

可配对的情况下：

那么除去本身配对的,则有2个新加

而这两个新加的就为此括号的另一半前，能匹配且与左括号相靠的括号对个数

不能匹配情况下就近似于一个‘(‘

综上

我们设计状态为当前的最大值，上一个未匹配的左括号，和有多少个连续，可匹配的括号对

代码

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
int n,fa[500100],last[500100],line[500100];
ull f[500100];
char c[500100];
void pre( ){
    scanf("%d",&n);
    int i;
    getchar( );
    for(i=1;i<=n;i++)
    c[i]=getchar( );
    getchar( );
    for(i=2;i<=n;i++)
    scanf("%d",&fa[i]);
    fa[1]=0;
    f[1]=0;
    last[1]=c[1]=='('?1:0;
    line[1]=0;
    return;
}
ull dfs(int k){
    if(f[k]||k==1)return f[k];
    dfs(fa[k]);
    if(c[k]=='('){                   //左括号不可能与之前的括号匹配 
        last[k]=k;                   //最近的一个就为他自己 
        f[k]=f[fa[k]];               //不会又增加的 
        line[k]=0;                   //不可能连续了 
    }else if(last[fa[k]]){           //有可以匹配的 
        f[k]=f[fa[k]]+line[fa[last[fa[k]]]]+1;            //配合图一 
        last[k]=last[fa[last[fa[k]]]];                    //配合图二 
        line[k]=line[fa[last[fa[k]]]]+1;                  //配合图三 
    }else{                            //否则近似于一个'(' 
        last[k]=0;
        f[k]=f[fa[k]];               //最近的一个左括号不变 
        line[k]=0;
    }
    return f[k];
}
int main( ){
    //freopen("brackets.in","r",stdin);
    //freopen("brackets.out","w",stdout);
    pre( );
    ull ans=0;
    int i;
    for(i=2;i<=n;i++)ans=ans xor dfs(i)*i;
    cout<<ans<<endl;
    return 0;
}

P5658 括号树

原文：https://www.cnblogs.com/the-Blog-of-Mikasa/p/12109372.html