Parenthese sequence

??
????
(??

Unique
Many
None

题解及代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
    int pos,l,r;  //用来记录问号的位置和正序(从左到右)时，
}t[1000100];      //左括号的最大数目和右括号的数目

int main()
{
    int k=0;
    char s[1000100];
    memset(s,0,sizeof(s));
    while(scanf("%s",&s)!=EOF)
    {
        k=1;
        int nl=0,nr=0;
        bool flag=true;
        int len=strlen(s);
        if(len%2)         //长度为奇数时，不可能
        {
            printf("None\n");
            continue;
        }

        int l=0,r=0;
        for(int i=0;i<len;i++)        //从左向右测试，看是否能出现()))……这种情况
        {                             //我们把？都当作左括号来处理
            if(s[i]=='('||s[i]=='?') l++;
            else r++;

            if(r>l)
            {
                flag=false;
                break;
            }

            if(s[i]=='?')
            {
                t[k].pos=i;t[k].l=l;t[k++].r=r;
            }
            else if(s[i]=='(') nl++;
            else nr++;
        }
        if(!flag)
        {
            printf("None\n");
            continue;
        }

        l=0,r=0;
        for(int i=len-1;i>=0;i--)         //从右向左测试是否会出现……(((()的情况
        {                                 //我们把？都当作右括号来处理
            if(s[i]==')'||s[i]=='?') r++;
            else l++;
            if(r<l)
            {
                flag=false;
                break;
            }
        }

        if(!flag)
        {
            printf("None\n");
            continue;
        }
      
                                        //排除了上述的不可能情况之后，剩下的一定能构造出来了
        int n=len/2;                    //下面讨论unique和many的区别
        if(nl==n||nr==n)                //nl记录左括号的数目，nr记录右括号的数量，这里unique很好理解
        {
            printf("Unique\n");
            continue;
        }

        flag=false;                    //这里的解释放在最下面
        int i=n-nl;
        if(i<k-1)
        {
            int j=i+1,d=-1;
            l=t[i].l-1;
            r=t[i].r+1;

            if(l>=r)
            for(d=t[i].pos+1;d<t[j].pos;d++)
            {
                if(s[d]=='(') l++;
                else if(s[d]==')') r++;

                if(r>l) break;
            }

            if(d>=t[j].pos) flag=true;
        }

        if(flag) printf("Many\n");
        else printf("Unique\n");
    }
}
/*
这里解释一下能构造出括号对的情况下，unique和many的区别。

首先我们能想到，如果只有一个问号或者没有问号的情况下，那么
这就只能是unique了。

然后考虑问号的数目大于等于2的情况：(这里我们只考虑正序)如果
我想要得到many，首先我们要保证一对问号变换之后，如：?……?变
成(……)，还能将这对括号对换位置，即)……(。

那么这样改过之后，我们可能就会出现())))……的情况，如果出现这种
情况，那么我们选的这对?……?就是不能变动的，接着选取另外两对问
号进行测试，直到测试完所有的问号对都出现上述情况，那就只能是unique
或者当我们选定的问号对不会出现()))……的情况就能输出many了。

其实这样已经计算了所有能够达到many的情况，其实我们只要计算一个就
可以了，那么我们计算哪一个呢？挑一个对整体影响最小的，即我们把前
n-nl-1个问号都变成(，本来第n-nl个我们也变成(的，那么剩下的变成)就
能满足情况了，这里我们把它变成),而第n-nl+1个问号变成(,即在最原始的
情况下(左括号都在右括号的左边)把最中间两个??从()变成)(，这样影响是
最小的。

为什么呢？比如：((??)(????)),当我们正序考虑时，贪心思想先把遇到的?
变成左括号，然后是其他的变成右括号，这样我们判断第二种不满足条件时
才能尽可能的使其满足情况。假设我们把第一个?变成),那么我们判断时，它
影响当前位置及后面所有位置的l和r的数目;当我们把将第三个?变成)时，它
影响的只有当前位置和它后面所有位置l和r的数目。同时我们也能发现，当
后一种情况都不能满足many时，前面的情况是根本不可能构成many的。

*转载请注明出处，谢谢。
*/

hdu 4915 Parenthese sequence,布布扣,bubuko.com

hdu 4915 Parenthese sequence

原文：http://blog.csdn.net/knight_kaka/article/details/38389215