比赛的时候没想出来,主要卡在了判Many那。后来看到有人说尝试反向最中间两个?(如果有) 如果还成立,那么就是Many。最开始判的时候(括号尽量选左边,)括号尽量选右边,然后就没了
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1e6+100;
char str[maxn];
int n;
int main()
{
while(scanf("%s",str)!=EOF)
{
n=strlen(str);
if((n&1)||str[0]==')'||str[n-1]=='(')
{
printf("None\n");
continue;
}
str[0]='(';
str[n-1]=')';
int cntw=0,num=0;
for(int i=0;i<n;i++)
{
if(str[i]=='?')
cntw++;
else if(str[i]=='(')
num++;
else
num--;
}
if(num<0)
num=(cntw+num)/2+(-num);
else
num=(cntw-num)/2;
bool is=true,first=true;
int cnt=0,cntx=0,last=0;
for(int i=0;i<n;i++)
{
if(str[i]=='?')
{
if(cntx<num)
{
cnt++;
last=i;
str[i]='(';
}
else
{
if(first&&last!=-1)
{
str[i]='(';
str[last]=')';
first=false;
}
else
str[i]=')';
cnt--;
}
cntx++;
}
else if(str[i]=='(')
cnt++;
else
cnt--;
if(cnt<0)
{
is=false;
break;
}
}
if(cnt)
is=false;
if(!is)
{
printf("None\n");
continue;
}
if((!first)&&last!=-1)
{
is=true;
cnt=0;
for(int i=0;i<n;i++)
{
if(str[i]=='(')
cnt++;
else
cnt--;
if(cnt<0)
{
is=false;
break;
}
}
if(cnt)
is=false;
if(is)
{
printf("Many\n");
continue;
}
}
printf("Unique\n");
}
return 0;
}