USACO23OPEN-Silver C

题目来源

洛谷： USACO23OPEN-Pareidolia(C)

SPOJ：USACO23OPEN-Pareidolia(C)

题解： USACO23OPEN-Pareidolia(C)

题目背景

$\qquad$$Pareidolia$ 是一种现象，你的眼睛倾向于在不存在的图像中看到熟悉的模式，例如在云中看到一张脸。正如你所想象的那样，由于农夫约翰经常与奶牛接触，他经常在日常物品中看到与奶牛相关的图案。例如，如果他看着字符串“$bqessiyexbesszieb$”，农夫约翰的眼睛会忽略一些字母，他所看到的只是“$bessieessie$”。

题面描述

$\qquad$给定一个字符串 $s$ ，$s$ 仅包含小写英语字母 $a～z$，$s$ 的长度不超过 $3\times 10^5$。

$\qquad$定义 $B(s)$ 表示把 $s$ 中的若干个字母删去后，形成尽量多个 bessie 相连的形式 (bessiebessiebessieb...)，返回 bessie 的最大数量。如 $B(bqessiyexbesszieb)=2$。

$\qquad$对字符串 $s$ 计算 $B(s)$ 是一个有趣的挑战，但农夫约翰想到了一个更有趣的挑战：对 $s$ 的所有子串进行计算 $B$ 函数，并求和。

输入格式

$\qquad$输入一个字符串 $s$ ，该字符串仅包含小写英语字母 $a～z$，其的长度不超过 $3\times 10^5$。

输出格式

$\qquad$输出一个整数，表示对 $s$ 的所有子串进行计算 $B$ 函数后的和。

样例

输入数据 1

bessiebessie

输出数据 1

样例1解释

$\qquad$有 $12$ 个子字符串$(b,e,s,s,i,e,b,e,s,s,i,e)$正好包含 $11$ 个 bessie；

$\qquad$有 $1$ 个字符串 $(bessiebessie)$ 正好包含 $2$ 个 bessie；

$\qquad$因此总数为 $12 \times 1+1 \times 2=14$。

输入数据 2

abcdefghssijebessie

输出数据 2

数据规模与约定

测试点 $3～5$ ：输入 $s$ 的长度不超过 $5000$。
测试点 $6～12$ ：输入 $s$ 的长度不超过 $3\times 10^5$。

题解（Solution）

$\qquad$SPOJ 题解：

$\qquad$首先我们设 $f_{i}$ 表示以 $i$ 作为结尾的区间中总共有多少 bessie。

$\qquad$考虑转移。

$\qquad$首先我们需要找到最近的一个 bessie，我们可以考虑设一个 $lst_{i}$ 表示找到的上一个 bessie 的前 $i$ 项的起始位置。

$\qquad$举个例子，字符串 bessie 就有 $l s t_{i}=1(1 \leq i \leq 6)$ .

$\qquad$那这个怎么算呢? 我们找到一个字符，先设想其是 bessie 哪一位，设为 $x$ 位，则它的开头显然是 $l s t_{x-1}$

$\qquad$接下来，我们把贡献分成两份，一份是上一个 bessie 的贡献，一份是其他 bessie 的贡献。

$\qquad$后者的贡献我们发现就是 $f_{l s t_{6}-1}$ ，因为往后的字符串与我们当前的这个 bessie 不可以同时出现。

$\qquad$对于当前的字符串，我们发现对于 $l \in\left[1, l s t_{6}\right]$ 而言都可以包含当前这个 bessie，因此 bessie 总数会增加 $l s t_{6}$ .

$\qquad$得转移方程：$f_{i}=f_{l s t_{6}-1}+l s t_{6}$.

$\qquad$而问题问的是所有区间，所有我们需要把它们加起来，即：$\text { ans }=\sum_{i=1}^{n}f_{i}$.

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int N = 301234;
char s[N];
int n,lst[N],f[N],ans;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	cin>>(s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++){//bessie 
		if(s[i]=='b') lst[1]=i;
		if(s[i]=='e') lst[6]=lst[5],lst[2]=lst[1];
		if(s[i]=='s') lst[4]=lst[3],lst[3]=lst[2];
		if(s[i]=='i') lst[5]=lst[4];
		f[i]=f[lst[6]-1]+lst[6];
	}For(i,1,n) ans+=f[i];
	return cout<<ans<<'\n',0;
}