P76028 相邻相同询问 — 题解

专题： 前缀和
适用题目： 新生 OJ 本地题包中的 P76028，不要直接用于外站同名题。

解题思路

令 pre[i] 记录到第 i 位为止相邻相同对数，询问 [l,r] 使用 pre[r]-pre[l]。

复杂度

预处理 $O(n)$，每次查询 $O(1)$。

易错点

询问的相邻对起点只能落在 [l,r-1]。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    static char s[100005];scanf("%100004s",s);
    int n=(int)strlen(s),q;int *pre=calloc(n+1,sizeof(int));
    for(int i=2;i<=n;i++)pre[i]=pre[i-1]+(s[i-1]==s[i-2]);
    scanf("%d",&q);
    while(q--){int l,r;scanf("%d%d",&l,&r);printf("%d\n",pre[r]-pre[l]);}
    free(pre);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    int q;
    cin>>s>>q;
    int n=s.size();
    vector<int>pre(n+1);
    for(int i=2;i<=n;i++)pre[i]=pre[i-1]+(s[i-1]==s[i-2]);
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<pre[r]-pre[l]<<nl;
    }
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。