洛谷 P5658 括号树 题解
简要题意:
求出以从每个节点到根形成的括号序列的合法对数。
算法一
观察到 \(n \leq 8\) ,所以我们可以用 纯粹的暴力 。
用 \(O(n)\) 时间得出当前节点到根的字符串。
然后 \(O(n^2)\) 枚举子串。
再用 \(O(n)\) 暴力判断(用栈)。
时间复杂度: \(O(n^5)\).
实际得分: \(10pts\).
优化一
用 \(s_i\) 表示 \(i\) 号节点对应的括号。
用 \(h_i\) 表示当前节点到根的字符串。
用 \(fa_i\) 表示当前节点的父亲编号。
则:
\]
由此,\(O(1)\) 推出字符串。
然后 \(O(n^2)\) 枚举子串,\(O(n)\) 验证。
时间复杂度: \(O(n^4)\)
实际得分: \(10pts\).
优化二
同样 \(O(1)\) 推出字符串。
下面,我们用 \(f_i\) 表示从第 \(i\) 号节点到根形成的括号序列的合法对数。
那么,显然存在:
\(f_i \geq f_{fa_i}\)
也就是说,我们只需要考虑以 \(i\) 号节点结尾的子串的贡献。
这样,我们枚举子串的时间复杂度降为 \(O(n)\),判断降为 \(O(n)\).
总时间复杂度: \(O(n^3)\)
实际得分:\(20pts\)
优化三
显然,我们需要摆脱枚举子串,而用另一些东西直接维护。
\begin{cases}
h_{fa_i},s_i = \text{(} \\
h_{fa_{g_i}}, s_i = \text{)} \\
\end{cases}
\]
其中, \(g_i\) 表示从当前节点开始,到根的路径上第一个(从下往上数)未匹配的左括号。
如果 \(s_i = \text{(}\) ,显然以当前节点结尾没有合法子串。
如果 \(s_i = \text{)}\) , 则找到它可以匹配的第一个左括号,然后记录那个左括号父亲的值(即前面的值)即可。
那么,\(g_i\) 如何维护呢?
\begin{cases}
i , s_i = \text{(} \\
g_{fa_i} , s_i = \text{)} \\
\end{cases}
\]
这也是显然的。
那么,我们可以做到 \(O(n)\) 时间维护这所有的东西。
总时间复杂度: \(O(n)\).
实际得分: \(100pts\).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+1;
typedef long long ll;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
char s[N];
int n; ll ans;
ll f[N],g[N],fa[N];
vector<int>G[N];
// f[i] 为 当前节点的贡献值
// g[i] 为 从当前节点起,第一个没匹配的左括号的编号
inline void dfs(int dep) {
g[dep]=g[fa[dep]];
if(s[dep]=='(') g[dep]=dep;
else if(g[dep]) f[dep]=f[fa[g[dep]]]+1,g[dep]=g[fa[g[dep]]]; //维护
for(int i=0;i<G[dep].size();i++) dfs(G[dep][i]); //递归下去
}
int main(){
n=read(); scanf("%s",s+1); //一个技巧,让字符串下标从 1 开始
for(int i=2,t;i<=n;i++) {
t=read(); fa[i]=t;
G[t].push_back(i); //存儿子节点编号
} dfs(1);
ans=f[1]; for(int i=2;i<=n;i++)
f[i]+=f[fa[i]],ans^=(i*f[i]); //我们把父亲的值放到最后算,避免出错
printf("%lld\n",ans);
return 0;
}
最新文章
- IE10 和 Chrome50 对日期 new Date() 支持的区别
- GPS部标平台的架构设计(九)-GPS监控客户端设计
- C++注册表操作
- 安装使用RESTful 框架SLIM方法
- 上传按钮样式优化 <;input type=";file"; />;
- hdu 4858 项目管理 图的分块
- 深入理解ob_flush/flush
- MongoDB - The mongo Shell, Configure the mongo Shell
- Ubuntu下非常给力的下载工具
- kettle在linux启动spoon.sh报错
- 使用python制作ArcGIS插件(2)代码编写
- Effective Java 第三版——25. 将源文件限制为单个顶级类
- zookeeper核心-zab协议-《每日五分钟搞定大数据》
- chart API笔记
- 插入排序的Java代码实现
- Luogu4717 【模板】快速沃尔什变换(FWT)
- c# 匿名反序列化
- IO(字节流)
- JSONP跨域访问百度实现搜索提示小案例
- 全球顶尖大学的UX课程资源,英文!