打卡信奥刷题（3319）用C++实现信奥题 P9188 [USACO23OPEN] Pareidolia S

P9188 [USACO23OPEN] Pareidolia S

题目描述

题目背景

注意：本题的时间限制为 4 秒，是默认时间限制的 2 倍。

Pareidolia 是一种现象，指的是人们倾向于在并不真正存在的地方看到熟悉的图案——例如在云中看到一张脸。可以想象，由于农夫 John 经常与奶牛接触，他常常在日常物品中看到与奶牛相关的图案。例如，如果他看到字符串 “bqessiyexbesszieb”，农夫 John 的眼睛会忽略其中的一些字母，而他看到的只是 “bessiebessie”。

给定一个字符串sss，令B(s)B(s)B(s)表示通过删除sss中的零个或多个字符后，能够形成的 “bessie” 的最大重复次数。在上面的例子中，B(“bqessiyexbesszieb")=2B(\text{``bqessiyexbesszieb"}) = 2B(“bqessiyexbesszieb")=2。

计算B(s)B(s)B(s)是一个有趣的挑战，但农夫 John 对解决一个更有趣的挑战感兴趣：给定一个长度不超过3⋅1053 \cdot 10^53⋅105的字符串ttt，且仅由字符 a-z 组成，计算所有连续子串sss的B(s)B(s)B(s)之和。

输入格式

输入由一个非空字符串组成，长度不超过3⋅1053 \cdot 10^53⋅105，且所有字符均为小写英文字母。

输出格式

输出一个数字，表示输入字符串的所有子串中能够形成的 “bessie” 的总数。

输入输出样例 #1

输入 #1

bessiebessie

输出 #1

14

输入输出样例 #2

输入 #2

abcdefghssijebessie

输出 #2

28

说明/提示

对于第一个样例，有 12 个子串恰好包含111个 “bessie”，有111个子串恰好包含222个 “bessie”，因此总数为12⋅1+1⋅2=1412 \cdot 1 + 1 \cdot 2 = 1412⋅1+1⋅2=14。

C++实现

#include<iostream>#include<cstdio>#defineintlonglongusingnamespacestd;constintN=3e5+5;intn,f[7],ans,dp[N];string s;signedmain(){cin>>s;n=s.size();s="#"+s;for(inti=1;i<=n;i++){if(s[i]=='b')f[1]=i;if(s[i]=='e')f[6]=f[5],f[2]=f[1];if(s[i]=='s')f[4]=f[3],f[3]=f[2];if(s[i]=='i')f[5]=f[4];dp[i]=dp[f[6]-1]+f[6];}for(inti=1;i<=n;i++)ans+=dp[i];printf("%lld",ans);return0;}

• 输入 3-5：字符串长度不超过500050005000。
  

• 后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容