首页 > 代码库 > HDOJ 4915 Parenthese sequence

HDOJ 4915 Parenthese sequence

2024-07-17 02:23:00   218人阅读



Parenthese sequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 716    Accepted Submission(s): 335


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 s1s2…sn (1≤n≤106).
 

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
 

Author
Xiaoxu Guo (ftiasch)
 

Source
2014 Multi-University Training Contest 5
 



#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=1001000;

char str[maxn];
int num[maxn],prefix[maxn],suffix[maxn];
int pre0[maxn],suf0[maxn];

void init()
{
    memset(num,0,sizeof(num));
    memset(prefix,0,sizeof(prefix));
    memset(suffix,0,sizeof(suffix));
    memset(pre0,0,sizeof(pre0));
    memset(suf0,0,sizeof(suf0));
}

int main()
{
while(scanf("%s",str)!=EOF)
{
    int n=strlen(str);
    if(n%2==1)
    {
        puts("None"); continue;
    }
    init();
    for(int i=0;i<n;i++)
    {
        if(str[i]=='(') num[i+1]=1;
        else if(str[i]==')') num[i+1]=-1;
        else if(str[i]=='?') num[i+1]=0;
    }
    bool flag=true;
    for(int i=1;i<=n;i++)
    {
        if(num[i]) prefix[i]=prefix[i-1]+num[i];
        else prefix[i]=prefix[i-1]+1;
        if(prefix[i]<0)
        {
            flag=0; break;
        }
    }
    for(int i=n;i>=1;i--)
    {
        if(prefix[i]<=1)
            pre0[i]=pre0[i+1]+1;
        else pre0[i]=pre0[i+1];
    }
    if(flag==false)
    {
        puts("None"); continue;
    }
    for(int i=n;i>=1;i--)
    {
        if(num[i]) suffix[i]=suffix[i+1]-num[i];
        else suffix[i]=suffix[i+1]+1;
        if(suffix[i]<0)
        {
            flag=false;
            break;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(suffix[i]<=1)
            suf0[i]=suf0[i-1]+1;
        else suf0[i]=suf0[i-1];
    }
    if(flag==false)
    {
        puts("None"); continue;
    }
    int cnt=0;
    for(int i=2;i<n;i++)
    {
        if(num[i]==0)
        {
            if( (prefix[i]>=2&&pre0[i]==0) && (suffix[i]>=2&&suf0[i]==0) )
                cnt++;
        }
    }
    if(cnt)
        puts("Many");
    else
        puts("Unique");
}
	return 0;
}




联系
我们