[洛谷题解] CF1238D AB-string

发布于 2019-10-11  523 次阅读

题目链接：CF1238D AB-string

题目描述

一个好的字符串t（下标从1开始）满足：对于其中任意一个字符，都属于一个或多个长度大于1的回文子串。

回文串是从前向后或从后向前读都一样的字符串。比如A，BAB，ABBA，BAABBBAAB都是回文串，而AB，ABBBAA，BBBA都不是。

下面是好的字符串的例子：

  • t = AABBB（其中t_1和t_2属于子串t_{1..2}，t_3，t_4和t_5属于子串t_{3..5}）

  • t = ABAA（其中t_1，t_2和t_3属于t_{1..3}，t_4属于子串t_{3..4}）

  • t = AAAAA（所有字符属于回文子串t_{1..5}）

给你一个长度n的字符串s，请计算其好的子串的数量。

输入格式

第一行一个整数n\ (1 \leq n \leq 3\cdot 10^5)，表示s的长度。

第二行一个仅由字符'A'和'B'构成的字符串s。

输出格式

一个整数，s中好的子串的数量。

样例解释

样例1：有s_{1..2}，s_{1..4}，s_{1..5}，s_{3..4}，s_{3..5}，s_{4..5}

样例2：有s_{1..2}，s_{2..3}，s_{1..3}

解题思路

注意：字符串只由'A'和'B'构成。字符下标从1开始。

我们考虑一个字符串中不在两端的字符。容易发现，这个字符一定属于一个长度大于1的回文子串。设这个字符为t_i

  • 如果 t_{i-1} =\not t_{i+1}，那么t_{i-1}和t_{i+1}中必有一个和t_i相等。不妨令t_i = t_{i+1}，那么t_i就属于t_{i..i+1}这个回文子串。

  • 如果 t_{i-1} = t_{i+1}，那么t_i属于t_{i-1..i+1}这个回文子串。

因此只需考虑两端的字符是否属于一个长度大于1的回文子串（换句话说，是否同时有一个回文前缀和回文后缀，前缀和后缀包含本身），就可以判断一个字符串是不是好的了。

接下来我们考虑在字符串s上统计。

假设当前考虑的子串从s_i开始。那么，可能存在一个字符s_j（j尽可能小，j>i），使得如果当前子串结束点在s_j之后，那么这个字符串就有一个回文前缀。

  • 如果存在一个j，那么定义next[i] = j。
  • 否则，next[i] = 0

很显然，s_{i..next[i]}是以s_i开头的，最短的回文子串。

相应地，我们定义prev[]，使s_{prev[i]..i}是s_i结尾的，最短的回文子串。很显然：

  • 如果存在j使next[j]=i，那么prev[i] = j
  • 否则，prev[i] = 0

那么如何求next数组呢？

由于字符串中只存在'A'和'B'，next[i]等于满足s_j = s_i和j>i的最小j。

有了prev和next之后，我们就可以知道符合要求的子串s_{x..y}满足下面的条件：

  • x \leq prev[y]
  • next[x] \leq y

于是我们可以用树状数组1实现统计（树状数组是一种维护序列的log(n)数据结构，功能是：单点修改，求前缀和）。细节见代码。

// status: [Accepted]
// oj:     [luogu]

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll

const int MAXN = 300002;
// next数组
int nextMatch[MAXN];
// prev数组
int prevMatch[MAXN];
int n;
char s[MAXN];

// 树状数组1
struct WxwAkIoi {
    int data[MAXN];
    static inline int lowbit(int x) {return x&-x;}
    void update(int p,int v) {
        for(int i=p;i<MAXN;i+=lowbit(i)) {
            data[i] += v;
        }
    }
    int query(int p) {
        int ret = 0;
        for(int i=p;i;i-=lowbit(i)) {
            ret += data[i];
        }
        return ret;
    }
}tr;

// 预处理next数组
void pre() {
    int prevA = -1;
    int prevB = -1;
    for(int i=1;i<=n;i++) {
        if(s[i] == 'A') {
            if(prevA != -1) nextMatch[prevA] = i;
            prevA = i;
        }
        else if(s[i] == 'B') {
            if(prevB != -1) nextMatch[prevB] = i;
            prevB = i;
        }
        else {
            cerr<<"DDoSForces AK IOI";
            exit(28403);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>n;
    cin>>(s+1);
    n = strlen(s+1);

    pre();

    // 计算prev数组
    for(int i=1;i<=n;i++) {
        if(nextMatch[i] != 0) {
            prevMatch[nextMatch[i]] = i;
        }
    }

    // 统计
    int ans = 0;
    for(int i=1;i<=n;i++) {
        if(prevMatch[i]) {
            // next[prev[i]] = i，而对于之后的i，有next[prev[i]] < new_i。
            // 这就满足了 next[x] <= y 的性质
            tr.update(prevMatch[i],1);
        }
        // 求树状数组从1到prev[i]的和。
        // 这就满足了 x <= prev[y] 的性质
        ans += tr.query(prevMatch[i]);
    }

    cout<<ans<<endl;
}

评测记录：R25031139

赏

undefined