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。
• 为满足“五主色齐全”，对每个右端点 r，用 last[c] 记录五个主色各自的最后出现位置，若都出现过，则允许的左端点必须满足 l ≤ minLast，其中 minLast = min(last[D], last[M], last[T], last[A], last[O])。 因为当 l ≤ minLast 时，子串 s[l..r] 一定包含五个主色各至少一次。
• 维护一个哈希表 freq 统计已允许作为起点的前缀下标的前缀值次数：当某次 minLast 增大时，把 i 从上次边界 addedUpto+1 到新的 minLast 的所有 P[i] 值加入 freq。
• 此时对固定 r，答案增量为 freq[ P[r+1] - R ]。将所有 r 的增量累加即可。

相关算法：

• 前缀和（统计辅助色数量）
• 单次线性扫描（维护五主色最后出现位置的最小值）
• 哈希计数（在允许的左端点集合上做值频统计）

整体复杂度 O(n)，只需一次线性遍历与哈希维护。

2. 复杂度分析

• 时间复杂度：每个字符被处理常数次，minLast 单调不减，每个前缀至多加入 freq 一次，因此 O(n)。
• 空间复杂度：前缀数组 O(n)，哈希表在最坏情况下存放 O(n) 个不同前缀值，故 O(n)。满足题目数据范围。

3. 代码实现

Python

# -*- coding: utf-8 -*-
# 题意实现：统计包含 D/M/T/A/O 各至少一次，且恰好 R 个其他辅助色的子串数量
# 算法：前缀和 + 最后出现位置最小值 + 允许左端点的前缀值计数

import sys

def solve_one(R, s):
    n = len(s)
    S = set("DMTAO")  # 主色集合
    # 前缀和：P[i] = s[0..i-1] 中的辅助色数量
    P = [0]*(n+1)
    for i, ch in enumerate(s, 1):
        P[i] = P[i-1] + (0 if ch in S else 1)

    # 记录五主色的最后出现位置，初始为 -1（未出现）
    last = {c: -1 for c in "DMTAO"}
    addedUpto = -1  # 已加入 freq 计数的最大可用左端点下标
    from collections import defaultdict
    freq = defaultdict(int)

    ans = 0
    for r, ch in enumerate(s):
        if ch in S:
            last[ch] = r

        # 若五主色都出现过，计算可用的最小右界对应的最大允许左端点
        minLast = min(last.values())
        if minLast != -1:
            # 把所有 l ∈ (addedUpto, minLast] 的前缀值加入计数
            while addedUpto < minLast:
                addedUpto += 1
                freq[P[addedUpto]] += 1

            target = P[r+1] - R
            ans += freq.get(target, 0)

    return ans

def main():
    data = sys.stdin.read().strip().split()
    t = int(data[0])
    idx = 1
    out = []
    for _ in range(t):
        R = int(data[idx]); idx += 1
        s = data[idx].strip(); idx += 1
        out.append(str(solve_one(R, s)))
    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

/**
 * 题意实现：统计包含 D/M/T/A/O 各至少一次，且恰好 R 个其他辅助色的子串数量
 * 算法：前缀和 + 五主色最后出现位置 + 允许左端点的前缀值计数
 * 注意：答案可能很大，使用 long
 */
public class Main {
    static long solveOne(int R, String s) {
        int n = s.length();
        // 主色集合判断
        boolean[] isMain = new boolean[26];
        for (char c : "DMTAO".toCharArray()) isMain[c - 'A'] = true;

        // 前缀和 P[i]：前 i 个字符中的辅助色数量
        int[] P = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            char ch = s.charAt(i - 1);
            P[i] = P[i - 1] + (isMain[ch - 'A'] ? 0 : 1);
        }

        // 五主色最后出现位置
        int[] last = new int[5];
        Arrays.fill(last, -1);
        // 将主色字符映射到 0..4
        int[] mapIdx = new int[26];
        Arrays.fill(mapIdx, -1);
        mapIdx['D' - 'A'] = 0;
        mapIdx['M' - 'A'] = 1;
        mapIdx['T' - 'A'] = 2;
        mapIdx['A' - 'A'] = 3;
        mapIdx['O' - 'A'] = 4;

        // 计数哈希：允许左端点的 P[l] 频次
        HashMap<Integer, Integer> freq = new HashMap<>();
        int addedUpto = -1; // 已加入的最大 l

