1 条题解

  • 0
    @ 2026-2-21 0:21:01
    #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
    上传者