Tk王国的括号时间限制1秒空间限制1024M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述众所周知我们日常使用的括号如()、[]等但是在遥远的 Tk 王国他们使用字母作为括号。具体地Tk 王国共有 26 种不同的括号对其中前 13 对为az、by、cx、…、lo、mn即小写字母表中的第i ii个字母和第27 − i 27-i27−i个字母下标从 1 开始后 13 对为ZA、YB、XC、…、OL、NM即大写字母表中的第27 − j 27-j27−j个字母和第j jj个字母下标从 1 开始。现在给定一个长度为n nn的字符串s ss字符串由大小写字母构成。你可以重复以下操作任意次如果存在长度为 2 的连续子串且该子串正好是一对上述括号则删除该子串。如果被删除的子串位于开头或结尾则剩余部分直接形成新的字符串否则将被删除子串之前的部分和之后的部分拼接成新的字符串。求经过若干次操作后字符串可能达到的最短长度。输入描述第一行输入一个整数n ( 1 ≤ n ≤ 2 × 10 5 ) n\ (1 \le n \le 2 \times 10^5)n(1≤n≤2×105)表示字符串长度第二行输入一个长度为n nn仅由字母组成的字符串s ss。输出描述输出一个整数表示字符串可以达到的最短长度。示例1输入5 azbyc输出1示例2输入4 evPK输出0解题思路本题是括号匹配消除问题类似用栈处理相邻可配对字符。字符串由大小写字母组成定义了 26 对特殊的括号对每次可以删除相邻且恰好组成一对的两个字符求经过任意次删除后字符串的最短长度。1. 问题等价转化给定字符集某些二元组被视为可消除的“括号对”。操作规则不断寻找相邻的括号对并删除删除后原不相邻的字符可能变成相邻从而可能继续消除。这一过程与“括号匹配”完全一致可使用栈来模拟遍历字符串当前字符若能与栈顶字符组成一对括号则弹出栈顶消除这对括号否则将当前字符压入栈。最终栈中剩余的字符即为无法再消除的部分其长度就是答案。2. 配对规则小写字母对前 13 对为az,by,cx, …,mn。即对于小写字母a aa和b bba b a bab若它们的字母表下标之和为 250‑based则它们是一对。大写字母对后 13 对为ZA,YB,XC, …,NM。即对于大写字母a aa和b bba b a bab若它们的字母表下标之和为 25则它们是一对。判断函数match(a,b)根据大小写和下标和判断。3. 算法步骤读入字符串长度n nn可忽略和字符串s ss。初始化一个空栈t可用字符串模拟。遍历字符串s ss中的每个字符c若栈不为空且match(栈顶字符, c)为真则弹出栈顶否则将c压入栈。输出栈中剩余字符的个数即为最短长度。4. 复杂度分析时间复杂度每个字符至多入栈、出栈一次总复杂度O ( n ) O(n)O(n)n ≤ 2 × 10 5 n \le 2 \times 10^5n≤2×105完全可行。空间复杂度O ( n ) O(n)O(n)用于存储栈。总结本题实质是括号消除利用栈的后进先出特性处理相邻配对。配对规则可通过字母下标之和为 25 且大小写方向固定来统一判断。算法简洁高效只需一次线性扫描。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;boolmatch(chara,charb){if(islower(a))returnab(a-a)(b-a)25;returnab(a-A)(b-A)25;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);string s,t;cinss;for(charc:s){if(t.size()match(t.back(),c))t.pop_back();elset.push_back(c);}coutt.size()endl;return0;}