hdu 4915 Parenthese sequence（模拟）2014多培训学校5现场

Parenthese sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

Problem Description

bobo found an ancient string. The string contains only three charaters -- "(", ")" and "?".

bobo would like to replace each "?

" with "(" or ")" so that the string is valid (defined as follows). Check if the way of replacement can be uniquely determined.

Note:

An empty string is valid.
If S is valid, (S) is valid.
If U,V are valid, UV is valid.

Input

The input consists of several tests. For each tests:

A string s₁s₂…s_n (1≤n≤10⁶).

Output

For each tests:

If there is unique valid string, print "Unique". If there are no valid strings at all, print "None". Otherwise, print "Many".

Sample Input

??
?
???
(??

Sample Output

Unique
Many
None

题意：输入一个长度不超过10^6的字符串，串中仅仅包括‘（’、‘）’、‘?’。当中‘?

’既能够当做’（‘，又能够当做’）‘，求有多少种方法满足括号匹配。假设不能匹配，输出“None”；假设仅仅有一种，输出“Unique”；否则输出“Many”。

分析：假设没有‘?’。问题就变成了简单的括号匹配。这个非常好推断；

每次遇到一个‘?

’，我们能够先把这个‘?’变成‘（’，推断是否匹配。再把‘?

’变成')',推断是否匹配。

假设都匹配，则有多种匹配方法。

假设都不匹配，则无法匹配；

假设仅仅有一个匹配，则把这个‘?’变成使之匹配的括号，然后继续推断下一个‘?'就可以。

#include<cstdio>
#include<cstring>
const int N = 1e6 + 50;
char str[N], s[N];
int len;
int judge() //推断当前的字符串是否匹配
{
    int l = 0;  //记录左括号的数量
    int r = 0;  //记录右括号的数量
    int num = 0;  //记录已经遍历过的字符数量
    int i;
    for(i = 0; i < len; i++)  //从前往后推断
    {
        num++;
        if(num == 1)
        {
            if(s[i] == '?')
                s[i] = '(';
        }
        if(s[i] == '(') l++;
        else if(s[i] == ')') r++;
        if(r > num/2)  //右括号数量太多。无法全然匹配
            return 0;
        if(r * 2 == num)  //前num个能够全然匹配
        {
            l = r = num = 0;
        }
    }
    if(l > num/2) return 0;
    
    num = l = r = 0;
    for(i = len - 1; i >= 0; i--)  //从后往前推断
    {
        num++;
        if(num == 1)
        {
            if(s[i] == '?
')
                s[i] = ')';
        }
        if(s[i] == '(') l++;
        else if(s[i] == ')') r++;
        if(l > num / 2) return 0;  //左括号数量太多，无法全然匹配
        if(l * 2 == num)  //后num个能够全然匹配
        {
            l = r = num = 0;
        }
    }
    if(r > num/2) return 0;
    
    return 1;
}
int main()
{
    int flag_l, flag_r, i;
    while(~scanf("%s",str))
    {
        len = strlen(str);
        if(len & 1)
        {
            printf("None
");
            continue;
        }

        strcpy(s, str);
        flag_l = judge();  //如果没有 '?
'，推断是否匹配

        if(!flag_l)
        {
            printf("None
");
            continue;
        }
        for(i = 0; i < len; i++)
        {
            if(str[i] == '?')
            {
                strcpy(s, str);

                s[i] = ')';
                flag_l = judge();

                s[i] = '(';
                flag_r = judge();

                if(flag_l && flag_r)
                {
                    printf("Many
");
                    break;
                }
                if(!flag_l && !flag_r)
                {
                    printf("None
");
                    break;
                }
                if(flag_l && !flag_r)
                    s[i] = ')';
                else if(!flag_l && flag_r)
                    s[i] = '(';
            }
        }
        if(i == len)
            printf("Unique
");
    }
    return 0;
}