BGN53: 舞萌时间到!

思路

舞萌 DX 里每次敲击音符会得到一个判定,对应不同的 dx 分:

判定 字符 dx 分
Critical Perfect P 3
Perfect p 2
Great G 1
Good g 0
Miss m 0

给一个判定序列字符串,q 次询问,每次问区间 内的 dx 分总和。

这就是一道经典的前缀和模板题。把每个字符映射成对应的分值,预处理前缀和数组 表示前 个字符的分值之和,每次查询直接 回答:

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    vector<long long> pre(n+1, 0);
    auto score = [](char c) -> int {
        if(c=='P') return 3;
        if(c=='p') return 2;
        if(c=='G') return 1;
        return 0;
    };
    for(int i=0;i<n;i++){
        pre[i+1] = pre[i] + score(s[i]);
    }
    int q;
    cin >> q;
    while(q--){
        int l,r;
        cin >> l >> r;
        cout << pre[r] - pre[l-1] << '\n';
    }
    return 0;
}
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();
        int n = s.length();
        long[] pre = new long[n + 1];
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            int v = 0;
            if (c == 'P') v = 3;
            else if (c == 'p') v = 2;
            else if (c == 'G') v = 1;
            pre[i + 1] = pre[i] + v;
        }
        int q = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            sb.append(pre[r] - pre[l - 1]).append('\n');
        }
        System.out.print(sb);
    }
}
import sys
input = sys.stdin.readline

def main():
    s = input().strip()
    n = len(s)
    score_map = {'P': 3, 'p': 2, 'G': 1, 'g': 0, 'm': 0}
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + score_map.get(s[i], 0)
    q = int(input())
    out = []
    for _ in range(q):
        l, r = map(int, input().split())
        out.append(str(pre[r] - pre[l - 1]))
    sys.stdout.write('\n'.join(out) + '\n')

main()
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    let idx = 0;
    const s = lines[idx++].trim();
    const n = s.length;
    const scoreMap = {'P': 3, 'p': 2, 'G': 1, 'g': 0, 'm': 0};
    const pre = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + (scoreMap[s[i]] || 0);
    }
    const q = parseInt(lines[idx++]);
    const out = [];
    for (let i = 0; i < q; i++) {
        const [l, r] = lines[idx++].split(' ').map(Number);
        out.push(pre[r] - pre[l - 1]);
    }
    console.log(out.join('\n'));
});

复杂度分析

  • 时间复杂度: ,预处理前缀和 ,每次查询
  • 空间复杂度: ,存储前缀和数组。

小结

前缀和的入门题,没有任何弯弯绕。把字符映射成分值,建前缀和数组,区间求和就是做差。唯一需要注意的是下标从 1 开始, 作为哨兵,查询 就是