hdu4915 Parenthese sequence 2014 Multi-University Training Contest 5

Parenthese sequence

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

Total Submission(s): 28    Accepted Submission(s): 5

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
        

Source 2014 Multi-University Training Contest 5  

Recommend hujie  

比較麻煩的題，考慮多種情況，首先排除不行的，然後判斷是否能有多個解，比賽的時候有個地方寫錯wa了5次···

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=1000005;
int f1[N],f2[N];
char s[N];
int main(){
    while(scanf("%s",s)!=EOF){
        int l=strlen(s);
        if(l%2){
            printf("None\n");
            continue;
        }
        if(s[0]==')'||s[l-1]=='('){
            printf("None\n");
            continue;
        }
        int flag=0;
        memset(f1,0,sizeof(f1));
        for(int i=1;i<l;i++){
            if(s[i]==')')f1[i]++;
            f1[i]+=f1[i-1];
            if(f1[i]>(i+1)/2){
                printf("None\n");
                flag=1;
                break;
            }
        }
        if(flag)continue;
        memset(f2,0,sizeof(f2));
        for(int i=l-2;i>=0;i--){
            if(s[i]=='(')f2[i]++;
            f2[i]+=f2[i+1];
            if((l-i)/2<f2[i]){
            printf("None\n");
            flag=1;
            break;
            }
        }
        if(flag)continue;
        int vis1=0,vis2=0;
        for(int i=l-1;i>=0;i--){
            if(f1[i]==(i+1)/2)break;
            if(s[i]=='?')vis1=i;
        }
        for(int i=0;i<l;i++){
            if(f2[i]==(l-i)/2)break;
            if(s[i]=='?')vis2=i;
        }
        if(vis1&&vis2&&vis2>vis1) printf("Many\n");
        else printf("Unique\n");
    }
    return 0;
}