#C231114B. 奇迹(miracle)
标签（Label）
- 思维
- 图论转化
网址（Website）
题目（Problem）
题目背景
八云紫拥有操控境界程度的能力。作为其式神的八云蓝，同样拥有一定程度的操作境界的能力，而作为八云蓝的式神橙，却因为功力尚且不足，而无法对境界进行过多的干预了。
于是八云蓝打算教教橙，境界的用法。境界可以被抽象成一层一层的括号，操作境界本质上就是对括号序列进行修改。由于橙的能力尚且不足，因此只能进行一些简单的境界的建立与摧毁。
尽管如此，通过简单的操作，亦可以把一个境界转换为另外一个境界。为了给橙作为练习，蓝找来了两个境界的范本。将其中一个境界转换为另外一个境界的难度，就是橙需要施用能力的最小次数。但是由于境界实在太长，蓝决定写一个程序（？）来帮帮她计算出境界的难度。
题目描述
境界可以被抽象为由圆括号组成的括号序列。现做出如下定义：
- 定义 $D_i$ 为嵌套括号序列。其中 $D_0$ 为零阶嵌套括号序列，被定义为单组括号 $\verb!()!$；而 $D_k$ 则为 $k$ 阶嵌套括号序列（$k \geq 1$）定义为 $\verb!(!D_{k-1}\verb!)!$，即在 $D_{k-1}$ 的外层增添了一层括号。
- 定义 $F_i$ 为平铺括号序列。其中 $F_0$ 为零阶平铺括号序列，被定义为单组括号 $\verb!()!$；而 $F_k$ 则为 $k$ 阶平铺括号序列（$k \geq 1$），定义为 $\verb!()!F_{k-1}$，即在 $F_{k-1}$ 的左侧增添了一对括号。
例如，$\verb!((()))!$ 为 $D_2$，$\verb!()()()()!$ 为 $F_{3}$。
现在蓝给出了两个长度为 $n$ 的合法括号序列 $A$ 和 $B$。橙可以用以下操作对序列 $A$ 进行变换：
- 选择任意非负整数 $k$，选择括号序列的一个子串满足其为一个 $k$ 阶嵌套括号序列，然后将其变为 $k$ 阶平铺括号序列。
- 选择任意非负整数 $k$，选择括号序列的一个子串满足其为一个 $k$ 阶平铺括号序列，然后将其变为 $k$ 阶嵌套括号序列。
提示说明处有「合法括号序列」与「子串」的定义。
现在需要求出将序列 $A$ 变换为序列 $B$ 所需的最少操作数。可以证明，总存在一种操作方案能将序列 $A$ 变换为序列 $B$。
输入格式
- 第一行共有一个整数 $n$，表示 $A$ 与 $B$ 括号序列的长度。
- 接下来一行，共有 $n$ 个字符，描述括号序列 $A$。保证序列 $A$ 合法。
- 接下来一行，共有 $n$ 个字符，描述括号序列 $B$。保证序列 $B$ 合法。
输出格式
- 共一行，一个整数，表示将 $A$ 转换为 $B$ 需要的最少步数（可能为 $0$，也就是不进行任何操作）。
样例 #1
样例输入 #1
14
((()())(()()))
()()()()()()()样例输出 #1
6样例 #2
样例输入 #2
14
((()())(()()))
(()())(()())()样例输出 #2
10提示
见选手目录下的 $miracle/miracle3 \sim5.in$ 与 $miracle/miracle3\sim 5.ans$。
样例 1 解释
- 第一步：$\verb!((()())(()()))!\to\verb!(((()))(()()))!$。
- 第二步：$\verb!(((()))(()()))!\to\verb!(((()))((())))!$。
- 第三步：$\verb!(((()))((())))!\to\verb!(((()))()()())!$。
- 第四步：$\verb!(((()))()()())!\to\verb!(()()()()()())!$。
- 第五步：$\verb!(()()()()()())! \to\verb!((((((()))))))!$。
- 第六步：$\verb!((((((()))))))!\to\verb!()()()()()()()!$。
可以证明，不存在更短的方案。
提示
合法括号序列通过这样一个形式定义：
- $\verb!()!$ 是合法括号序列。
- 若 $A$ 是合法括号序列，那么 $\verb!(!A\verb!)!$ 是合法括号序列。
- 若 $A,B$ 均为合法括号序列，那么 $AB$ 是合法括号序列。
我们称 $A$ 是 $B$ 的子串，当且仅当删除 $B$ 开头若干个字符（可以不删除），再删除 $B$ 末尾若干个字符（可以不删除），剩下来的字符序列与 $A$ 完全相同。
数据范围及约定
本题共有 $20$ 个测试点，每个测试点 $5$ 分。最终分数为所有测试点分数之和。
本题使用打包测评。各子任务的附加限制及分值如下表所示:
| 子任务编号 | 附加限制 | 分值 |
|---|---|---|
| $1$ | $n \leq 18$ | $15$ |
| $2$ | $n \leq 2000$, 性质 $\mathrm{A}, \mathrm{B}$ | $20$ |
| $3$ | $n \leq 2000$, 性质 $\mathrm{B}$ | $10$ |
| $4$ | $n \leq 2000$ | $10$ |
| $5$ | $n \leq 2 \times 10^{5}$, 性质 $\mathrm{B}$ | $10$ |
| $6$ | $n \leq 2 \times 10^{5}$, 性质 $\mathrm{C}\qquad\quad$ | $10$ |
| $7$ | 无特殊限制 | $25$ |
特殊性质 $A$：保证 $B$ 是 $(n\div 2-1)$ 阶平铺括号序列。
题解（Solution）
$\qquad$由于作者很懒，感性理解就好啦~
代码（Code）
#include<bits/stdc++.h>
#include<stack>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
inline int input(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;}
const int N = 1012345;
char s[N],t[N];
int n,ans;
vector<int> sona[N],sonb[N],*son;
int ra[N],rb[N];
inline void chai(int x){
if(son[x].size()==0) return;
while(son[x].size()==1) x=son[x][0];
if(son[x].size()==0) return ans++,void();
ans+=2;for(auto y:son[x]) chai(y);
}
void solve(int a,int b){
for(int i=0,j=0;i<sona[a].size()||j<sonb[b].size();){
if(i<sona[a].size()&&j<sonb[b].size() && sona[a][i]==sonb[b][j] && ra[sona[a][i]]==rb[sonb[b][j]]){//如果可以合成一个
solve(sona[a][i],sonb[b][j]);
i++,j++;
}else if(j==sonb[b].size() || (i<sona[a].size() && sona[a][i]<sonb[b][j])){
son=sona;
chai(sona[a][i]);
i++;
}else{
son=sonb;
chai(sonb[b][j]);
j++;
}
}
}
signed main(){
freopen("miracle.in","r",stdin);
freopen("miracle.out","w",stdout);
scanf("%d%s%s",&n,s+1,t+1);
{
int fa=0;stack<int> st;
For(i,1,n){
if(s[i]=='('){
st.push(i);
sona[fa].emplace_back(i);
fa=i;
}else{
ra[st.top()]=i,st.pop();
fa=st.empty()?0:st.top();
}
}
}
{
int fa=0;stack<int> st;
For(i,1,n){
if(t[i]=='('){
st.push(i);
sonb[fa].emplace_back(i);
fa=i;
}else{
rb[st.top()]=i,st.pop();
fa=st.empty()?0:st.top();
}
}
}
solve(0,0);
return cout<<ans<<'\n',0;
}
