专栏文章

题解：P14172 【MX-X23-T2】括号串

YYGBC_
P14172题解参与者 15已保存评论 15

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
15 条
当前快照
1 份
快照标识符
@minogelp
此快照首次捕获于
2025/12/02 05:44
3 个月前
此快照最后确认于
2025/12/02 05:44
3 个月前
查看原文

P14172 括号串 题解

题意简述

对于一个括号串 ss ，可以将连续的 )( 转化为 () ，判断 ss 在能否在修改后合法（或者是本身合法）。

解法

对于顺序匹配的问题，考虑用栈维护。
假设 ss 为合法括号串，我们可以使用一个栈 stst 维护，栈中存储一个对，记下括号在串中的位置，以及括号类型，将 ( 记为 11，) 记为 00。顺序遍历整个串，对于串中的括号 (，直接压入栈中；对于括号 ) ,检查栈顶是否有配对的 (，如果有，就一并弹出栈。
接下来考虑能将相邻两个括号 )( 改成 () 情况。我们发现如果存在能将 )( 改成 () 使括号串合法的情况，除去相邻的 )(，剩下的部分一定是合法的，而合法的部分一定在栈操作中被抵消。
所以我们可以检查栈，如果栈中只存在连续的 )( 我们便认定这个串在修改后是合法的。
出入栈操作复杂度 O(n)O(n)，检查栈复杂度 O(n)O(n)，总时间复杂度 O(n)O(n)。
AC Code:
CPP
#include<bits/stdc++.h>
#define pib pair<int,bool>
#define fi first
#define se second
#define mp make_pair
using namespace std;

int T;

void solve(){
	int N;
	string s;
	stack<pib> st;
	cin>>N>>s;
	if(N%2){
		cout<<"No\n";          //对于奇数串进行特判，以免最后检查时出错 
		return ;
	}
	for(int i=0;i<N;i++){
		if(s[i]==')'){
			if(st.empty()) st.push(mp(i,0));
			else{
				if(st.top().se) st.pop();
				else st.push(mp(i,0));
			}                 //对于反过来的括号进行配对检查 
		}
		else st.push(mp(i,1));
	}
	while(st.size()>=2){
		pib nw=st.top();
		st.pop();
		if((nw.se^st.top().se)&&(nw.fi==st.top().fi+1)) st.pop();    //检查连续的 ')(' 是否可以修改
		else{
			cout<<"No\n";
			return ;
		}   
	}                         //对于栈中剩下的括号进行检查 
	cout<<"Yes\n";            //如果全部匹配或是栈为空（本身合法），输出 "Yes" 
}

int main()
{
	cin>>T;
	while(T--) solve();
    return 0;
}
（本人的第一个题解，求轻喷，不懂可以私信问。）

评论

共 15 条评论，欢迎与作者交流。

正在加载评论...