题解：AT_arc180_a [ARC180A] ABA and BAB

· · 题解

题意

给出一段只有 A、B 的字符串，同时可以将其中为 ABA 的子串变为 A，BAB 的子串变为 B，要求经过若干次这样的操作后，能够形成几个不同的字符串（该字符串可以包含 ABA 或 BAB）。

思路

先来研究几个样例：

ABA

显然答案有 ABA、A 两种。

ABABA

答案有 ABABA、ABA、A 三种。

ABABABA

答案有 ABABABA、ABABA、ABA、A 四种。

所以规律就是：对于这种 A、B 交替出现的字符串，答案为 \frac{n+1}{2}。

根据这个规律，我们可以把给出的字符串分成几个部分（中间是连续的 A 或 B）。

例如第三个样例：

BBABABAABABAAAABA

可以被分成 BABAB、ABABA、ABA。通过乘法原理，我们可以把三个部分的答案乘起来，即可得到最终答案。即 \frac{5+1}{2}\times\frac{5+1}{2}\times\frac{3+1}{2}=18。

具体见代码：

#include<bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
long long n,ans=1,sum=1;//从一开始，答案至少为1。
string st;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>st;
    for(int i=1;i<st.size();i++)//从一开始，避免越界。
    {
        if(st[i]!=st[i-1])sum++;//交替出现。
        else
        {
            if(sum%2==0)sum--;//若是偶数，说明是记录到了类似 ABABAB 的字符串，需要减一。
            ans*=(((sum+1)/2)%MOD);
            ans%=MOD;//记得取模。
            sum=1;
        }
    }
    if(sum!=1)ans*=(((sum+1)/2)%MOD),ans%=MOD;//如果结尾是AB交替出现的字符串。
    cout<<ans%MOD;
    return 0;
}

记录