hdu 4915 Parenthese sequence

Parenthese sequence

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

Total Submission(s): 458    Accepted Submission(s): 207

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 1s 2…s n (1≤n≤10 6).  

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
        

題意：？可以變成（或）存在括号配對的情況是無，唯一還是多種

解法：

第一遍預處理：隻計算到i這個位置之前（和？号可以變成）的情況，如果一個問号可以變成）那麼就把？變成），如果不行就變成（，一下三種情況

1. 有（在前面出現那麼？可以變成）

2  （已經被比對完了，那麼？隻能變成（--------最左邊的？隻能變成（

3 （被比對完了，現在還遇到了），那麼以前變成）的？就要變成（，那麼就多出兩個（，于是用一個（比對目前）就可以了

如果（，？都沒有，說明無解，當然字元串的長度為奇數，也必然無解

這一遍預處理可以得到的結果是是否存在解，以及沒個位置得到的情況。

第二遍從右往左掃描，把？都與）進行比對。

方法與第一遍一樣，

然後得到一個？變成（的個數，以及）的個數

以這個字元的左邊作為切割點，把兩側的（和）比對完，如果有一側的（或）多出來了，那麼就把另一側的變成括号的？變成另一種括号

現在隻剩下這條切割線左右兩側分别變成）和（的？個數了。

如果數量都大于0，那麼可以把這兩個？都變成相反的括号，那麼已然還是比對的，這個時候就知道了括号比對的結果不是唯一的了。

原因：

解存在的情況比較顯然，

多解的情況是有兩個？是連續的----連續的意思是中間的（）？可以達成一個比對，

而且這兩個問号變成（），）（都是允許的，就存在多解。而且左邊的？因為其左邊有（是以之前變成），右邊也是一樣，是以改變方向不會出錯

同時因為最左邊和最右邊的？都變成了相應的）（，于是這兩個？改變是可行的，

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 1000007
int wen[maxn],kuo[maxn];
char word[maxn];
int work(int len){
    if(len % 2==1)return 0;
    int i;
    kuo[0] = wen[0] = 0;
    for(i=0;i<len;i++){
        if(i > 0)wen[i] = wen[i-1],kuo[i]=kuo[i-1];
        if(word[i]=='(')kuo[i]++;
        else if(word[i]=='?'){
            if(kuo[i]>0){wen[i]++;kuo[i]--;}
            else kuo[i]++;
        }
        else {
            if(kuo[i] > 0) kuo[i]--;
            else if(wen[i]>0)wen[i]--,kuo[i]++;
            else return 0;
        }
    }
    if(kuo[i-1] > 0) return 0;
    return 1;
}

int work2(int len){
    int i,a=0,b=0,c=0,d;
    for(i=len-1;i>0;i--){
        if(word[i]==')')a++;
        else if(word[i]=='?'){
            if(a>0)a--,b++;
            else a++;
        }
        else {
            if(a>0)a--;
            else if(b>0)a++,b--;
            else return 0;
        }
        c = a-kuo[i-1];
        if(c >= 0){
            d = b-c/2;
            if(d>0&&wen[i-1]>0)return 2;
        }
        else {
            d=wen[i-1]+c/2;
            if(d>0&&b>0)return 2;
        }
    }
    return 1;
}
int main(){
    while(scanf("%s",word)!=EOF){
        int len = strlen(word);
        int ans = work(len);
        if(ans == 0) {printf("None\n");continue;}
        ans = work2(len);
        if(ans == 1)printf("Unique\n");
        else printf("Many\n");
    }
    return 0;
}



/*

??
????
(??
((??))
?()?
?(?()?
?()(?)
((((
((()
(((?
((??
((?)
(()?
(())
(???
(??)
(?)?
(?))
))))
*/