【HDU】5831 Rikka with Parenthesis II

01 Sep 2016

Rikka with Parenthesis II

题目链接

Rikka with Parenthesis II

题目大意

给你一个由”(“和”)”组成的串，要你求通过一次交换，这个串在交换后是否合法。

关于合法：

空串合法
”()”合法
如果X合法，(X)合法
如果X，Y合法，XY合法

题解

贪心

注意到一个”(“必须要一个”)”来与之相配，所以从最左边开始向右边找，遇到一个”(“cnt就+1，遇到一个”)”cnt就-1，在第一个cnt=-1的时候把cnt清零（表明这个位置需要交换）再继续往后处理，注意在此过程中cnt是不能等于-2的（如果等于-2的话最后一定有两个串不能匹配）这样一直处理到串的末尾，如果cnt=1（剩下一个交换的位置），则说明可以，否则不行。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 100005

using namespace std;

int T,n;
char s[maxn];

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        memset(s,0,sizeof(s));
        scanf("%d",&n);
        scanf("%s",s);
        if (n&1)
        {
            printf("No\n");
            continue;
        }
        int cnt=0;
        bool flag=0,ans=0;
        for (int i=0;i<n;i++)
        {
            if (s[i]=='(') cnt++;
            else cnt--;
            if (cnt==-1 && !flag)
            {

                flag=1;
                cnt=0;
            }
            if (cnt==-2 && flag)
            {
                ans=1;
                break;
            }
        }
        if (cnt==1 && !ans) printf("Yes\n");
        else if (cnt==0 && !ans && n!=2) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}