Codeforces #594 div1 B/div2 D2 – The World Is Just a Programming Task

题目链接：https://codeforces.com/contest/1239/problem/B

题意：给你一个长度为n的括号字符串，将这个括号字符串围成一个环，问交换一次两个括号的位置，能使环中最多出现多少个正确的括号序列。

做法：很(我)有(不)意(会)思(做)的思维题。首先我们定义没有被任何括号包住的括号为一级括号，例如“()()()”就是3个一级括号，然后我们定义被一层一级括号包住的括号为二级括号，例如“(()())”就是一级括号里面有2个二级括号，最后我们定义被一层二级括号和一层一级括号包住的括号为三级括号，例如“((()()))”就是一级括号里面有1个二级括号里面有2个三级括号。当出现二级括号时，我们通过交换包住二级括号的一级括号两端可以把里面的二级括号放出来，例如“(()())”可以通过交换变为“)()()(”，但是代价是这个操作会将外面的其他括号包起来变成一个一级括号，操作期望为二级括号数+1。当出现三级括号时，我们通过交换包住三级括号的二级括号两端可以把里面的三级括号放出来，例如“((()()))”可以通过交换变为“()()()()”，但是代价时这个操作会将一级括号里的其他二级括号包起来变成2个一级括号，操作期望为三级括号数+一级括号数+1(还有一个是原来就存在的一级括号)，具体实现见代码。

参考代码：

#include <iostream>
#include <stack>

using namespace std;
stack<int> S;
char str[600005];
int sum[600005], s[3][600005];

int main()
{
    int n, pos = 1, cnt = 0, minn = 0;
    cin >> n >> str + 1;
    for (int i = 1; i <= n; ++i)
    {
        if (str[i] == '(')
            cnt++;
        else
            cnt--;
        if (cnt < minn)
        {
            minn = cnt;
            pos = i + 1;
        }
    }
    if (cnt)
    {
        cout << "0" << endl;
        cout << "1 1" << endl;
        return 0;
    }
    for (int i = n + 1; i <= 2 * n; ++i)
        str[i] = str[i - n];
    for (int i = pos; i < pos + n; ++i)
    {
        for (int j = 0; j < 3; ++j)
            s[j][i] = s[j][i - 1];
        if (str[i] == '(')
            S.push(i);
        else
        {
            S.pop();
            if (S.empty())
                s[0][i]++;
            else if (S.size() == 1)
                s[1][i]++;
            else if (S.size() == 2)
                s[2][i]++;
        }
    }
    int ans = s[0][pos + n - 1], l = 1, r = 1;
    for (int i = pos; i < pos + n; ++i)
    {
        if (str[i] == '(')
            S.push(i);
        else
        {
            int temp = S.top();
            S.pop();
            if (S.empty())
            {
                int tempone = s[1][i] - s[1][temp] + 1;
                if (tempone > ans)
                {
                    ans = tempone;
                    if (i % n)
                        r = i % n;
                    else
                        r = n;
                    if (temp % n)
                        l = temp % n;
                    else
                        l = temp;
                }
            }
            else if (S.size() == 1)
            {
                int temptwo = s[2][i] - s[2][temp] + s[0][pos + n - 1] + 1;
                if (temptwo > ans)
                {
                    ans = temptwo;
                    if (i % n)
                        r = i % n;
                    else
                        r = n;
                    if (temp % n)
                        l = temp % n;
                    else
                        l = temp;
                }
            }
        }
    }
    cout << ans << endl;
    cout << l << " " << r << endl;
    return 0;
}

Codeforces #594 div1 B/div2 D2 – The World Is Just a Programming Task

原文：https://www.cnblogs.com/mapleaves/p/11808809.html