题目描述

难度分:$922$

输入$n(1 \leq n \leq 10^4)$和$n$个字符串，每个字符串只包含大写字母，长度在$[2,10]$中。

将这些字符串按照某种顺序相连，得到字符串$s$。

问：$s$中最多可以有多少个连续子串是AB？

输入样例$1$

3
ABCA
XBAZ
BAD

输出样例$1$

2

输入样例$2$

9
BEWPVCRWH
ZZNQYIJX
BAVREA
PA
HJMYITEOX
BCJHMRMNK
BP
QVFABZ
PRGKSPUNA

输出样例$2$

4

输入样例$3$

7
RABYBBE
JOZ
BMHQUVA
BPA
ISU
MCMABAOBHZ
SZMEHMA

输出样例$3$

4

算法

贪心构造

有这样一种贪心的构造方案，将所有字符串分成$4$类：

1. 不是B开头，但是A结尾；
2. 是B开头，且是A结尾；
3. 是B开头，但不是A结尾；
4. 既不是B开头，也不是A结尾。

按照如下优先级连接出$s$串：

1. 先用$1$类开头；
2. 然后让$2$类首尾相连用尽（因为$2$类的优势就在于首尾有可能能够凑出边缘AB，尽量发挥这个优势）；
3. 接下来连一个$3$类，又凑出一个连接处的AB；
4. 然后交替使用$1$和$3$类，直到两者用尽；
5. 最后把$4$类全部连接上即可，反正$4$类不会产生额外的AB，原串中有多少个AB它就能贡献多少个AB，不可能再多了。

复杂度分析

时间复杂度

一共遍历了输入的$n$个字符串，每个字符串的长度在$10$以内，因此构造出的连接串$s$是$O(n)$规模的，这也是算法的时间复杂度。

空间复杂度

保存输入的$n$个字符串，空间为$O(n)$；构造出来的答案串$s$为$10n$规模，仍然是$O(n)$，因此算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<string> a, b, c, d;
    for(int i = 0; i < n; i++) {
        string word;
        cin >> word;
        if(word[0] == 'B') {
            if(word.back() == 'A') a.push_back(word);   // B开头A结尾的
            else b.push_back(word);                     // B开头不是A结尾的
        }else {
            if(word.back() == 'A') c.push_back(word);   // 不是B开头，但是A结尾的
            else d.push_back(word);                     // 不是B开头，也不是A结尾的
        }
    }
    int i = 0, j = 0, k = 0, l = 0;
    string s;
    while(i < a.size() || j < b.size() || k < c.size()) {
        if(k < c.size()) {
            s += c[k++];
        }
        while(i < a.size()) {
            s += a[i++];
        }
        if(j < b.size()) {
            s += b[j++];
        }
    }
    while(l < d.size()) {
        s += d[l++];
    }
    int ans = 0;
    for(int i = 1; i < s.size(); i++) {
        if(s[i - 1] == 'A' && s[i] == 'B') ans++;
    }
    cout << ans << endl;
    return 0;
}