【Henu ACM Round#20 F】 Arthur and Brackets

在这里输入题意

【题解】

所给的li,ri是左括号从左到右的顺序给的。
(且注意长度是2*n
现在我们先把第一个左括号放在第1个位置。

然后考虑第二个位置。

如果这个位置能放右括号和第一个匹配(位置满足在1+l[i]..1+r[i]之间.

那么我们就在第二个位置放一个右括号就好了。

(如果我们作死不放右括号的话,那就只能放左括号了->一定要放一个括号的

那么我们就只能先匹配这一个左括号了,而前一个左括号可能在第3个位置就不能匹配了。

这就会造成错解。

也就是说当前栈顶的左括号是当前需要匹配的括号。不能跳过它。那么我们的原则肯定就是赶快把它匹配了。

越拖到后面,就越没机会匹配。

(所以能和之前的某个括号匹配,就一直匹配

而如果这个位置不能匹配。

那么没办法。

只好放一个左括号在这个地方了。

然后优先匹配新加进去的这个左括号。

如果当前的位置已经大于上界了。

那么就直接输出无解。

如果还有没匹配到的左括号。

也输出无解。

【代码】

#include<bits/stdc++.h>

using namespace std;

const int N = 600;

int n,l[N+10],r[N+10],pos[N+10];

stack<int> sta;

vector<char> ans;

int main()

{

    cin >>n;

    for (int i = 1;i <= n;i++){

        cin >> l[i] >> r[i];

    }

    int now = -1;

    for (int i = 1;i <= n;i++){

        sta.push(i);

        pos[i] = ++now;

        ans.push_back('(');

        while (!sta.empty()){

            int top = sta.top();

            if (pos[top]+l[top]<=now+1 && now+1<=pos[top]+r[top]){

                sta.pop();

                ans.push_back(')');

                ++now;

            }else if (now+1>pos[top]+r[top]){

                return cout<<"IMPOSSIBLE"<<endl,0;

            }else break;

        }

    }

    if (!sta.empty()) return cout<<"IMPOSSIBLE"<<endl,0;

    for (char key:ans)

        cout<<key;

    return 0;

}

巴特西

【Henu ACM Round#20 F】 Arthur and Brackets

最新文章

热门文章