首页 > 代码库 > HDU 4915 Parenthese sequence(瞎搞题)

HDU 4915 Parenthese sequence(瞎搞题)

2024-07-16 01:06:40   216人阅读

从左向右扫一遍左括号的最大值，与最小值。

从右向左扫一遍右括号的最大值，与最小值。

比较最大值中的最小数与最小中的最大数看能否有交集，0个，1个或者多个。

Parenthese sequence

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


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)
 

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#include <stdio.h>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define eps 1e-12
///#define M 1000100
#define LL __int64
///#define LL long long
///#define INF 0x7ffffff
#define INF 0x3f3f3f3f
#define PI 3.1415926535898
#define zero(x) ((fabs(x)<eps)?0:x)

using namespace std;


const int maxn = 1010000;

int sum[maxn][2], ans[maxn][2];
char str[maxn];

int main()
{
    while(cin >>str+1)
    {
        int len = strlen(str+1);
        if(len%2)
        {
            cout<<"None"<<endl;
            continue;
        }
        memset(sum, 0, sizeof(sum));
        memset(ans, 0, sizeof(ans));
        int flag = 0;
        for(int i = 1; i <= len; i++)
        {
            if(str[i] == '(')
            {
                sum[i][0] = sum[i-1][0]+1;
                sum[i][1] = sum[i-1][1]+1;
            }
            else if(str[i] == ')')
            {
                if(sum[i-1][0] == 0) sum[i][0] = 1;
                else sum[i][0] = sum[i-1][0]-1;
                sum[i][1] = sum[i-1][1] - 1;
            }
            else if(str[i] == '?')
            {
                if(sum[i-1][0] == 0) sum[i][0] = 1;
                else sum[i][0] = sum[i-1][0]-1;
                sum[i][1] = sum[i-1][1] +1;
            }
            if(sum[i][0] > sum[i][1]) flag = 1;
        }
        if(flag)
        {
            cout<<"None"<<endl;
            continue;
        }
        for(int i = len; i >= 1; i--)
        {
            if(str[i] == ')')
            {
                ans[i-1][0] = ans[i][0]+1;
                ans[i-1][1] = ans[i][1]+1;
            }
            else if(str[i] == '(')
            {
                if(ans[i][0] == 0) ans[i-1][0] = 1;
                else ans[i-1][0] = ans[i][0]-1;
                ans[i-1][1] = ans[i][1]-1;
            }
            else if(str[i] == '?')
            {
                if(ans[i][0] == 0) ans[i-1][0] = 1;
                else ans[i-1][0] = ans[i][0]-1;
                ans[i-1][1] = ans[i][1]+1;
            }
            if(ans[i][0] > ans[i][1]) flag = 1;
        }
        if(flag)
        {
            cout<<"None"<<endl;
            continue;
        }
        for(int i = 1; i <= len; i++)
        {
            int xx = max(sum[i][0], ans[i][0]);
            int yy = min(sum[i][1], ans[i][1]);
            if(xx > yy)
            {
                flag  = 1;
                break;
            }
            if(xx < yy)
                flag = 2;
        }
        if(flag == 1) cout<<"None"<<endl;
        else if(flag == 2) cout<<"Many"<<endl;
        else cout<<"Unique"<<endl;
    }
    return 0;
}


联系
我们