CF1685C Bring Balance 题解

· · 题解

写篇题解记录一下学长讲的为数不多能听懂的题

如果觉得废话太多可以直接看末尾结论

遇到括号序列、01 串，并且要考虑其前缀的，可以转化成折线图，即将左括号看成 +1，右括号看成 -1，并计算序列中每个位置的前缀和，可以得到一个折线图：

题目中说 0 和 1 的数量相等，因此 1 和 n\times 2 对应的高度均为 0.

我们的目标便是将所有低于 x 轴的点翻上来。

而我们能够进行的操作是区间反转，假设我们反转如下红色线段围住的区间：

黑色是反转前的线段，绿色是反转后的线段，可以看出，对应点及其高度均关于两点连线（紫色线段）的中点中心对称， 也就是每次反转区间 [l,r] 相当于将内部所有点变成关于线段 lr 的中点的中心对称点。

每次将某些低于 x 轴的部分翻上去，就可能会有一些高于 x 轴的部分翻下去，我们不希望这种事情发生，因此想办法处理。而其中原先高度最高的反转后高度肯定最低，只需要考虑它即可。

考虑反转了区间 [l,r]，原先高度最高的点为 a，反转后的点为 a'。当最高点刚好落在 x 轴上时：

（其中相同颜色标注的线段相等）

我们有：

\frac{1}{2}h_a=\frac{1}{2}(h_l+h_r)

即：

h_a=h_l+h_r

__也就是说当 [l,r] 中所有的 a 满足 h_a\leq h_l+h_r 时，反转 [l,r] 后没有点会跑到 x 轴下方。__

结论：

也就是说若能找到一个 l 和 r 满足上述条件，且在 x 轴下方的点全部在 [l,r] 之间，那么我们可以通过翻转一次 [l,r] 直接得到答案。当然，在具体实现中，使用贪心策略，设 p_l 为最左的低于x轴的点，设 p_r 为最右的低于x轴的点，那么只需记录 [1,p_l] 和 [p_r,n\times 2] 中最高的点作为 l,r 即可。

那如果不能一次搞定呢？那肯定是全部 [l,r] 中都包含一个很高的 x，而这个 x 肯定是所有点中高度最高的一个。于是我们可以 化敌为友 ，直接反转 [1+x] 和 [x+1,n\times 2]，共两次。（因为这两个区间内没有任何一个数大于 x 的）

然后献上又臭又长的代码qwq：

#include<cstdio>
#include<iomanip>
#define INF 0x7f7f7f7f
using namespace std;
const int N=2e5+50;
char s[N];
int h[N],pm,pk[N],ed1,ed2;
//pm记录最高点，pk记录所有低于x轴的点 
int n,t;
inline int Max(int a,int b){return a>b?a:b;}

pair<int,int> Work(int l,int r)//计算区间的最大值 
{
    int maxn=-INF,pos=0;
    for(int i=l;i<=r;i++){
        if(h[i]>maxn){
            maxn=h[i],pos=i;
        }
    }
    return make_pair(maxn,pos);
}
bool Check()
{
    int ml=0,mr=0,mm=0;
    pair<int,int> l,r,mid; 

    //注意这里h[i]表示i的前缀和，因此0才表示第一个括号，下面输出左区间+1也是同理 
    l=Work(0,pk[1]);
    mid=Work(pk[1],pk[ed2]);
    r=Work(pk[ed2],n*2);

    if(l.first+r.first>=mid.first){//有区间满足条件 
        printf("1\n");
        printf("%d %d\n",l.second+1,r.second);
        return true;
    }
    return false;
}
void Print()
{
    if(!ed2){//原序列为合法序列，不需要反转 
        printf("0\n");
        return ;
    }
    if(!Check()){//若没有区间满足条件 
        printf("2\n");
        printf("1 %d\n%d %d\n",pm,pm+1,2*n);
    }
}
void Pre()//初始化点的高度 
{
    ed1=ed2=0;
    for(int i=1;i<=n*2;i++){
        if(s[i]=='(') h[i]=h[i-1]+1;
        else h[i]=h[i-1]-1;
    }
}

void Solve()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    Pre();
    int maxn=-INF;//注意有的点可能小于0，因此 maxn 不能设为0，上同 
    for(int i=1;i<=n*2;i++){
        if(h[i]>=maxn){
            pm=i;
            maxn=h[i];
        }
        if(h[i]<0) pk[++ed2]=i;
    }
}
int main()
{
    scanf("%d",&t);
    while(t--){
        Solve();
        Print();
    }
    return 0;
}

然后就讲完力（喜）