题目链接

舞萌时间到！

题目描述

给定一个由 'P', 'p', 'G', 'g', 'm' 组成的判定序列字符串，分别对应 dx 分 3, 2, 1, 0, -1。现有 次询问，每次给出一个区间 ，求此区间内 dx 分的总和。

解题思路

本题的核心是求一个固定序列在多个不同区间的“分值之和”。这是一个典型的静态区间和问题，与 BGN51 的问题模型完全一致。最高效的解法是使用前缀和。

首先，我们需要将输入的判定字符串转换为一个分值数组。我们可以建立一个映射关系：

  • 'P' -> 3
  • 'p' -> 2
  • 'G' -> 1
  • 'g' -> 0
  • 'm' -> 0

然后，我们对这个分值数组 构建一个前缀和数组 。 表示从第 1 个判定到第 个判定的累计 dx 分。

前缀和数组可以在 的时间内计算出来，其中 是判定序列的长度。 构建好前缀和数组后，对于任意区间 （下标从 1 开始）的 dx 分总和，我们可以通过 在 时间内求得。

算法步骤：

  1. 读入判定字符串。
  2. 创建一个分值数组 ，遍历字符串，根据映射关系填充分值。
  3. 创建一个长度为 的前缀和数组 ，并初始化为 0。
  4. 根据分值数组 计算出前缀和数组 。
  5. 对于每一次询问 ，计算 并输出结果。

代码

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;
    int n = s.length();

    // 建立字符到分值的映射
    map<char, int> score_map;
    score_map['P'] = 3;
    score_map['p'] = 2;
    score_map['G'] = 1;
    score_map['g'] = 0;
    score_map['m'] = 0;

    // 构建前缀和数组
    vector<long long> prefix_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + score_map[s[i]];
    }

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << prefix_sum[r] - prefix_sum[l - 1] << "\n";
    }

    return 0;
}

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();

        // 建立字符到分值的映射
        Map<Character, Integer> scoreMap = new HashMap<>();
        scoreMap.put('P', 3);
        scoreMap.put('p', 2);
        scoreMap.put('G', 1);
        scoreMap.put('g', 0);
        scoreMap.put('m', 0);

        // 构建前缀和数组
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + scoreMap.get(s.charAt(i));
        }

        int q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            System.out.println(prefixSum[r] - prefixSum[l - 1]);
        }
    }
}

import sys

def main():
    s = sys.stdin.readline().strip()
    n = len(s)

    # 建立字符到分值的映射
    score_map = {'P': 3, 'p': 2, 'G': 1, 'g': 0, 'm': 0}
    
    # 构建前缀和数组
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + score_map[s[i]]

    q = int(sys.stdin.readline())
    
    # 处理所有查询
    for line in sys.stdin:
        l, r = map(int, line.split())
        print(prefix_sum[r] - prefix_sum[l - 1])

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：前缀和
  • 时间复杂度：，其中 是判定序列的长度， 是查询次数。 用于构建前缀和数组，之后的 次查询每次只需要 的时间。
  • 空间复杂度：，用于存储前缀和数组。