USACO乱做

P9188 [USACO23OPEN] Pareidolia S

做了好久,感觉自己好sb
这种题有一个比较显然的想法,就是\(f_i\),代表的是以\(i\)为结尾的所有字串的bessie个数。
首先有\(f_i=f_{i-1}\),因为以\(i\)结尾的个数肯定比\(i-1\)多,这是很显然的。
接下来考虑多出一个\(c_i\)所多出的贡献,接下来有两种情况,需要分开讨论。
1.\(c_i \neq e,f_i = f_{i-1}\)
2.\(c_i = e,f_i = f_{k-1}+k\)
这里的\(k\)是最后一个\(k\)到\(i\)能够有子序列bessie的位置,这个位置一定是\(d\)。
第一种情况很明显没有多出的贡献。
第二种是\(k\)到\(i\)会多出一个bessie,对于以\(1\)到\(k\)开头的字串都会多一个,而多出来的基础是从\(f_{k-1}\)的基础上转移的,很明显是对的。

code

#include <bits/stdc++.h>
#define int long long
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
    x = 0 ;rg int f(0) ; rg char c(gc()) ;
    while(!isdigit(c)) f |= (c=='-'),c = gc() ;
    while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
    x = (f?-x:x) ;
    read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
    if(x < 0) pc('-'),x = -x ;
    do stk[++tp] = x%10,x /= 10 ; while(x) ;
    while(tp) pc(stk[tp--]^48) ; //space ;
    print(p...) ;
}
bool S_GND ;
const int N = 6e5+5 ;
int n,st,ans,top(1) ;
char s[N],t[100] = " bessie" ;
int f[N],g[N],pre[510] ;
int las[N][10] ;
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
	// freopen("3.in","r",stdin) ;
	// freopen("3.out","w",stdout) ;
    cin>>s+1,n = strlen(s+1) ;
    FOR(i,1,n,1)
    {
        f[i] = f[i-1] ;
        FOR(j,0,3,1) las[i][j] = pre[j] ;
        if(s[i] == 'b') pre[0] = i ;
        if(s[i] == 'e') pre[1] = i ;
        if(s[i] == 's') pre[2] = i ;
        if(s[i] == 'i') pre[3] = i ;
        if(s[i] == 'e')
        {
        int rp = s[i]=='e'?i:las[i][1] ;
        int wz = las[las[las[las[las[rp][3]][2]][2]][1]][0] ;
        if(!wz) continue ; f[i] = f[wz-1]+wz ; //print(wz),space,print(f[i]),enter ;
        }
    }
    FOR(i,1,n,1) ans += f[i] ;
    print(ans) ;
    return 0 ;
}