题解：CF2143E Make Good

题目：洛谷 || CF

怎么是简单题啊/崇拜

题目分析

考虑两种操作可以让我们干什么：

将 )) 替换为 ((。

我们先将所有 )) 替换为 ((。这样就可以得到 ..()(...()(... 这样的东西。

考虑一个 )，假设它右边是 ((，那么我们可以把它右移两位（)((

\to

)))

\to

(()）。

考虑两个 ) 会发生什么。比如说 )(()，这时我们可以把中间两个翻转一下，变成 ))))，然后再把左边两个和右边两个翻转，变成 ((((。

所以我们得到：

可以将两个中间括号个数为偶数的 ) 都替换成 (。
可以将 ) 在不越过其他 ) 的时候移动偶数位。

于是我们维护哪些位置的 ) 是不能变的。可以用一个栈维护，如果栈顶与当前之间的括号个数为偶数，那么就都弹出，否则加入。

然后开始构造。由于要构造括号序列，就贪心地将 ) 往后放。不妨先把所有 ) 移到左边，这时右边都是 ...(((( 的形式，从右往左翻转直到总右括号数量为

n/2

为止。

为什么要假定把 ) 移到左边：比如 (()(((，直接是不能把 ( 右移成 (((()(，这样会非常难解决；但如果我们先把它转化成 )((((( 这样就可以贪心在右边填 ))。

然后再把所有左边的 ) 尽可能移到右边就行了。

最后可能还要再判下是否合法。根据实现决定吧。

Code

~~自认为实现比较高妙（）~~

CPP

// by wangyizhi(571247)
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//bool Mst;
using namespace std;
namespace wyzfastio{}
using namespace wyzfastio;
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
const int N=2e5+5;
int a[N];
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
//	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	int t;read(t);
	while(t--) [&]()->void
	{
		int n;string s;
		read(n,s);
		for(int i=0;i<=n+1;i++) a[i]=0;
		stack<int> stk;
		for(int i=0;i<n;i++) if(s[i]==')')
		{
			if(stk.size()&&(i-stk.top())&1) stk.pop();
			else stk.push(i);
		}
		for(int i=n,j=1;j<=(n/2-(int)stk.size())/2*2;i--,j++) a[i]=1;
		for(int lst=n-(n/2-(int)stk.size())+1;stk.size();)
		{
			if((lst^stk.top())&1) {if(lst>2)a[lst-=2]=1;}
			else {if(lst>1)a[lst-=1]=1;}
			stk.pop();
		}
		int p=0;
		for(int i=1;i<=n;i++) if((p+=a[i]?-1:1)<0) return write("-1\n"),void();
		if(p) return write("-1\n"),void();
		for(int i=1;i<=n;i++) write(a[i]?')':'(');
		write('\n');
	}();
	return 0;
}

题解：CF2143E Make Good

文章操作

题目分析

Code

相关推荐

评论

题解：CF2143E Make Good