**题意:
问你括号匹配是否唯一,三种字符'(','?',')',问号可以变成任何字符。
思路:
首先我们要学会判断当前串是否成立?怎么判断?我的方法是跑两遍,开三个变变量
**
s1 s2 s3 分别存(?)他们三个的当前个数,然后先正着跑,只要s1 + s2 < s3那么就不成立,然后在倒着跑只要 s3 + s2 < s1也不成立,如果两变跑完了都成立,那么当前的串就是成立的,对于怎么判断他的唯一性,我采用的是暴力的方法,每次遇到"?"就把他变成(和)如果两个都满足。那么就直接是多组解,不然继续找下一个问号,还有就是我真心觉得这么做会超时的,虽然AC了,可能是数据水。
#include
#include
#include
using namespace std**;
char** str[1000010**];
bool** ok()
{
int s1 ,s2 ,s3 ,mk ,l ,i;
l = strlen(str);
s1 = s2 = s3 = 0;
for(i = 0 ;i < l;i ++)
{
if(str[i] == '(') s1 ++;
if(str[i] == '?') s2 ++;
if(str[i] == ')') s3 ++;
if(s1 + s2 < s3) return 0;
}
s1 = s2 = s3 = 0;
for(i = l - 1 ;i >= 0;i --)
{
if(str[i] == '(') s1 ++;
if(str[i] == '?') s2 ++;
if(str[i] == ')') s3 ++;
if(s2 + s3 < s1)return 0;
}
return 1**;
}
int main ()
{
int** mk1 ,mk2 ,l ,mk ,i;
while(~scanf("%s" ,str))
{
l = strlen(str);
if(l % 2) {puts("None");continue;}
if(!ok()) {puts("None");continue;}
for(mk = i = 0 ;i < l && !mk ;i ++)
{
if(str[i] == '?')
{
str[i] = '(';
ok()? mk1 = 1 : mk1 = 0;
str[i] = ')';
ok()? mk2 = 1 : mk2 = 0;
str[i] = '?';
if(mk1 && mk2) mk = 1;
}
}
mk ? puts("Many"): puts("Unique");
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章