记录

赛时思路

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
const int N=1000001;
int n,ans;
int nxa[N],nxb[N];
char a[N],b[N];
void Predeal(char c[],int nx[]){
	stack<int>sta;
	register int i,k;
	for(i=1;i<=n;++i)
		if(c[i]=='(')sta.push(i);
		else nx[sta.top()]=i,sta.pop();
}
int turn1(char[],int[],int,int);
int turn0(char c[],int nx[],int l,int r){
	register int i,k=0;
	for(i=l;i<=r;i=nx[i]+1)
		if(i+1!=nx[i])k+=turn1(c,nx,i+1,nx[i]-1)+1;
	return k;
}
int turn1(char c[],int nx[],int l,int r){
	if(l+1==r)return 0;
	if(nx[l]==r)return turn1(c,nx,l+1,r-1);
	else return turn0(c,nx,l,r)+1;
}
void separate(int l,int r){
//	printf("->%d %d\n",l,r);
	if(l>r)return;
	register int i,j,frn,bac;
	i=j=l;
	while(i<=r&&j<=r){
		while(i==j&&nxa[i]==nxb[j]&&i<=r){
			separate(i+1,nxa[i]-1);
			i=nxa[i]+1,j=nxb[j]+1;
		}if(i>r)break;
		frn=i,i=nxa[i]+1;
		while(i!=j&&i<=r&&j<=r)
			if(i<=j)i=nxa[i]+1;
			else j=nxb[j]+1;
		if(i>r||j>r)bac=r;
		else bac=i-1;
		ans+=turn0(a,nxa,frn,bac);
//		printf("%d\n",ans);
		ans+=turn0(b,nxb,frn,bac);
//		printf("%d\n",ans);
	}
}
int main(){
	scanf("%d\n",&n);
	scanf("%s%s",a+1,b+1);
	Predeal(a,nxa);
	Predeal(b,nxb);
	separate(1,n);
	printf("%d",ans);
	return 0;
}

Call me if the explanation is needed.

注：大数据样例第3和5点没过。