#C231114B. 奇迹(miracle)
前言（Front talk)
网址（Website）
题目（Problem）
题目背景
八云紫拥有操控境界程度的能力。作为其式神的八云蓝，同样拥有一定程度的操作境界的能力，而作为八云蓝的式神橙，却因为功力尚且不足，而无法对境界进行过多的干预了。
于是八云蓝打算教教橙，境界的用法。境界可以被抽象成一层一层的括号，操作境界本质上就是对括号序列进行修改。由于橙的能力尚且不足，因此只能进行一些简单的境界的建立与摧毁。
尽管如此，通过简单的操作，亦可以把一个境界转换为另外一个境界。为了给橙作为练习，蓝找来了两个境界的范本。将其中一个境界转换为另外一个境界的难度，就是橙需要施用能力的最小次数。但是由于境界实在太长，蓝决定写一个程序（？）来帮帮她计算出境界的难度。
题目描述
境界可以被抽象为由圆括号组成的括号序列。现做出如下定义：
- 定义
为嵌套括号序列。其中 为零阶嵌套括号序列，被定义为单组括号 ；而 则为 阶嵌套括号序列（ ）定义为 ，即在 的外层增添了一层括号。 - 定义
为平铺括号序列。其中 为零阶平铺括号序列，被定义为单组括号 ；而 则为 阶平铺括号序列（ ），定义为 ，即在 的左侧增添了一对括号。
例如，
现在蓝给出了两个长度为
- 选择任意非负整数
，选择括号序列的一个子串满足其为一个 阶嵌套括号序列，然后将其变为 阶平铺括号序列。 - 选择任意非负整数
，选择括号序列的一个子串满足其为一个 阶平铺括号序列，然后将其变为 阶嵌套括号序列。
提示说明处有「合法括号序列」与「子串」的定义。
现在需要求出将序列
输入格式
- 第一行共有一个整数
，表示 与 括号序列的长度。 - 接下来一行，共有
个字符，描述括号序列 。保证序列 合法。 - 接下来一行，共有
个字符，描述括号序列 。保证序列 合法。
输出格式
- 共一行，一个整数，表示将
转换为 需要的最少步数（可能为 ，也就是不进行任何操作）。
样例 #1
样例输入 #1
14
((()())(()()))
()()()()()()()样例输出 #1
6样例 #2
样例输入 #2
14
((()())(()()))
(()())(()())()样例输出 #2
10提示
见选手目录下的
样例 1 解释
- 第一步：
。 - 第二步：
。 - 第三步：
。 - 第四步：
。 - 第五步：
。 - 第六步：
。
可以证明，不存在更短的方案。
提示
合法括号序列通过这样一个形式定义：
是合法括号序列。 - 若
是合法括号序列，那么 是合法括号序列。 - 若
均为合法括号序列，那么 是合法括号序列。
我们称
数据范围及约定
本题共有
本题使用打包测评。各子任务的附加限制及分值如下表所示:
| 子任务编号 | 附加限制 | 分值 |
|---|---|---|
| 无特殊限制 |
特殊性质
题解（Solution）
代码（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;
}
