CSP2019-D1T2 括号树 题解

1、暴力:10~20pts,复杂度 \(O(n^4)\),只能解决链

暴力很容易就会了。

因为只解决链,所以不用建树,用一个数组存就可以了,编号为 ii 的祖先恰好是\(i-1\) ,也就是说本身编号就是顺序的

先套一重 for 枚举\(i\) ,代表从根节点走到了 \(i\)号节点。由于要计算 \(1-i\)中究竟有多少个子括号序列,所以我们还需要枚举左端点 \(l\)和右端点 \(r\) ,表示枚举到区间为 \([l,r]\) 的子括号序列。然后还要写一个判断括号是否匹配的 \(check\) 子函数。子函数的复杂度为 \(O(r-l)\)。

check子函数,开栈来判断即可。具体可以看这题

3重循环套一个 check ,所以复杂度为 \(O(n^4)\)。实际上是跑不满的,所以有望过 \(n=200\) 的数据。

2、55pts,复杂度 \(O(n)\) ,只解决链

O(1)计算呢

注意,以下的例子第一个字符的下标均为 1


例子1:
()()()

我们发现, i=2的时候,对答案的贡献值为 1 。而 i=4 的时候,本身 \([3,4]\)就有一个满足要求的括号序列,在合并上前面的成为 \([1,4]\),同样满足,于是对答案的贡献值就为 2 ,再加上前面 [1,2]本身有的括号序列,总共为 3 。

i=6时同理,总共的贡献值为 3 ,加上前面的有 3+3=6种。其他位置均没有贡献。

换句话说, i为 1-6 时对答案的贡献分别为 0,1,0,2,0,3 ,合并后的总答案为 0,1,1,3,3,6


例子2:
())()

继续前面的思想, i=2 时,对答案贡献 1 。而 i=3时,由于不满足成匹配的括号序列,所以没有贡献。而 i=5时,由于 i=3多了一个后括号, [1,3] 不匹配,导致 [1,5]成不了一个匹配的括号序列。故对答案的贡献仍为 1

i为 1-5时对答案的贡献分别为 0,1,0,0,1 ,合并后的总答案为 0,1,1,1,2


例子3:
()(())

接着刚刚的分析, i=2时,贡献为 1,而 i=5时,由于 i=3 在中间断开,使 [1,5]不能匹配,所以贡献仍为 1 。

当 i=6情况有了变化。我们发现 [1,2]是匹配的。故 [1,2],[3,6]能合成一个匹配的序列,故对答案贡献为 2。

i为 1-6时对答案的贡献分别为 0,1,0,0,1,2,合并后的总答案为 0,1,1,1,2,4


发现,一个后括号如果能匹配一个前括号,假设这个前括号的前 1 位同样有一个已经匹配了的后括号,那么我们势必可以把当前的匹配和之前的匹配序列合并,当前的这个后括号的贡献值,其实就等于前面那个后括号的贡献值 +1 !

这是一个非常重要的结论,可以在递推过程中,直接完成 O(1) 计算贡献值!

有了贡献值,当前位置答案总和就很好算了。很明显,第 i位的总和等于 i-1位的总和 加上 第 i位的贡献值。

那怎么判断括号是否匹配呢? 我们同样可以用这题的思想开栈做。每次压入一个括号然后进行操作即可。

就算后括号匹配了,那我又如何知道前括号的位置呢? 其实也很简单。我们把压入括号改一改,不压括号,取之而代,压入前括号的位置即可。判断是否匹配只需要看栈里有没有数即可。

我们用 lst[i] 表示第 i位的贡献, sum[i]表示第 i 位的答案总合。那么就有:

//s是栈,top是栈顶,手写栈貌似要快很多。

if(c[i] == ')') //是后括号
{
    if(top == 0) continue; //栈为空,则没有匹配
    int t = s[top]; //匹配的前括号的位置 
    lst[i] = lst[t - 1] + 1 //结论计算贡献值
    top --;
}
else if(c[i] == '(') s[++ top] = i; //是前括号,就压入它的位置 
sum[i] = sum[i - 1] +  lst[i]; //计算总和 

很容易发现,这样处理一个位置的总和其实是 O(1)的

当然整个代码要放进一个循环里。完整代码如下:

for(int i = 1; i <= n; i ++) //好吧只多了个循环....
{
    if(c[i] == ')')
    {
        if(top == 0) continue; //判断栈是否为空 
        int t = s[top]; //匹配的前括号的位置 
        lst[i] = lst[t - 1] + 1 //结论计算贡献值
        top --;
    }
    else if(c[i] == '(') s[++ top] = i; //是前括号,就压入它的位置 
    sum[i] = sum[i - 1] +  lst[i]; //计算总和 
} 

