1. 解题思路
本题要求统计子串数目:子串中必须包含五个主色字母各至少一次(D、M、T、A、O),且恰好包含 R 个其他辅助色。
直接双指针在“恰好”约束下较难计数,我们采用前缀和 + 最后出现位置 + 计数哈希的一次线性算法。
核心思想:
- 设主色集合
S = {D, M, T, A, O}。定义前缀数组 P[i] 表示前 i 个字符中出现的辅助色个数(P[0]=0)。
对任意子串 s[l..r],辅助色个数为 P[r+1] - P[l]。若要恰好 R 个辅助色,则需 P[l] = P[r+1] - R。
P4207.第2题-多多的演唱会灯光方案
题目内容
多多负责少女乐队演唱会的灯光部署,乐队成员都有各自神秘的艺名:Doloris(悲伤)、Mortis(死亡)、Timoris(恐惧)、Amoris(爱)、Oblivionis(忘却)。在乐队的演出中,舞台灯光系统有着独特的密码设定--五种主色灯光分别代表五位成员的艺名首字母(D、M、T、A、O),每场演出如果想要点亮舞台的最终特效,则灯光变换序列中必须包含全部五种主色(至少出现过一次),并且恰好有 R 个其他辅助色的灯光。
多多已经想好了一段灯光方案 lightSequence , 请你帮多多求出其中有多少种子方案可以触发舞台的最终特效(子方案为原方案中截取的一段连续的序列)
输入描述