题目大意

对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。

现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。

输入样例

第一行一个正整数N (N ≤ 500,000)。第二行一个长度为N的01字符串。

输出样例

一个正整数，表示反对称子串的个数。

输入样例

11001011

输出样例

题解

最简单的方法就是二分+Hash了。

我们可以想，对于每个点$i$，如果字符串$[i - j + 1...i + j]$为反对称的，则对于满足$1 \leqslant k < j$的$k$，都有字符串$[i - k + 1...i + k]$为反对称的。

根据这个单调性，我们只需要枚举$i$，然后二分$j$即可。

#include <iostream>

#include <cstdio>

#define MAX_N (500000 + 5)

using namespace std;

typedef unsigned long long ull;

typedef const unsigned long long cull;

int n;

char s[MAX_N];

cull b = ;

ull h1[MAX_N], h2[MAX_N], pb[MAX_N];

int ans;

int main()

{

    scanf("%d%s", &n, s + );

    pb[] = ;

    for(register int i = , j = n; i <= n; ++i, --j)

    {

        h1[i] = h1[i - ] * b + (s[i] == '') + ;

        h2[j] = h2[j + ] * b + (s[j] == '') + ;

        pb[i] = pb[i - ] * b;

    }

    int lt, rt, mid;

    for(register int i = ; i <= n; ++i)

    {

        lt = ;

        rt = min(i, n - i);

        while(lt <= rt)

        {

            mid = lt + rt >> ;

            if(h1[i + mid] - h1[i - mid] * pb[mid << ] != h2[i - mid + ] - h2[i + mid + ] * pb[mid << ]) rt = mid - ;

            else lt = mid + ;

        }

        ans += rt;

    }

    printf("%d", ans);

    return ;

}

参考程序（Hash）

当然，我们也可以直接用manacher做。

其实反对称就类似回文，这里的反对称其实可以理解为对于每个字符串，左半边异或后等于右半边，我们把manacher稍微改一下即可。

注意，这里不能随枚举奇数长度的子串，因为奇数长度本身就是不可能反对称的，这样子可能会影响偶数长度子串的判断。

#include <iostream>

#include <cstdio>

#define MAX_N (500000 + 5)

using namespace std;

int n;

char s[MAX_N];

int len;

char ns[MAX_N << ];

int p[MAX_N << ];

char to[];

long long ans;

int main()

{

    scanf("%d%s", &n, s + );

    len = n <<  | ;

    ns[] = '~';

    ns[len + ] = '^';

    ns[] = '#';

    for(register int i = ; i <= n; ++i)

    {

        ns[i << ] = s[i];

        ns[i <<  | ] = '#';

    }

    to[''] = '';

    to[''] = '';

    to['#'] = '#';

    to['~'] = '~';

    to['^'] = '^';

    int rt = , mid = ;

    for(register int i = ; i <= len; i += )

    {

        if(i < rt) p[i] = min(rt - i + , p[(mid << ) - i]);

        else p[i] = ;

        while(ns[i + p[i]] == to[ns[i - p[i]]]) ++p[i];

        if(i + p[i] -  > rt)

        {

            rt = i + p[i] - ;

            mid = i;

        }

        ans += p[i] >> ;

    }

    printf("%lld", ans);

    return ;

}

参考程序（Manacher）

巴特西

【题解】Antisymmetry

题目大意

输入样例

输出样例

输入样例

输出样例

题解

最新文章

热门文章