2、100pts,复杂度 O(n),正解

很明显,我们解决链的做法在树里有很多行不通的地方。

困难主要出现在这 2个方面。

首先,你没法遍历整颗树的时候编号是连续的。这代表着我们 lst[i] = lst[t - 1] + 1 这样计算是完全行不通了。

其次,遍历一棵树必然会有递归和回溯。而处理链我们不考虑回溯,一直向下找就可以找完了。


先看第一个问题

虽然编号不连续了,但是你的括号序列一定是从父节点传递下来的!

仔细一想,我们发现,在链的情况里,为什么能用 lst[i] = lst[t - 1] + 1 计算贡献?其实, t-1 就是 t的父亲节点!无非是 [t,i]的括号序列继承了 [1,t-1],也就是 [1,fa[t]]的括号序列!( fa[i]代表 i 的父亲)

这条定则对于树完全适用。于是我们就可以修改一波原来的式子:

lst[i] = lst[t - 1] + 1` ->−> `lst[x] = lst[fa[t]] + 1;

当然计算总答案也要修改:

sum[i] = sum[i - 1] + lst[i];` ->−> `sum[x] = sum[fa[x]] + lst[x];

接下来考虑解决第二个问题:

在树中遍历有回溯,回溯后栈里的信息可能就无法对应当前的版本...

其实这个问题很容易解决。由于每次回溯只回溯一层,所以我们在回溯的时候,执行我们递归时相反的操作即可!

比如,如果我们扫到右括号,递归时如果栈不为空,照理来说会弹出一个位置信息。

那么我们就可以记录这个信息,回溯的时候再把它压回去,又变成了我们当前的版本。

扫到左括号也一样。我们会压入一个位置信息,那么回溯时,直接弹出这个压入的信息就可以了!

其实这也相当于“复原”操作,让栈里的信息永远留在我们现在的状态!

递归代码就很好写了:

//我使用的链表存图qwq,head,nxt,to都是链表所用(应该都看得懂吧?)

void dfs(int x)
{
    int tmp = 0;
    if(c[x] == ')')
    {
        if(top)
        {
            tmp = s[top];
            lst[x] = lst[fa[tmp]] + 1;
            -- top; 
        }
    }
    else if(c[x] == '(') s[++ top] = x; 
    sum[x] = sum[fa[x]] + lst[x]; //如上所述 
    for(int i = head[x]; i; i = nxt[i])
        dfs(to[i]); //递归 
    //回溯复原操作
    if(tmp != 0) s[++ top] = tmp; //不为 0 代表有信息被弹出 
    else if(top) -- top; 
    //为 0 代表没有弹出,如果栈不为空说明一定压入了一个信息,需要弹出这个信息复原 
}

完整代码

#include<bits/stdc++.h>
#define orz 0
#define inf 0x3f3f3f3f
#define ll long long
#define maxn 500005;

using namespace std;

int n;
char c[maxn];
int head[maxn], nxt[maxn], to[maxn], cnt, fa[maxn];
ll lst[maxn], sum[maxn], ans;
int s[maxn], top;

void add_edge(int u, int v)
{
    nxt[++ cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}

void dfs(int x)
{
    int tmp = 0;
    if(c[x] == ')')
    {
        if(top)
        {
            tmp = s[top];
            lst[x] = lst[fa[tmp]] + 1;
            -- top; 
        }
    }
    else if(c[x] == '(') s[++ top] = x; 
    sum[x] = sum[fa[x]] + lst[x]; //如上所述 
    for(int i = head[x]; i; i = nxt[i])
        dfs(to[i]); //递归 
    //回溯复原操作
    if(tmp != 0) s[++ top] = tmp; //不为 0 代表有信息被弹出 
    else if(top) -- top; 
    //为 0 代表没有弹出,如果栈不为空说明一定压入了一个信息,需要弹出这个信息复原 
}

int main()
{
    scanf("%d", &n);
    scanf("%s", c + 1);
    for(int i = 2; i <= n; i ++)
    {
        int f;
        scanf("%d", &f);
        add_edge(f, i);
        fa[i] = f;
    }
    dfs(1);
    for(int i = 1; i <= n; i ++)
        ans ^= sum[i] * (ll)i;
    printf("%lld", ans);
    return orz;
}

不仅 ans要开 longlong , lst 和 sum 同样需要!否则你会被构造数据卡得崩溃...

上一篇:备忘录


下一篇:火星无人机全部代码公开!毅力号带着手机芯片和 Linux 系统上太空