本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P3015 [USACO11FEB] Best Parenthesis S【题目描述】给定一个只包含左右括号的字符串得分规则如下如果一对括号内没有括号那么这对括号的得分为1如果两对括号互不包含即并列存在那这两对括号的得分相加如果括号内包含一对括号那么这个括号的得分记为内部括号序列的得分× 2 \times 2×2。例如对于这样一个字符串() ()两对括号并列存在则得分为1 1 2 112112;而对于这样一个字符串(())最外层的括号内层包含一对括号则得分为2 × 1 2 2 \times 1 22×12。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【核心思想】问题分析给定一个长度为N NNN ≤ 10 5 N \le 10^5N≤105的括号序列其中字符0代表左括号(字符1代表右括号)。根据规则计算得分空括号()得1 11分并列括号得分相加嵌套括号的得分为内部得分× 2 \times 2×2。需要对结果取模12345678910 1234567891012345678910。本质是括号匹配与树形结构计算问题可以用栈模拟括号的嵌套和并列关系。算法选择栈模拟维护一个栈每个元素存储当前层的累计得分和是否包含过括号的标记。遇到左括号时压入新层得分 0标记 false遇到右括号时弹出栈顶计算当前括号对的得分若该层内部未包含括号标记为 false则当前括号对为空得分为1 11。若内部包含括号则得分为内部得分 * 2。然后将当前括号对的得分加到新的栈顶元素的累计得分中表示并列相加并标记新栈顶为已包含括号。最后栈底元素即为总得分。关键步骤读入与转换读取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即为答案。时间/空间复杂度时间复杂度O ( N ) O(N)O(N)每个字符入栈或出栈一次。空间复杂度O ( N ) O(N)O(N)栈在最坏情况下存储N NN个元素。栈模拟括号树的核心思想括号层次结构括号序列天然形成一棵树每对括号是一个节点并列关系对应兄弟节点嵌套关系对应父子节点。栈的层叠性用栈的压入和弹出模拟树的深度优先遍历每个栈帧存储当前节点的累计得分和是否包含子节点。得分规则转换空括号()对应叶子节点得分为 1嵌套括号对应父节点得分为子节点得分 * 2并列括号对应兄弟节点得分相加。取模处理由于得分可能极大每次加法后立即对12345678910 1234567891012345678910取模。适用场景适用于括号序列的解析和计算特别是涉及嵌套和并列复杂度的表达式求值。【算法标签】#普及 #栈【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintmod12345678910;// 取模数intn;stackpairint,boolstk;// 栈元素first为当前段累计得分second表示该段内是否已经包含括号signedmain(){cinn;// 栈底放入一个初始元素作为最终总得分的容器stk.push({0,false});// 逐个读入字符0 代表 (1 代表 )for(inti1;in;i){intx;cinx;// 左括号压入新的一层初始得分0且尚未包含内部括号if(x0){stk.push({0,false});}// 右括号处理当前最内层括号else{autocurstk.top();// 当前层被右括号闭合的括号对stk.pop();// 如果该层内部已经包含括号即 cur.second true// 则当前括号对的得分为内部得分乘以2// 否则该括号对为空得分为1intscorecur.second?(2*cur.first):1;// 将当前括号对的得分加入到外层新栈顶的累计得分中// 因为并列括号得分相加stk.top().first(stk.top().firstscore)%mod;// 标记外层已经包含了至少一个括号即内部不为空stk.top().secondtrue;}}// 栈底元素存储了整个字符串的总得分coutstk.top().firstendl;return0;}【运行结果】6 0 0 1 1 0 1 3