贪心构造

首先题目里面保证了必定有一个合法的状态，我们不妨先构造一个出来。

经过某个经典转换，将左右括号分别标为 $+1,-1$，那么一个串合法当且仅当这个串的和为 $0$ 且任意前缀和 $\geq 0$ 。

所以贪心地选择先填写左括号，使得前缀和尽量大即可构造出一个合法串。

然后考虑判断是否能通过改变这个合法串来构造出另一个合法串。

我们肯定是将一个左括号改成右括号，一个右括号改成左括号，相当于转换序列中将一个 $+1$ 转换为 $-1$。而这样做的风险在于会因为某个前面的 $+1$ 改成 $-1$ 导致后面的某个前缀 $<0$。

所以尽可能晚的选择将 $+1$ 改成 $-1$，尽可能早的将 $-1$ 改成 $+1$ 来挽回可能 $<0$ 的前缀。改完以后再判一次是否合法即可。

具体来说就是先给前面的空填上左括号，直到总左括号数等于长度的一半，剩下的空填上右括号以构造第一个合法解，再交换最后一个填左括号的空和第一个填右括号的空以判断是否存在第二个解。另外，如果问号里完全没填某一种括号一定有唯一解。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<cstring>
#define rep(a,b,c) for(int c(a);c<=(b);++c)
#define drep(a,b,c) for(int c(a);c>=(b);--c)
inline int read()
{
	int res=0;char ch=getchar();bool flag=0;while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return flag ? -res : res ;
}
template<typename T> inline T min(const T&x,const T&y){return x<y?x:y;}
template<typename T> inline T max(const T&x,const T&y){return x<y?y:x;}
template<typename T> inline void Swap(T&x,T&y){T tmp=x;x=y;y=tmp;}
const int N=2e5+10;char c[N];int n;int s[N],a[N];
inline void Solve()
{
	scanf("%s",c+1);n=strlen(c+1);
	rep(1,n,i)if(c[i]=='(')a[i]=1;else if(c[i]==')')a[i]=-1;else a[i]=0;
	int sm[2]={0,0};rep(1,n,i)if(c[i]=='(')++sm[0];else if(c[i]==')')++sm[1];
	if(!(n/2-sm[0])||!(n/2-sm[1])){puts("YES");return;}
	int k=0;rep(1,n,i)if(c[i]=='?'&&k<n/2-sm[0]){++k;a[i]=1;}else if(c[i]=='?')a[i]=-1;
	int l=1,r=1;drep(n,1,i)if(c[i]=='?'&&a[i]==1){l=i;break;}
	rep(1,n,i)if(c[i]=='?'&&a[i]==-1){r=i;break;} a[l]=-1;a[r]=1;
	int res=0;rep(1,n,i){res+=a[i];if(res<0){puts("YES");return;}}
	puts("NO");return;
	
}
signed main()
{
	int T=read();
	while(T--)Solve();
}