找不同大赛
查看原帖
找不同大赛
800499
suzhikz楼主2024/10/9 21:13

都快改的和第一篇tj一样了怎么还是90

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
#define int long long
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
//void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=1e6+1e5;
int n,ans; 
char a[N],b[N];
int p1[N],p2[N];
void work(char x[],int y[]){
	stack<int>s;
	for(int i=1;i<=n;i++){
		if(x[i]=='(')s.push(i);
		else{
			y[i]=s.top();
			y[y[i]]=i;
			s.pop();
		}
	}
}
int func(int x[],int l,int r,bool f){
//	cout<<l<<' '<<r<<endl;
	if(r==l+1)return 0;
	if(x[r-1]==l+1){
		if(!f)return func(x,l+1,r-1,1)+1;
		else return func(x,l+1,r-1,1);
	}else{
		int re=0;
		for(int i=l+1;i!=r;i=x[i]+1){
			re+=func(x,i,x[i],0);
		}
		if(f==0)re+=2;
		else re++;
		return re;
	}
}
bool L[N],R[N];
int cal(int l,int r){
	if(r==l+1)return 0;
	for(int i=l;i!=r+1;i=p1[i]+1){
		L[i]=1;
	}
	for(int i=l;i!=r+1;i=p2[i]+1){
		R[i]=1;
	}
	int re=0;
	for(int i=l;i!=r+1;L[i]=R[i]=1,i=p1[i]+1){
		if(R[i]&&p2[i]==p1[i]){
			re+=cal(i+1,p1[i]-1);
		}
	}
	for(int i=l;i!=r+1;i=p1[i]+1){
		if(!L[i]||p2[i]!=p1[i]){
			re+=func(p1,i,p1[i],0);
		}
	}
	for(int i=l;i!=r+1;i=p2[i]+1){
		if(!R[i]||p2[i]!=p1[i]){
			re+=func(p2,i,p2[i],0);
		}
	}
	for(int i=l;i!=r+1;i=p1[i]+1){
		L[i]=0;
	}
	for(int i=l;i!=r+1;i=p2[i]+1){
		R[i]=0;
	}
	return re;
}
signed main(){
	scanf("%d",&n);
	scanf("%s%s",a+1,b+1);
	work(a,p1);work(b,p2);
	cout<<cal(1,n);
	return 0;
}
2024/10/9 21:13
加载中...