C/C++教程

CF1149C 题解

本文主要是介绍CF1149C 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

(Link,Div1,2700)

首先把边上的括号序转换成不完整的点上括号序:把每条边上的括号下放到它所指向的儿子处,题设序列就变成了“从根节点开始遍历整棵树,除根结点外,每开始访问和结束访问某个结点的子树时分别将一个 ( 和一个 ) 添加至序列末尾”所最终形成的括号序。借鉴树上莫队的方式方法可知这个括号序的子串们 去掉匹配括号后的长度(以下简称“去匹长”)可以满射到树上任意一条路径的长度,且它们相等(实际上是子串去掉匹配括号后可以直接满射到路径上,感性理解):

\[\forall u\in[1,n]\land v\in[1,n]\land u\le v,\exist i\in[1,2n-2]\land j\in [1,2n-2]\land i\le j,f((i,j))=(u,v) \]

其中 \(f\) 是一种奇怪的映射,具体可以访问这篇blog中的【树上莫队】篇内容。

于是树的直径变成了【子串们去匹长的最大值】。这东西很难看,考虑具象化,赋予每个 ( \(1\) 的权值以及每个 ) \(-1\) 的权值,一个串的去匹长转化为把这个串分成两段(均可以为空)后 后面一段的权值和减去前面一段的权值和 的最大值:

\[\operatorname{len\_extract\_match}(t)=\max_{i=0}^{|t|} \left(\sum_{j=i+1}^{|t|} val(t_j)\right)-\left(\sum_{j=1}^i val(t_j)\right) \]

这个仍然可以感性理解,分出来的后面那段要放尽量多的 ( 也就是权值尽量大,前面那段要放尽量多的 ) 也就是权值尽量小,加减的过程中匹配的 () 会被自动消掉。

外面再套上一层 \(\max\),求出一个串 \(S\) 的任意一个子串 \(t\) 去匹长的最大值:

\[\operatorname{max\_substr\_len\_extract\_match}(S)=\max_{t\in substr(S)} \max_{i=0}^{|t|} \left(\sum_{j=i+1}^{|t|} val(t_j)\right)-\left(\sum_{j=1}^i val(t_j)\right)\\ =\max_{i=0}^{|S|} \left(\sum_{j=i+1}^{|S|} val(S_j)\right)-\left(\sum_{j=1}^i val(S_j)\right) \]

做到这一步题目中 swap 已经没有任何性质了,线段树维护然后模拟之即可。

重头戏来了。每个结点需要维护 \(7\) 个值(设其维护的区间为 \([l,r]\)):

  • ans,该结点答案,即 \([l,r]\) 这个子串的所有子串们去匹长的最大值;
  • whans,用上 \([l,r]\) 这个子串的所有位置组成串的去匹长,也就是 \([l,r]\) 这个子串的去匹长;
  • lans,包含 \(l\) 这个位置的 \([l,r]\) 的子串的去匹长的最大值,即前缀最大去匹长;
  • rans,包含 \(r\) 这个位置的 \([l,r]\) 的子串的去匹长的最大值,即后缀最大去匹长;
  • sum,\([l,r]\) 的权值和;
  • lmx,\([l,r]\) 中包含 \(l\) 这个位置的 \([l,r]\) 的子串的权值和最大值,即前缀最大权值和;
  • rmx,\([l,r]\) 中包含 \(r\) 这个位置的 \([l,r]\) 的子串的权值和最大值,即后缀最大权值和。

剩下的就是如何 pushup 了,十分的简单,简单到笔者在赛时AC本题的 dalao 的帮助下调了6h:

void updata(int x){
    ans(x)=max(max(ans(ls(x)),ans(rs(x))),
               max(lans(rs(x))-min(rmn(ls(x)),0),rans(ls(x))+max(lmx(rs(x)),0)));
    whans(x)=max(whans(ls(x))+sum(rs(x)),whans(rs(x))-sum(ls(x)));
    lans(x)=max(lans(ls(x)),max(whans(ls(x))+max(lmx(rs(x)),0),lans(rs(x))-sum(ls(x))));
    rans(x)=max(rans(rs(x)),max(whans(rs(x))-min(rmn(ls(x)),0),rans(ls(x))+sum(rs(x))));
    sum(x)=sum(ls(x))+sum(rs(x));
    lmx(x)=max(lmx(ls(x)),sum(ls(x))+lmx(rs(x)));
    rmn(x)=min(rmn(rs(x)),sum(rs(x))+rmn(ls(x)));
}
这篇关于CF1149C 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!