        long ans = 0;
        for (int r = 0; r < n; r++) {
            char ch = s.charAt(r);
            int mi = mapIdx[ch - 'A'];
            if (mi != -1) last[mi] = r;

            // 若五主色都出现过
            int minLast = Integer.MAX_VALUE;
            for (int v : last) {
                if (v == -1) { minLast = -1; break; }
                if (v < minLast) minLast = v;
            }
            if (minLast != -1) {
                // 将新的可用左端点加入计数
                while (addedUpto < minLast) {
                    addedUpto++;
                    int key = P[addedUpto];
                    freq.put(key, freq.getOrDefault(key, 0) + 1);
                }
                int target = P[r + 1] - R;
                ans += freq.getOrDefault(target, 0);
            }
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        // 默认输入已合法，使用 BufferedReader + StringTokenizer
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        while (line != null && line.trim().isEmpty()) line = br.readLine();
        int T = Integer.parseInt(line.trim());
        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            String rLine = br.readLine();
            while (rLine != null && rLine.trim().isEmpty()) rLine = br.readLine();
            int R = Integer.parseInt(rLine.trim());
            String s = br.readLine().trim();
            long ans = solveOne(R, s);
            sb.append(ans).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

/*
 * 题意实现：统计包含 D/M/T/A/O 各至少一次，且恰好 R 个其他辅助色的子串数量
 * 算法：前缀和 + 五主色最后出现位置最小值 + 允许左端点的前缀值计数
 * 复杂度：O(n) 时间，O(n) 空间
 */

long long solveOne(int R, const string &s) {
    int n = (int)s.size();
    // 主色集合
    vector<int> isMain(26, 0);
    for (char c : string("DMTAO")) isMain[c - 'A'] = 1;

    // 前缀和：P[i] = s[0..i-1] 中辅助色个数
    vector<int> P(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        char ch = s[i - 1];
        P[i] = P[i - 1] + (isMain[ch - 'A'] ? 0 : 1);
    }

    // 五主色最后出现位置
    vector<int> last(5, -1);
    vector<int> mapIdx(26, -1);
    mapIdx['D' - 'A'] = 0;
    mapIdx['M' - 'A'] = 1;
    mapIdx['T' - 'A'] = 2;
    mapIdx['A' - 'A'] = 3;
    mapIdx['O' - 'A'] = 4;

    // freq: 允许左端点 l 的 P[l] 计数
    unordered_map<int, long long> freq;
    freq.reserve(n * 2 + 7);
    int addedUpto = -1; // 已加入的最大 l

    long long ans = 0;
    for (int r = 0; r < n; ++r) {
        char ch = s[r];
        int mi = mapIdx[ch - 'A'];
        if (mi != -1) last[mi] = r;

        // 计算 minLast（若有未出现则为 -1）
        int minLast = INT_MAX;
        for (int v : last) {
            if (v == -1) { minLast = -1; break; }
            minLast = min(minLast, v);
        }
        if (minLast != -1) {
            // 扩充允许的左端点集合：把新出现的 l 的 P[l] 加入计数
            while (addedUpto < minLast) {
                ++addedUpto;
                ++freq[P[addedUpto]];
            }
            int target = P[r + 1] - R;
            auto it = freq.find(target);
            if (it != freq.end()) ans += it->second;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; 
    if (!(cin >> T)) return 0;
    while (T--) {
        int R; string s;
        cin >> R >> s;
        cout << solveOne(R, s) << "\n";
    }
    return 0;
}

题目内容

多多负责少女乐队演唱会的灯光部署，乐队成员都有各自神秘的艺名：Doloris(悲伤)、Mortis(死亡)、Timoris(恐惧)、Amoris(爱)、Oblivionis(忘却)。在乐队的演出中，舞台灯光系统有着独特的密码设定--五种主色灯光分别代表五位成员的艺名首字母($D、M、T、A、O$)，每场演出如果想要点亮舞台的最终特效,则灯光变换序列中必须包含全部五种主色(至少出现过一次)，并且恰好有 $R$ 个其他辅助色的灯光。

多多已经想好了一段灯光方案 $lightSequence$ , 请你帮多多求出其中有多少种子方案可以触发舞台的最终特效(子方案为原方案中截取的一段连续的序列)

输入描述

第一行为一个整数 $T$ , 表示共有 $T$ 个测试数据 $(1<=T<=10)$

每组测试数据：

第一行为一个整数 $R$ ,表示需要搭配的其他辅助色的灯光数目 $0<=R<=[lightSequence]-5)$

第二行为灯光方案序列 $lightSequence(1<=(lightSequence) <= 100000)$ ，

其中每个字符 $ci$ 表示灯光色号 ($'A'<=ci<'Z'$ ,仅包含大写字母)

输出描述

每组数据输出一个整数，表示能够触发舞台最终特效的子方案数量，每个结果占一行

样例1

输入

1
3
DAVMTTBLMO

输出

1

说明

只有一种子方案施触发最终特效：$DAVMTTBLMO$ , 其中 $V、B、L$ 是输入要求的恰好有的 $3$ 种辅助色，剩下的都是主色，且主色齐全

样例2

输入

1
0
DOAMT

输出

1

说明

只有一种子方案能触发最终特效：$DOAMT$ , 需要的辅助色为 $0$ ,方需中全是主色，且主色齐全

样例3

输入

1
1
OYOMAOTD

输出

2

说明

触发最终特效的子方案有两种：$OYOMAOTD、YOMAOTD$，恰好有 $1$ 个输入要求的辅助色 $Y$，剩下的都是主色，且主色齐全