题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4915
解题报告：从前往后遍历一次，每次判断')'的数目是不是满足 n < (i +1)/ 2，从后往前遍历一次，每次判断'('的数目是不是满足 n <= (len - i) / 2;
这样就可以判断出这个序列是否存在匹配的序列。接下来就是判断是Many还是Unique的情况，因为数据是10的六次方，所以遇到问号改成'(' 或')'暴力判断是不行的，但是我们可以判断出只要(和)的数目小于等于len / 2而且有三个连续的?那句是Many，否则再进行暴力判断，这样就可以大大减小时间复杂度。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = +;
char str[maxn]; int judge(char* str)
{
int len = strlen(str);
int a = ,b = ;
for(int i = ,j = len- ;i < len,j >= ;++i,--j)
{
if(str[i] == ')') a++;
if(str[j] == '(') b++;
if(a > (i + ) / ) return ;
if(b > (len - j) / ) return ;
}
return ;
}
int main()
{
// freopen("1005.in","r",stdin);
int T = ;
while(scanf("%s",str)!=EOF)
{
T++;
int ans;
ans = judge(str);
int l = strlen(str);
if(l & ) ans = ;
if(!ans)
{
puts("None");
continue;
}
int len = strlen(str);
int a = ,b = ,c = ,f = ,M = ;
for(int i = ;i < len;++i)
{
if(str[i] == '(') a++;
if(str[i] == ')') b++;
if(str[i] == '?')
{
f++;
c++;
}
else
{
M = max(M,f);
f = ;
}
}
if(a >= len / || b >= len / || c <= )
{
puts("Unique");
continue;
}
if(M >= )
{
puts("Many");
continue;
}
ans = ;
for(int i = ;i < len;++i)
if(str[i] == '?')
{
int tt = ;
str[i] = '(';
tt += judge(str);
str[i] = ')';
tt += judge(str);
if(tt == )
{
ans = ;
break;
}
str[i] = '?';
}
printf(ans? "Many\n":"Unique\n");
}
return ;
}