【解题报告】洛谷P5658 括号树

题目链接

https://www.luogu.com.cn/problem/P5658

思路

看到这道题目，我们有必要了解一下括号序列

然后不会打正解？

好，打部分分

  • fi=i−1f_i=i-1 的部分

    • n≤200n \le 200

      这一部分的分数我们可以直接打暴力，然后三个循环 O(n3)O(n^3) 再加上一个 O(n)O(n) 的判断被嵌套在这三个循环里面，总共是 O(n4)O(n^4) ，可以过掉这一部分的数据

      期望得分 20pts

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      #include <iostream>
      #include <cstdio>
      #include <algorithm>
      #include <cstring>
      #include <string>
      using namespace std;
      const int maxn=500005;
      int n,fa[maxn],ans;
      bool flag=true;
      char s[maxn];
      struct edge{
      	int e,next;
      }ed[maxn<<1];
      int en,first[maxn];
      void add_edge(int s,int e)
      {
      	en++;
      	ed[en].next=first[s];
      	first[s]=en;
      	ed[en].e=e;
      }
      bool check(int l,int r)
      {
      	int cnt=0;
      	for(int i=l;i<=r;i++)
      	{
      		if(s[i]=='(') cnt++;
      		else if(s[i]==')') cnt--;
      		if(cnt<0) return false;
      	}
      	if(cnt==0) return true;
      	return false;
      }
      int main()
      {
      	cin>>n;
      	scanf("%s",s+1);
      	for(int i=1;i<=n-1;i++)
      	{
      		int x;
      		cin>>x;
      		fa[i+1]=x;
      		if(fa[i+1]!=i) flag=false;
      		add_edge(i+1,x);
      		add_edge(x,i+1);
      	}
      	if(flag)
      	{
      		for(int i=1;i<=n;i++)
      		{
      			int cnt=0;
      			for(int l=1;l<=i;l++)
      			{
      				for(int r=l+1;r<=i;r++)
      				{
      					if(check(l,r))
      						cnt++;
      				}
      			}
      			ans=(ans^(cnt*i));
      		}
      		cout<<ans<<'\n';
      		return 0;
      	}
      	return 0;
      }

    • n≤105n \le 10^5 的部分

      我们可以发现，实际上我们的瓶颈在于我们有一个 n3n^3 的美剧左端点，枚举右端点和一次判断，我们要完成 10510^5 的数据，至少要达到 O(nlogn)O(nlogn) 的时间复杂度，所以我们要继续优化

      根据大佬的提示，我们可以知道下面一段话

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

      然后我们就可以按照这个写出代码，这个结论要用手模一下

      期望得分 55pts

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      #include <iostream>
      #include <cstdio>
      #include <algorithm>
      #include <cstring>
      #include <string>
      #define int long long
      using namespace std;
      const int maxn=500005;
      int n,fa[maxn],ans;
      int st[maxn],don[maxn],sum[maxn],size;
      bool flag=true;
      char s[maxn];
      struct edge{
      	int e,next;
      }ed[maxn<<1];
      int en,first[maxn];
      void add_edge(int s,int e)
      {
      	en++;
      	ed[en].next=first[s];
      	first[s]=en;
      	ed[en].e=e;
      }
      bool check(int l,int r)
      {
      	int cnt=0;
      	for(int i=l;i<=r;i++)
      	{
      		if(s[i]=='(') cnt++;
      		else if(s[i]==')') cnt--;
      		if(cnt<0) return false;
      	}
      	if(cnt==0) return true;
      	return false;
      }
      signed main()
      {
      	cin>>n;
      	scanf("%s",s+1);
      	for(int i=1;i<=n-1;i++)
      	{
      		int x;
      		cin>>x;
      		fa[i+1]=x;
      		if(fa[i+1]!=i) flag=false;
      		add_edge(i+1,x);
      		add_edge(x,i+1);
      	}
      	if(flag)
      	{
      		for(int i=1;i<=n;i++)
      		{
      			if(s[i]==')')
      			{
      				if(size==0) continue;
      				int t=st[size];
      				don[i]=don[t-1]+1;
      				size--;
      			}
      			else if(s[i]=='(')
      			st[++size]=i;
      		}
      		for(int i=1;i<=n;i++)
      			sum[i]=sum[i-1]+don[i];
      		for(int i=1;i<=n;i++)
      		ans=(ans^(i*sum[i]));
      		cout<<ans<<'\n';
      		return 0;
      	}
      	return 0;
      }

  • 无特殊性质

    这种情况，我们要做的是把序列上的问题转化到树上，每个结点到根的简单路径有且仅有一条，所以如果单单是对于这一条链的话，策略跟上面一样,但是我们的前一个结点就变了，上一个左括号的，也就是上面的代码中的 tt 我们要改成 fa[t]fa[t] 这样，然后计算每个结点对应的合法序列的个数也要改变

    那我们压进栈里面的数字怎么办啊

    我们设置了一个中间值，记录上一个左括号的位置，如果这个中间值为 00 的话，说明这是一个左括号，那么在栈里面加入它，如果不是 00 的话，判断一下栈的大小是否为 00 ，如果不是 00 的话，我们就可以发现一个事情，在之前的递归中，我们一定压入了一个数，但是这个数会影响后面的答案，所以我们将这个值弹出，相当于回溯一下子

    期望得分100pts

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #define int long long
    using namespace std;
    const int maxn=500005;
    int n,fa[maxn],ans;
    int st[maxn],don[maxn],sum[maxn],size;
    bool flag=true;
    char s[maxn];
    struct edge{
    	int e,next;
    }ed[maxn<<1];
    int en,first[maxn];
    void add_edge(int s,int e)
    {
    	en++;
    	ed[en].next=first[s];
    	first[s]=en;
    	ed[en].e=e;
    }


    void dfs(int x)
    {
    	int tmp=0;
    	if(s[x]==')')
    	{
    		if(size!=0)
    		{
    			tmp=st[size];
    			don[x]=don[fa[tmp]]+1;
    			size--;
    		}
    	}
    	else if(s[x]=='(')
    	st[++size]=x;
    	sum[x]=sum[fa[x]]+don[x];
    	for(int i=first[x];i;i=ed[i].next)
    	{
    		int e=ed[i].e;
    		dfs(e);
    	}
    	if(tmp!=0)
    	st[++size]=tmp;
    	else if(size)
    	size--;
    }

    bool check(int l,int r)
    {
    	int cnt=0;
    	for(int i=l;i<=r;i++)
    	{
    		if(s[i]=='(') cnt++;
    		else if(s[i]==')') cnt--;
    		if(cnt<0) return false;
    	}
    	if(cnt==0) return true;
    	return false;
    }
    signed main()
    {
    	cin>>n;
    	scanf("%s",s+1);
    	for(int i=2;i<=n;i++)
    	{
    		int x;
    		cin>>x;
    		add_edge(x,i);
    		fa[i]=x;
    	}
    	dfs(1);
    	for(int i=1;i<=n;i++)
    	ans=(ans^(i*sum[i]));
    	cout<<ans<<'\n';
    	return 0;
    }