P14731 [ICPC 2022 Seoul R] Parentheses Tree 题解

DHEnry

2025 年 12 月 13 日

38 次浏览

暂无评论

777字数

编程 Online Judge 洛谷

## 传送门

[题目](https://www.luogu.com.cn/problem/P14731)
[更好的阅读体验](https://www.fmcraft.top/index.php/archives/222.html)

## 题目大意

读入一个字符串， 匹配括号字符串所表示的树，求根节点到所有叶节点的距离之和。

## 分析题目

- 括号字符串中，每一个叶节点都是对应一个 `()`；
- 字符串中的深度比实际深度大 $1$，需要减去 $1$ 再进行计算；
- 扫描字符串，遇到 `(` 深度 $+1$，否则深度 $-1$；
- 当遇到 `()` 时，当前的深度 $-1$ 就是根节点到此处的距离；
- 时间复杂度为 $O(n)$ 可以通过此题。

## 算法步骤

1. 扫描字符串，记为 $s_i$；
2. 对 $s_i$ 作判断，`(` 和 `)` 需要分情况讨论；
3. 如果遇到 `(`，深度 $+1$，并且，如果下一个字符是 `)` 说明找到了叶节点，将 `深度-1` 记录到答案，需要注意下个字符是否为合法边界；
4. 如果遇到 `)`，深度 $-1$；
5. 输出答案。

## 代码

```cpp
#include <bits/stdc++.h>
#define int long long // 将所有的 int 替换成 long long，否则会爆 int
using namespace std;
string s;
int ans,depth,i;
signed main(){ // 因为 int 会被替换成 long long，但是返回值不允许 long long，所以使用 signed
    cin>>s; // 对应步骤 1
    for(i=0;i<s.length();i++) // 对应步骤 2
        if(s[i]=='('){ // 对应步骤 3 及下面两行
            depth++;
            if(i+1<s.length()&&s[i+1]==')') ans+=depth-1; // 注意 i+1<s.length()，如果当前字符 id +1 比 s 的长度长，那么属于越界操作，不计算
        }else depth--; // 对应步骤 4
    cout<<ans; // 对应步骤 5
}
```

![code.png](https://www.fmcraft.top/usr/uploads/2025/12/2482871496.png)

最后修改：2025 年 12 月 13 日

如果觉得我的文章对你有用，请随意赞赏

P14731 [ICPC 2022 Seoul R] Parentheses Tree 题解

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

IP地址修改器 [bilibili配套]

关于 2025 CSP

个人对于身高歧视的评价

FMCRAFT Res领地插件使用教程【官方 and 非官方】

关于 2025 年浙江省初中名校发展共同体七年级第一学期考试反思

教你快速搭建一个文件快递柜[filecodebox使用教程]

2025年10月12日学校编程集训感言

2025/12/22 to 2025/12/28 周记

关于 2025 CSP

上海市2025CSP-J十连测Round 5卷后感

P14731 [ICPC 2022 Seoul R] Parentheses Tree 题解

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

P14731 [ICPC 2022 Seoul R] Parentheses Tree 题解

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款