题解：洛谷 P3015 [USACO11FEB] Best Parenthesis S

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P3015 [USACO11FEB] Best Parenthesis S

【题目描述】

给定一个只包含左右括号的字符串，得分规则如下：

如果一对括号内没有括号，那么这对括号的得分为1；如果两对括号互不包含（即并列存在），那这两对括号的得分相加；如果括号内包含一对括号，那么这个括号的得分记为内部括号序列的得分× 2 \times 2×2。

例如：对于这样一个字符串：() ()，两对括号并列存在，则得分为1 + 1 = 2 1+1=21+1=2;

而对于这样一个字符串：(())，最外层的括号内层包含一对括号，则得分为2 × 1 = 2 2 \times 1 = 22×1=2。

Bessie 想击败所有同事的牛，所以她需要计算某个字符串的评分。给定一个长度为n nn、只包含括号的字符串（2 ≤ N ≤ 100000 2 \le N \le 1000002≤N≤100000），计算其得分帮助 Bessie。

【输入】

第一行，输入一个整数n nn。
接下来n nn行，每行一个数字，如果是0 00，表示这个字符是(；如果是1 11，表示这个字符是)。

【输出】

字符串的分数，由于数字可能会变得很大，所以对12345678910 1234567891012345678910取模。

【输入样例】

6 0 0 1 1 0 1

【输出样例】

3

【核心思想】

1. 问题分析：给定一个长度为N NN（N ≤ 10 5 N \le 10^5N≤105）的括号序列，其中字符0代表左括号(，字符1代表右括号)。根据规则计算得分：空括号()得1 11分；并列括号得分相加；嵌套括号的得分为内部得分× 2 \times 2×2。需要对结果取模12345678910 1234567891012345678910。本质是括号匹配与树形结构计算问题，可以用栈模拟括号的嵌套和并列关系。

2. 算法选择：

   • 栈模拟：维护一个栈，每个元素存储当前层的累计得分和是否包含过括号的标记。遇到左括号时压入新层（得分 0，标记 false）；遇到右括号时弹出栈顶，计算当前括号对的得分：
     • 若该层内部未包含括号（标记为 false），则当前括号对为空，得分为1 11。
     • 若内部包含括号，则得分为内部得分 * 2。
   • 然后将当前括号对的得分加到新的栈顶元素的累计得分中（表示并列相加），并标记新栈顶为已包含括号。
   • 最后栈底元素即为总得分。

3. 关键步骤：

   • 读入与转换：读取N NN，逐个读入数字（0 或 1）。
   • 栈初始化：stk.push({0, false})，作为总得分的容器。
   • 处理左括号（0）：压入新层{0, false}。
   • 处理右括号（1）：
     • 弹出栈顶cur。
     • 计算当前层得分：score = cur.second ? (2 * cur.first) % mod : 1。
     • 将score加到当前栈顶的累计得分上：stk.top().first = (stk.top().first + score) % mod。
     • 标记当前栈顶为包含括号：stk.top().second = true。
   • 输出：栈底元素的first即为答案。

4. 时间/空间复杂度：

   • 时间复杂度：O ( N ) O(N)O(N)，每个字符入栈或出栈一次。
   • 空间复杂度：O ( N ) O(N)O(N)，栈在最坏情况下存储N NN个元素。

5. 栈模拟括号树的核心思想：

   • 括号层次结构：括号序列天然形成一棵树，每对括号是一个节点，并列关系对应兄弟节点，嵌套关系对应父子节点。
   • 栈的层叠性：用栈的压入和弹出模拟树的深度优先遍历，每个栈帧存储当前节点的累计得分和是否包含子节点。
   • 得分规则转换：空括号()对应叶子节点，得分为 1；嵌套括号对应父节点，得分为子节点得分 * 2；并列括号对应兄弟节点，得分相加。
   • 取模处理：由于得分可能极大，每次加法后立即对12345678910 1234567891012345678910取模。
   • 适用场景：适用于括号序列的解析和计算，特别是涉及嵌套和并列复杂度的表达式求值。

【算法标签】

#普及 #栈

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintmod=12345678910;// 取模数intn;stack<pair<int,bool>>stk;// 栈元素：first为当前段累计得分，second表示该段内是否已经包含括号signedmain(){cin>>n;// 栈底放入一个初始元素，作为最终总得分的容器stk.push({0,false});// 逐个读入字符：0 代表 '('，1 代表 ')'for(inti=1;i<=n;i++){intx;cin>>x;// 左括号：压入新的一层，初始得分0，且尚未包含内部括号if(x==0){stk.push({0,false});}// 右括号：处理当前最内层括号else{autocur=stk.top();// 当前层（被右括号闭合的括号对）stk.pop();// 如果该层内部已经包含括号（即 cur.second == true），// 则当前括号对的得分为内部得分乘以2；// 否则该括号对为空，得分为1intscore=cur.second?(2*cur.first):1;// 将当前括号对的得分加入到外层（新栈顶）的累计得分中，// 因为并列括号得分相加stk.top().first=(stk.top().first+score)%mod;// 标记外层已经包含了至少一个括号（即内部不为空）stk.top().second=true;}}// 栈底元素存储了整个字符串的总得分cout<<stk.top().first<<endl;return0;}

【运行结果】

6 0 0 1 1 0 1 3