95分求助WA on #20!悬赏关注!非常焦急!
查看原帖
95分求助WA on #20!悬赏关注!非常焦急!
494699
卷王慢即快楼主2023/1/7 21:04
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, top1 = 0, top2 = 0, ans = 0;
char a[1000001], b[1000001];
int s1[1000001], s2[1000001];
int m1[1000001], m2[1000001];
inline int check(int l, int r, int m[], bool flag)
{
    if(l + 1 == r) return 0;
    int sum = 0;
    if(m[r - 1] == l + 1)
    {
        if(flag == 1) return check(l + 1, r - 1, m, 1);
        else return check(l + 1, r - 1, m, 1) + 1;
    }
    if(flag == 1) sum = 1;
    else sum = 2;
    for(int i = l + 1; i <= r - 1; i = m[i] + 1)
        sum += check(i, m[i], m, 0);
    return sum;
}
inline int work(int l, int r) //ll?
{
    if(l + 1 == r) return 0;
    int sum = 0;
    for(int i = l; i <= r; i = m1[i] + 1)
        if(m1[i] == m2[i]) sum += work(i + 1, m1[i] - 1);
        else sum += check(i, m1[i], m1, 0);
    for(int i = l; i <= r; i = m2[i] + 1)
        if(m1[i] != m2[i]) sum += check(i, m2[i], m2, 0);
    return sum;
}
int main()
{
    scanf("%d %s %s", &n, a + 1, b + 1);
    if(a == b)
    {
        cout << 0;
        return 0;
    }
    for(int i = 1; i <= n; i++)
    {
        if(a[i] == '(') s1[++top1] = i;
        else
        {
            m1[i] = s1[top1--];
            m1[m1[i]] = i;
        }
        if(b[i] == '(') s2[++top2] = i;
        else
        {
            m2[i] = s2[top2--];
            m2[m2[i]] = i;
        }
    }
    cout << work(1, n);
    return 0;
}
2023/1/7 21:04
加载中...