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 开始, 作为哨兵,查询
就是
。



京公网安备 11010502036488号