1153C 括号序列

https://codeforces.com/contest/1153/problem/C

题目大意:给出1个带有'(',')','?'三种字符的序列，可以将?转换为)或(

若存在转换后的护法序列为'(xxxxxx)'则打印，不存在则输出':('

思路:

学到了一个思路把'('转换为+1,')'转换为-1,

对于一个合法序列[1,n]，任意前缀和[1,i]>=0,i∈[1,i-1],且前缀和[1,n]=0

于是记录在序列中有a个(,b个),c个?,设c中有x个变成(,y个变成)

由于x+y=c,x+a=y+b,算出x,y其中x,y∈[0,c]，如果超出这个范围，就说明c不够，序列不存在了

根据贪心思想，为了不让前缀和[1,i]小于0，就把前面x个?变成(,后面的变成)

如果中途还是遇到了L[1,i]<0或者最后L[1,n]!=0,那就没办法了，就只有不可能了

代码:

//Problem:
//Date:
//Skill:
//Bug:
/Definations/
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n)  for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//输入输出
#define PII pair<int,int>
#define PB push_back
#define x first
#define y second
using namespace std;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
Options//
typedef long long ll;
#define stdcpph
#define CPP_IO

#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
Basic Functions//
template<typename INint>
inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint>
inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
Added Functions//
const int maxn = int(3e5+10);
int a[maxn];
int n1, n_1, n0;
int ok(int n)
{
	if (n & 1)return 0;
	if (a[1] == -1 || a[n] == 1)return 0;
	a[1] = 1; a[n] = -1;
	F(i, 2, n - 1)
		a[i] == 0 ? ++n0 : (a[i] == 1 ? ++n1 : ++n_1);
	int zuo = (n0 + n_1 - n1) / 2;
	int you = n0 - zuo;
	int c1(0);
	int cnt(0);
	F(i, 2, n - 1)
	{
		if (a[i] == 0)
		{
			if (c1 < zuo)
			{
				++c1; a[i] = 1;
			}
			else a[i] = -1;
		}
		cnt += a[i];
		if (cnt < 0)return 0;
	}
	if (cnt != 0)return 0;
}
Code/
int main()
{
	//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	int T(1), times(0);
#ifdef CPP_IO// CPP_IO
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//cin >> T;
#else
	//IN(T);
#endif 
	/
	while (++times, T--)
	{
		int n; cin >> n;
		RE2(i, n)
		{
			char t; cin >> t;
			a[i] = (t == '(') ? 1 : (t == ')' ? -1 : 0);
		}
		if (ok(n))
		{
			RE2(i, n)
				cout << (a[i] == 1 ? '(' : ')') ;
		}
		else cout << ":(" << endl;
	}
	///
	return 0;
}