自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:37:06，当前版本为作者最后更新于2022-03-23 22:54:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解

为了方便起见，

• 定义展开序列 $B$ 表示将括号序列 $B$ 变为 $\verb!()()...()!$ 的形式。
• 定义堆叠序列 $B$ 表示将括号序列 $B$ 变为 $\verb!(((...)))!$ 的形式。

考虑将一个形如 $\verb!(!A\verb!)!$ 的括号序列（其中 $A$ 为合法的括号序列），现在想要将它展开。那么唯一的路径就是堆叠 $A$，然后使用操作 $1$ 展开 $\verb!(!A\verb!)!$。同样地，要试图堆叠一个序列 $\verb!(!A\verb!)!$，那只能把 $A$ 堆叠。这是本题的一个基本思路。

要想直接实现 $A$ 到 $B$ 的转换有些麻烦。考虑先做性质 $\text{A}$。

设 $f(l,r)$ 表示将合法括号序列 $A[l:r]$ 展开需要的最少步骤数目，$g(l,r)$ 表示将合法括号序列 $A[l:r]$ 堆叠需要的最少步骤数目。

• 对于 $f(l,r)$，如果与 $A_{l+1}$ 相匹配的那个括号就是 $A_{r-1}$，那么就能发现，$f(l,r)=g(l+1,r-1)+1$；否则，考虑这样的情形：

$$\texttt{(\textcolor{red}{(...)}\textcolor{cyan}{(...)}...\textcolor{orange}{(...)})} $$

需要分别展开 $A[l+1:r-1]$ 当中的这些彩色区间，然后将 $A[l+1:r-1]$ 使用操作 $2$ 嵌套，再将整体使用操作 $1$ 展开。

• 对于 $g(l,r)$，如果与 $A_{l+1}$ 相匹配的那个括号就是 $A_{r-1}$，那么就能发现，$g(l,r)=g(l+1,r-1)$；否则，仍然考虑这样的情形：

$$\texttt{(\textcolor{red}{(...)}\textcolor{cyan}{(...)}...\textcolor{orange}{(...)})} $$

需要分别展开 $A[l+1:r-1]$ 当中的这些彩色区间，然后将 $A[l+1:r-1]$ 使用操作 $2$ 嵌套。此时能够发现 $A[l:r]$ 已经变成了嵌套序列。

具体实现时，我们需要求出与一个括号相匹配的另外一个括号的位置。这一步骤可以进行预处理。具体而言，开一个栈，依次枚举。如果是左括号则直接入栈，如果是右括号则将它与栈顶的左括号匹配并将其弹出。容易发现这么做可以在 $\mathcal O(n)$ 复杂度内预处理。

接着是考虑这两个「区间」$\text{dp}$。它可以使用递归来实现。我们需要用刚刚预处理好的匹配信息，进行次一级括号（上文当中的彩色括号。注意：次一级括号不包含这彩色括号内部的括号）的枚举。容易发现每对括号只会被枚举恰好一次，因此时间复杂度仍然是 $\mathcal O(n)$。

---

在此基础上，我们需要将括号序列 $A$ 转换为 $B$，并输出将 $A$ 转换为 $B$ 所需最少步骤。

值得注意的是，如果可以将一个括号序列 $S$ 经过一系列操作变为括号序列 $T$，那么总是可以按照反方向将 $T$ 转化为 $S$，因为操作 $1$ 和 $2$ 是互逆的（对于一种操作，可以使用另一种操作撤回它的效果）。那么就能够发现，如果我们能把 $B$ 用最少步骤展开为平铺括号序列，就能用这么多步骤把一个平铺括号序列转换为 $B$。

但这不是最小方案。考虑如何操作最小。举出下面这个情形：

$$\begin{aligned} &\texttt{\textcolor{red}{(...)}(..)(...)(.)\textcolor{blue}{(.....)}\textcolor{orange}{(..)}} \cr &\texttt{\textcolor{red}{(...)}(.....)(...)\textcolor{blue}{(.....)}\textcolor{orange}{(..)}} \end{aligned} $$

容易发现，如果存在某两个括号序列在 $A,B$ 中的位置对应相等（图中的红色、蓝色、橘色括号序列。这里对应相等仅仅指次一级的括号位置相同，不包括这次一级括号里面的内容），那么它们就不需要展开到底，只需要对其中的部分进行递归操作即可。剩下来的部分（黑色部分）则需要全部展开。

这是与刚刚的区间 $\text{dp}$ 相类似的。记 $\operatorname{calc}(l,r)$ 表示将 $A[l:r]$ 转换为 $B[l:r]$ 的最少步骤数。那么我们需要枚举出所有的可以对应相等的次一级括号，对它们采取递归；剩下来的所有括号都必须得完全展开（不然就没办法进行转换了）。容易发现时间复杂度还是 $\mathcal O(n)$ 的。

因此发现，总复杂度为 $\mathcal O(n)$。可以通过本题。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
const int MAXN =1e6+3;
int n; char A[MAXN],B[MAXN]; int P[MAXN],Q[MAXN];
void pre(char X[],int U[]){
    stack <int> S; up(1,n,i){
        if(X[i]==')') U[i]=S.top(),U[U[i]]=i,S.pop();
        else S.push(i);
    }
}
int  fun(int U[],int l,int r,bool f){ //0 推平
    if(r-1==l) return 0;
    if(U[r-1]==l+1){
        if(!f) return fun(U,l+1,r-1,true)+1;
        else   return fun(U,l+1,r-1,true); 
    }
    else{
        int ret=0; for(int p=l+1;p!=r;p=U[p]+1)
            ret+=fun(U,p,U[p],false);
        return ret+(f?1:2);
    }
}
bool L[MAXN],R[MAXN];
int  clc(int l,int r){
    if(r-1==l) return 0; int ret=0;
    for(int p=l;p!=r+1;L[p]=1,p=P[p]+1);
    for(int p=l;p!=r+1;R[p]=1,p=Q[p]+1);
    for(int p=l;p!=r+1;L[p]=1,p=P[p]+1)
        if(R[p]&&P[p]==Q[p] ) ret+=clc(p+1,P[p]-1);
    for(int p=l;p!=r+1;p=P[p]+1)
        if(P[p]!=Q[p]||!R[p]) ret+=fun(P,p,P[p],0);
    for(int p=l;p!=r+1;p=Q[p]+1)
        if(P[p]!=Q[p]||!L[p]) ret+=fun(Q,p,Q[p],0);
    for(int p=l;p!=r+1;L[p]=0,p=P[p]+1);
    for(int p=l;p!=r+1;R[p]=0,p=Q[p]+1);
    return ret;
}
int main(){
    scanf("%d%s%s",&n,A+1,B+1);
    pre(A,P),pre(B,Q);
    printf("%d\n",clc(1,n));
    return 0;
    
}