CF1686E

发表于 | 分类于 |

题面:https://codeforces.com/contest/1686/problem/E

大致题意:给定2*n个括号序列，其中含有n个左括号，n个右括号，可以对任意区间进行reverse操作，求最少需要多少次操作能使该序列左右括号匹配

题解:将左右括号抽象成1和-1，则左右括号的匹配条件转化成了对任意的i满足

考虑reverse操作，对区间外的pre不造成影响，对区间内的序号为i的元素，其反转后(序号发生了改变，等式中用原序列的编号表示)，要满足pre>=0，则，故我们易想出预先处理出pre值，记录第一个和最后一个pre<0的下标

  1. 若一次reverse操作即可满足条件，则该区间必须包含所有pre<0的元素，是否满足条件仅取决于区间pre与边界pre的大小关系，故我们取pre最大的位置为R、L+1(这里有个小细节)

  2. 若一次reverse无法满足条件，考虑能否用两次reverse操作完成，易联想到取pre最大的序列为i，则反转1~i与i+1~n即可满足条件

    证明:再次引用上述不等式,反转1~i时，为所有pre中的最大值，为0;反转i+1~n时，为所有pre中的最大值，为0，故一定能满足条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/

ll T, n, m, k, tt = 0;
ll tmp, pre[300005];
string s;
int main()
{
    T = 1;
    cin >> T;
    while (T--)
    {
        cin >> n;
        cin >> s;
        vector<ll> a(2*n);
        for (ll i = 0; i < 2*n; i++)
        {
            if (s[i] == '(')
            {
                a[i] = 1;
            }
            else
            {
                a[i] = -1;
            }
        }
        bool ok = 1;
        ll fir = -1, fin = -1, mx = -1;
        for (ll i = 0; i < 2*n; i++)
        {
            if (i == 0)
            {
                pre[i] = a[i];
                mx = 0;
            }
            else
            {
                pre[i] = pre[i - 1] + a[i];
            }
            if (pre[i] < 0)
            {
                ok = 0;
                if(fir==-1)
                {
                    fir = i;
                }
                fin = i;
            }
            if(pre[i]>pre[mx])
            {
                mx = i;
            }
        }
        if (ok)
        {
            cout << 0 << "\n";
            continue;
        }
        ok = 1;
        ll mxl = 0, mxr = 2*n-1;
        if(fin!=-1&&fir!=-1)
        {
            
            for (ll i = 0; i <= fir;i++)
            {
                if(pre[i]>pre[mxl])
                {
                    mxl = i;
                }
            }
            for (ll i = 2*n-1; i >=fin+1;i--)
            {
                if(pre[i]>pre[mxr])
                {
                    mxr = i;
                }
            }
            if(mxl!=fir)
                mxl++;
            reverse(a.begin()+mxl, a.begin()+mxr+1);
        }
        for (ll i = 0; i <2*n;i++)
        {
            if(i==0)
            {
                pre[i] = a[i];
            }else
            {
                pre[i] = pre[i - 1] + a[i];
            }
            if(pre[i]<0)
            {
                ok = 0;
            }
        }
        if(ok)
        {
            cout << "1\n";
            cout << mxl+1 << " " << mxr+1 << "\n";
        }else
        {
            cout << "2\n";
            cout << 1 << " " << mx+1 << "\n";
            cout << mx + 2 << " " << 2 * n << "\n";
        }
#ifdef DE_BUG
                    cout
                << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

注意在取mxl时，有可能mxl=fir(“(((“的情况)，则此时mxl再加1会导致有pre<0的元素不在reverse区间内,故mxl不能加1