AT_arc180_a [ARC180A] ABA and BAB 题解

思路

首先一个浅显易得的结论，当 \(A\) 或 \(B\) 连续出现时，我们可以将它们分成两段，每段都可以看作一个独立事件，结果数只和每个独立事件的样本点有关。

我们设独立事件共有 \(tot\) 个，每个独立事件的样本点为 \(w_i\)，则显然有 \(ans=\prod_{i=1}^{tot} w_i\)。

接下来该找 \(w_i\) 的值了。先打表找规律，发现 ABA 和 ABAB 的种类数均为 2，ABABA 和 ABABAB 的种类数均为 3。浅推一下，可以得到一个由 \(A\) 和 \(B\) 交替出现总计长度为 \(n\) 的串的全部样本点为 \(\lceil {\frac{n}{2}} \rceil\)，那么答案也就呼之欲出了。

实现要点

定义一个变量 \(flag\) 用来记录上一个出现的字符以判断是否到达两个独立事件的边界。

AtCoder 不能使用 cin>>s+1 的操作，我们只能从下标为 0 开始输入。

开 long long，防止爆 int。

code：

#include<bits/stdc++.h>
using namespace std;
const int Ratio=0;
const int N=250005;
const int mod=1e9+7;
int len,n,tot,w[N];
char ch[N];
bool flag;
long long ans=1;
void Wsolve()
{
	if(n&1) n++;int res=n/2;//手动向上取整
	w[++tot]=res; 
}
int main()
{
	scanf("%d",&len);cin>>ch;n=1;
	if(ch[0]=='A') flag=1;
	else flag=0;
	for(int i=1;i<len;i++)
		if((flag&&ch[i]=='B')||(!flag&&ch[i]=='A')) flag^=1,n++;
		else Wsolve(),n=1;
	Wsolve();//最后可能有未截止的独立事件
	for(int i=1;i<=tot;i++)
		ans=ans*w[i]%mod;
	printf("%lld\n",ans);
	return Ratio; 
}

完结撒花~