pareidolia (USACO Silver 2023 Open)

Pareidolia (USACO Silver 2023 Open)

本题是一个动态规划（DP）问题。

  1. 对于任意一个区间 [i,j][i, j]，可以贪心地统计其中出现的 "bessie" 子串个数。但是因为本题N=3⋅105N=3\cdot 10^5，所以暴力地对所有区间做贪心扫描是不行的。

  2. 定义 dp[i]dp[i] 表示区间 [i,N][i, N] 内所有子区间中 "bessie" 出现的总次数。

    那么有递推式：

    dp[i]=dp[j+1]+(N−j)dp[i] = dp[j+1] + (N - j)

    其中 jj 表示从 [i,N][i, N] 区间内第一个 "bessie" 的最后一个 'e' 字符的位置。 (N−j)(N-j) 表示以 ii 开头、以 jj 结尾的所有子区间 [i,j],[i,j+1],…,[i,N][i, j], [i, j+1], \ldots, [i, N] 都包含了这个 "bessie"。

  3. 最终答案为

    ∑i=1Ndp[i]\sum_{i=1}^N dp[i]

  4. 现在我们需要对于每个 ii 计算 jj。可以从后往前扫描字符串，预处理每个位置下一个 'b'、'e'、's'、'i' 字符的位置指针。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
char s[300005];
int nxt[300005][4];
ll dp[300005];
ll ans;
 
int main() {
    scanf("%s",s);
    n = strlen(s);
 
    // build nxt pointers
    int ptrs[4];
    memset(ptrs,-1,sizeof(ptrs));
    for (int i=n-1;i>=0;i--) {
        memcpy(nxt[i], ptrs, sizeof(ptrs));
        if (s[i] == 'b') ptrs[0] = i;
        else if (s[i] == 'e') ptrs[1] = i;
        else if (s[i] == 's') ptrs[2] = i;
        else if (s[i] == 'i') ptrs[3] = i;
    }
 
    // calculate dp
    for (int i=n-1;i>=0;i--) {
        int j = s[i] == 'b' ? i : nxt[i][0];   // find first 'b'
        if (j != -1) j = nxt[j][1];  // 'e'
        if (j != -1) j = nxt[j][2];  // 's'
        if (j != -1) j = nxt[j][2];  // 's'
        if (j != -1) j = nxt[j][3];  // 'i'
        if (j != -1) j = nxt[j][1];  // 'e'
 
        if (j != -1) dp[i] = dp[j+1] + (n-j);   // no +1 as j is 0-based
        ans += dp[i];
    }
    printf("%lld\n",ans);
 
    return 0;
}