1 条题解
-
0
#include<bits/stdc++.h> using namespace std; int n , k; // [1] n-字符串长度,k-匹配的括号对数 string s; // [2] s-输入的括号字符串 struct stu{ // [3] stu-栈元素结构体 char c; // 当前字符 int left,right; // 左括号计数、右括号计数(相对于当前连续段) }; int main(){ cin >> n >> k; // [4] 读入n和k cin >> s; // [5] 读入字符串s stack<stu> v; // [6] v-模拟栈,存放字符及连续计数 // [7] 遍历字符串每个字符,模拟删除k-括号匹配的过程 for(int i = 0;i < n;i++) { char a = s[i]; // [8] 当前字符 int l , r; // [9] 待计算的left和right值 // [10] 若栈空,根据当前字符初始化计数 if(v.empty()) { if(a == '(') { l = 1; // 左括号连续数=1 r = 0; // 右括号连续数=0 }else { l = 0; r = 1; } } // [11] 当前为 '(' 且栈非空 else if(s[i] == '(') { // [12] 若栈顶也是 '(',则左括号连续数累加 if(a == v.top().c) { l = v.top().left + 1; r = v.top().right; } // [13] 若栈顶是 ')',则新开连续段 else { l = 1; r = 0; } } // [14] 当前为 ')' 且栈非空 else { // [15] 若栈顶也是 ')',则右括号连续数累加 if(a == v.top().c) { l = v.top().left; r = v.top().right + 1; } // [16] 若栈顶是 '(',则新开连续段(但保留左括号计数?实际上此处逻辑可能有问题,按原代码注释) else { l = v.top().left; // 继承左括号计数 r = 1; // 右括号计数=1 } } v.push({a , l , r}); // [17] 将当前字符及其计数压栈 // [18] 检查栈顶是否满足移除条件:左括号连续数>=k 且 右括号连续数==k if(v.top().left >= k && v.top().right == k) { int num = 2*k; // [19] 需移除的字符个数 while(num--) // [20] 循环弹出2k个元素 v.pop(); } } string new_s=""; // [21] 存放栈中剩余字符(逆序) // [22] 将栈中所有字符取出 while(!v.empty()) { new_s += v.top().c; // [23] 追加栈顶字符 v.pop(); // [24] 弹出 } // [25] 逆序输出剩余字符串(因为栈后进先出,new_s是原串的逆序) for(int i = new_s.size() - 1;i >= 0;i--) cout << new_s[i]; return 0; }
信息
- ID
- 1473
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者