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输入 #1bessiebessie输出 #114输入输出样例 #2输入 #2abcdefghssijebessie输出 #228说明/提示对于第一个样例有 12 个子串恰好包含111个 “bessie”有111个子串恰好包含222个 “bessie”因此总数为12⋅11⋅21412 \cdot 1 1 \cdot 2 1412⋅11⋅214。C实现#includeiostream#includecstdio#defineintlonglongusingnamespacestd;constintN3e55;intn,f[7],ans,dp[N];string s;signedmain(){cins;ns.size();s#s;for(inti1;in;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(inti1;in;i)ansdp[i];printf(%lld,ans);return0;}输入 3-5字符串长度不超过500050005000。后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
