AtCoder-Contest122-C题-GetAC之前缀和预处理
题目的意思大概就是给你一个长度为N的字符串,M次询问区间,问你L,R中有多少个AC子列
这种题很明显是要预处理的,简单的一维前缀和处理,否则肯定超时
前缀处理只需要O(n+m)
开一个数组,下标 i 表示到第 i 个位置有多少个AC
所有答案所求的区间就可以之间相减结果 ,而不用循环去找
题面如下:
样例: 输入 8 3 ACACTACG 3 7 2 3 1 8
输出: 2 0 3
我的AC代码
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
int n , m;
cin>>n>>m;
getchar();
string str;
getline( cin , str );
int cnt[n];
fill( cnt , cnt + n , 0 );
for( int i = 1 ; i < str.length() ; i++ ){
if( str[i] == 'C' ){
if( str[i - 1] == 'A' ){
cnt[i] += cnt[i - 1] + 1;
}
else{
cnt[i] += cnt[i - 1];
}
}
else cnt[i] += cnt[i - 1];
}
// for( int i = 0 ; i < n ; i++ ){
// cout<<cnt[i]<<" ";
// if( i == n - 1 ) cout<<'\n';
// }
for( int i = 0 ; i < m ; i++ ){
int l , r;
cin>>l>>r;
cout<<cnt[r - 1] - cnt[l - 1]<<'\n';
}
return 0;
}