P8407 [COCI2021-2022#6] Superpozicija 题解

· · 题解

首先我们知道，一个括号序列合法当且仅当将所有的 ( 当成 +1 ,将所有的 ) 当成 -1 ,对于任意位置的前缀和都非负，且最后一个位置的前缀和为 0.

那么，如果 n 是奇数，直接无解。

接下来，让我们先考虑一些特殊情况；

那么考虑带悔贪心。

然而，我们会发现一个问题，这个题没有办法像一些带悔贪心的题一样建出来费用流模型，所以无法直接贪心模拟费用流。

于是我们需要建立一个反悔贪心机制，这个机制的核心点在于：对于所有的 () 和 )(，都先贪心地选择 )，然后贪心地将一些 ) 反悔成 (。

那么考虑如何利用带悔贪心将序列变为合法的。

先考虑一下，如果将一个 ) 变为 ( 对整个前缀和序列的贡献是什么？

不妨设第 i 对的两个位置靠左的为 l_i，靠右的为 r_i。

那么，对于一个位置来说，无论是删去一个 )，还是加上一个(，对这个位置以及以后所有的前缀和贡献都是 +1。

所以把第 i 对的 ) 变为 ( 的贡献就是：

对于每一个 l_i \leq j \leq n，sum_j 会增加 1。

对于每一个 r_i \leq j \leq n，sum_j 还会额外增加 1。

整理一下，就是：

对于每一个 l_i \leq j < r_i，sum_j 会增加 1。

对于每一个 r_i \leq j \leq n，sum_j 会增加 2。

但是此时又会产生一个问题：如果面对多个可以反悔的括号对，到底反悔哪个更优？

先说答案：优先选择 r_i 更小的反悔。

不妨设当前的位置为 p，那么我们只要证明对于剩余任意一对可以反悔的 l_j,r_j ,反悔第 j 对不会优于第 i 对就可以了。

所以，直接按照这个策略做带悔贪心就可以了。

无解的情况就是：在一个位置前缀和无论如何都 <0，或者最终前缀和只能 >0。

最后附上代码：

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pa pair<int,int>
#define mp make_pair
#define fi first
#define se second
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void file()
{
    string file_name="data";
    freopen((file_name+".in").c_str(),"r",stdin);
    freopen((file_name+".out").c_str(),"w",stdout);
}
const int N=1e5+10;
int n;
char s[2*N];
pa a[N];
//a表示一堆匹配的两个位置
int p[2*N],f[2*N];
//p表示当前位置在匹配中的另一个位置
//f表示当前位置选或者不选，f[i]=1代表选，f[i]=-1代表不选
bool solve()
{
    if(n&1)return 0;//n是奇数直接判掉
    priority_queue<int,vector<int>,greater<int>>q;
    int sum=0;
    for(int i=1;i<=2*n;i++)
    {
        if(f[i]==1){if(s[i]=='(')sum++;else sum--;}//这个位置已经标记必选
        if(s[i]!=s[p[i]]&&i<p[i])q.push(p[i]);//将r[i]加入队列中
        while(sum<0&&q.size())
        {
            int k=q.top();
            q.pop();
            f[k]=-f[k];
            f[p[k]]=-f[p[k]];
            //将这对匹配取反
            if(k<=i)sum++;
            if(p[k]<=i)sum++;
            //计算到当前位置的贡献，如果反悔的某个位置在当前位置后面，那么这个贡献到后面再算
        }
        if(sum<0)return 0;
        //当前位置前缀和无法做到>=0
    }
    if(sum!=0)return 0;
    //整个序列前缀和!=0
    return 1;
}
signed main()
{
    // file();
    int aqx=read();
    while(aqx--)
    {
        n=read();
        scanf("%s",s+1);
        //读入
        memset(p,0,sizeof(int)*(2*n+10));
        memset(f,-1,sizeof(int)*(2*n+10));
        //多测不能直接无脑memset
        for(int i=1;i<=n;i++)
        {
            int x=read(),y=read();
            a[i]=mp(x,y);
            p[x]=y,p[y]=x;
            if(s[x]==s[y])
            {
                //相同的情况，（取左边，）取后边
                if(s[x]=='(')f[x]=1;
                else f[y]=1;
            }
            else
            {
                //不相同，优先取）
                if(s[x]==')')f[x]=1;
                else f[y]=1;
            }
        }
        if(!solve())puts("-1");//无解
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(f[a[i].fi]==1)printf("0 ");
                else printf("1 ");
            }
            printf("\n");
        }
    }
    return 0;
}