2020 Multi-University Training Contest 3

1009：http://acm.hdu.edu.cn/showproblem.php?pid=6799
题意：给你一个字符串，由()* 组成，'* '代表'(' ')' ' '三者中的一个，问你能不能组成一个合法序列。多个答案的时候输出字典序最小的。
思路：括号序列的匹配，成功之后可以理解为这一对括号消失不见了，那么我们可以从左往右扫一遍，在从右往左扫一遍，字典序最小的时候就是改变' * '最少的时候。从左往右，遇到右括号就看前面有没有多的' * '或者'(',优先消除'('。从右往左也是同理。这里的话，用队列来存'*' 的位置，原因我也不明白，VECTOR的pop_back交上去WA了。如果这个最后不能全部左或右括号有剩余且不再有' * '，那这时就输出无解就好。

//team yglance+xhwl+TTD
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
queue <int > que;
char s[maxn];
int kong ,zuo,you,n;
int main()
{
    ios::sync_with_stdio(false);
//    freopen("in.in","r",stdin);
//    freopen("out.out","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        while(!que.empty())
        {
            que.pop();
        }
        memset(s,0,sizeof(s));
        scanf("%s",s);
        int f=1;
        kong=0;
        zuo=0;
        you=0;
        n=strlen(s);
        for(int i=0;i<n;i++)
        {
            if(s[i]=='*')
            {
                kong++;
                que.push(i);
            }
            else if(s[i]=='(')
            {
                zuo++;
            }
            else
            {
                you++;
                if(you>kong+zuo)
                {
                    f=0;
                    break;
                }
                else
                {
                    if(zuo>0)
                    {
                        zuo--;
                        you--;
                    }
                    else
                    {
                        kong--;
                        int pl=que.front();
                        que.pop();
                        s[pl]='(';
                        you--;
                    }
                }
            }
        }
        if(!f)
        {
            printf("No solution!\n");
            continue;
        }
        kong=0;
        zuo=0;
        you=0;
        while(!que.empty())
        {
            que.pop();
        }
        for(int i=n-1;i>=0;i--)
        {
            if(s[i]=='*')
            {
                kong++;
                que.push(i);
            }
            else if(s[i]=='(')
            {
                zuo++;
                if(zuo>kong+you)
                {
                    f=0;
                    break;
                }
                else
                {
                    if(you>0)
                    {
                        you--;
                        zuo--;
                    }
                    else
                    {
                        kong--;
                        int pl=que.front();
                        que.pop();
                        s[pl]=')';
                        zuo--;
                    }
                }
            }
            else
            {
                you++;
            }
        }
        if(f)
        {

            for(int i=0;i<n;i++)
            {
                if(s[i]!='*')
                printf("%c",s[i]);
            }
            printf("\n");
        }
        else
        {
            printf("No solution!\n");
        }

    }
     return 0;
}