题解 P8407 【COCI 2021/2022 #6 - Superpozicija】

· · 题解

这是可以算是一道反悔贪心的板子题。

题意简述

给出 2n 个括号组成的括号序列，序列中的括号两两形成一组，找出一个方案在这 n 组括号中每组各选一个，使得选择的括号构成一个合法的括号序列。

解题思路

整个括号序列合法的充要条件为：在每一个位点之前的左括号数大于等于右括号数，且整个序列的左括号数等于右括号数。

记左括号为 1，右括号为 -1，如果该位置的括号不选择则记为 0，这个序列合法的充要条件为：每个位置的前缀和大于等于零，且最后一个位置的前缀和等于零。

所以我们对于一组相同的括号可以直接这样贪心地选择：两个左括号取左侧的那个，两个右括号取右侧的那个。

设合法前缀序列表示一个所有位点的前缀和都大于等于零的序列。

显然可知以下推论：一个合法前缀序列删去任意一个右括号或添加任意一个左括号后仍为合法前缀序列。

所以对于一组不同的括号可以总是先选择右括号。

从左到右遍历、选择。在每一个位点都需要判断前缀序列是否为合法前缀序列，遇到不合法的情况（因为每个点都判断，此时当前位点的前缀和为 -1）时，将之前选择的一组不同的括号中的右括号改为左括号，此时可以保证当前位点的前缀和为 0 或 1，而之前的序列仍然是合法前缀序列。且这种方法得到的合法前缀序列的和最小。

如果之前选择了多组不同的括号，设左括号的位置为 p_L，右括号的位置为 p_R，则修改后会使得区间 [\min(p_L,p_R),\max(p_L,p_R)) 内的前缀和都增加 1，区间 [\max(p_L,p_R),2n] 内的前缀和都增加 2。如果当前遍历到了位置 p，对于 p\geq\max(p_L,p_R) 的所有组选择后都不会对后续情况产生影响，若 p<\max(p_L,p_R)，则为了让后续尽可能多的位置前缀和保持大于等于零，应尽量选择 \max(p_L,p_R) 最小的一组。

AC 代码

#include<bits/stdc++.h>
using namespace std;
char s[200010];
int pos[200010],ab[100005][2],q[200010];
struct comp{
    bool operator()(const pair<int,int>x,const pair<int,int>y)const{return max(x.first,x.second)>max(y.first,y.second);}
};
int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n,ans=0;scanf("%d%s",&n,s);
        for(int i=0;i<n;i++){
            q[i<<1]=q[(i<<1)|1]=0;
            scanf("%d%d",&ab[i][0],&ab[i][1]);
            --ab[i][0];--ab[i][1];
            pos[pos[ab[i][0]]=ab[i][1]]=ab[i][0];
        }
        priority_queue<pair<int,int>,vector<pair<int,int> >,comp>r;
        for(int i=0;i<n<<1;i++){
            if(q[i]==0&&q[pos[i]]==0){
                if(s[i]=='('){
                    if(s[pos[i]]=='(')q[i]=1;
                    else{
                        r.push(make_pair(i,pos[i]));
                        q[pos[i]]=-1;
                    }
                }
                else if(s[pos[i]]==')')q[pos[i]]=-1;
                else{
                    r.push(make_pair(pos[i],i));
                    q[i]=-1;
                }
            }
            if(q[i]!=0){
                ans+=q[i];
                if(ans<0){
                    if(r.empty())break;
                    pair<int,int>p=r.top();r.pop();
                    if(i>=p.second)ans++;
                    q[p.second]=0;
                    if(i>=p.first)ans++;
                    q[p.first]=1;
                }
            }
        }
        if(ans)puts("-1");
        else{
            for(int i=0;i<n;i++)printf("%d ",q[ab[i][0]]?0:1);
            putchar('\n');
        }
    }
    return 0;
}