首页 > 代码库 > HDU4915:Parenthese sequence（贪心）

HDU4915:Parenthese sequence（贪心）

2024-07-16 12:45:28   223人阅读

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


从前扫一遍，记录最大和最小的可能的左括号的值
如果左括号的大小小于右括号的大小，则必定不行
从后扫一遍，同样记录最大和最小的可能的左括号的值
如果右括号的大小小于左括号的大小，则必定不行
然后找最小值中的最大值，和最大值中的最小值
如果前者大于后者，则不行，如果后者大于前者则有多重解，如果相等则为唯一解
嗯，发现我代码越来越飘逸了，有木有
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define mem(a,b) memset(a,0,sizeof(a))
#define L 1000005
#define up(i,x,y) for(i = x;i<=y;i++)
#define down(i,x,y) for(i = x;i>=y;i--)
#define bre(x,y) if(x){flag=y;break;}
#define con(x,y) if(x){ans(y);continue;}
char s[L];
int a[L][2],b[L][2],len,flag;

void ans(int i)
{
    if(i==1) printf("Unique\n");
    else if(i==2) printf("Many\n");
    else printf("None\n");
}

int main()
{
    int i,j;
    while(~scanf("%s",s+1))
    {
        len = strlen(s+1);
        con((len&1),0)
        mem(a,0);
        mem(b,0);
        flag = 1;
        up(i,1,len)
        {
            if(s[i]=='(')
                a[i][0]=a[i-1][0]+1,a[i][1]=a[i-1][1]+1;
            else if(s[i]==')')
            {
                if(!a[i-1][0])
                    a[i][0]=1;
                else
                    a[i][0]=a[i-1][0]-1;
                a[i][1]=a[i-1][1]-1;
            }
            else if(s[i]=='?')
            {
                if(!a[i-1][0]) a[i][0]=1;
                else
                    a[i][0]=a[i-1][0]-1;
                a[i][1]=a[i-1][1]+1;
            }
            bre((a[i][0]>a[i][1]),0)
        }
        con((!flag),0)
        down(i,len,1)
        {
            if(s[i]==')')
                b[i-1][0]=b[i][0]+1,b[i-1][1]=b[i][1]+1;
            else if(s[i]=='(')
            {
                if(!b[i][0])
                    b[i-1][0]=1;
                else
                    b[i-1][0]=b[i][0]-1;
                b[i-1][1]=b[i][1]-1;
            }
            else if(s[i]=='?')
            {
                if(!b[i][0]) b[i-1][0]=1;
                else
                    b[i-1][0]=b[i][0]-1;
                b[i-1][1]=b[i][1]+1;
            }
            bre((b[i][0]>b[i][1]),0)
        }
        con((!flag),0)
        int l,r;
        flag = 1;
        up(i,1,len)
        {
            l = max(a[i][0],b[i][0]);
            r = min(a[i][1],b[i][1]);
            bre((l>r),0)
            bre((l<r),2)
        }
        con((flag==0),0);
        con((flag==1),1);
        con((flag==2),2);
    }

    return 0;
}



联系
我们