求调,56
  • 板块P1241 括号序列
  • 楼主1Stone
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/7/24 07:12
  • 上次更新2023/10/27 18:42:22
查看原帖
求调,56
648953
1Stone楼主2022/7/24 07:12
#include<bits/stdc++.h>
using namespace std;
int a[100868];
bool vs[100086];
void dfs(int l,int r,int k){
	int pl=-1,pr=-1;	
	for(int i=l;i<=r;i++){
		if(vs[i]==0&&a[i]==k)pl=i;
	}
	for(int i=r;i>=l;i--)if(vs[i]==0&&a[i]==k+2)pr=i;
	if(pl==-1&&pr==-1){
		return;
	}
	if(pl!=-1&&pr==-1){
		vs[pl]=1;
		a[pl]+=4;
		dfs(l,r,k);
	}
	if(pl==-1&&pr!=-1){
		vs[pr]=1;
		a[pr]+=2;
		dfs(l,r,k);
	}
	if(pl!=-1&&pr!=-1){
		if(pl<pr){
			vs[pl]=1;
			vs[pr]=1;	
			if(k==1)k=2;
			else k=1;
			dfs(pl+1,pr-1,k);
			if(k==1)k=2;
			else k=1;
			dfs(pr,r,k);
			dfs(l,pl,k);
		}
		if(pr<pl){
			dfs(l,pr,k);
			dfs(pr+1,pl-1,k);
			dfs(pl,r,k);
		}
	}
}
string s;
int main(){
	cin>>s;
	s=" "+s;
	for(int i=1;i<s.size();i++){
		if(s[i]=='('){
			a[i]=2;
		}
		if(s[i]==')'){
			a[i]=4;
		}
		if(s[i]=='['){
			a[i]=1;
		}
		if(s[i]==']'){
			a[i]=3;
		}
	}
	dfs(1,s.size()-1,2);
	dfs(1,s.size()-1,1);
	for(int i=1;i<s.size();i++){
		if(a[i]==2){
			cout<<"(";
		}
		if(a[i]==4){
			cout<<")";
		}
		if(a[i]==6){
			cout<<"()";
		}
		if(a[i]==1)cout<<"[";
		if(a[i]==3)cout<<"]";
		if(a[i]==5)cout<<"[]";
	}
	
	return 0;
}
2022/7/24 07:12
加载中...