CF313B 题解

zhang_kevin · 2022-08-17 21:47:39 · 题解

题目传送门

题目描述

给定一个长度为 n 的字符串(其中只包含 . 和 #)，还有 m 个问题，每个问题包含两个数 l，r 。 你的任务是找出每个问题的答案 p ，代表字符串由 l 位到 r 位有几位满足 s_i = s_{i+1}。

解题思路

这道题很简单，大部分人都会想到在给定的区间中暴力枚举。但是这种方法的时间复杂度是 O(nm)，会出现TLE。

因此我们要使用前缀和进行优化。前缀和是解决静态区间查询的好方法，也是解决这种问题的利器。

那这道题该如何使用前缀和呢？我们只需定义数组 f ，f_i 表示区间 (1,i) 中符合要求的位数。存储时进行 f_{i+1} = f_{i} + flag 即可，其中 flag 表示字符串的 s_i 与 s_{i+1} 是否一样。

最后询问时只需要输出 f_{r-1} - f_{l-1} 即可！

AC代码

#include<iostream>
using namespace std;
string s;
int n, m, l, r, f[100001];
int main(){
    cin >> s >> m;
    for(int i = 0; i < s.length(); i++){
        bool flag = (s[i]==s[i+1]);
        f[i+1] = f[i] + flag;
    }
    while(m--){
        cin >> l >> r;
        cout << f[r-1] - f[l-1] << endl;
    }
}