CF1555D 题解

~~注意到~~当且仅当一个字符串为长度为

3

的循环节构成的情况下才能满足条件，例如 abcabcab。
所以考虑维护前缀和，每个前缀和分别代表当循环节为 abc 时需要改多少个字母，当循环节为 acb 时需要改多少个字母，当循环节为 bac 时需要改多少个字母，当循环节为 bca 时需要改多少个字母，当循环节为 cab 时需要改多少个字母，当循环节为 cba 时需要改多少个字母。

CPP

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m, l, r, sum[200010][10];
string s;
ll query(ll op, ll x, ll y){
	return sum[y][op] - sum[x - 1][op];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> s, s = '_' + s;
	for(ll i = 1; i <= n; i++){
		sum[i][1] = sum[i - 1][1] + ((i % 3 == 1 && s[i] != 'a') || (i % 3 == 2 && s[i] != 'b') || (i % 3 == 0 && s[i] != 'c'));
		sum[i][2] = sum[i - 1][2] + ((i % 3 == 1 && s[i] != 'a') || (i % 3 == 2 && s[i] != 'c') || (i % 3 == 0 && s[i] != 'b'));
		sum[i][3] = sum[i - 1][3] + ((i % 3 == 1 && s[i] != 'b') || (i % 3 == 2 && s[i] != 'a') || (i % 3 == 0 && s[i] != 'c'));
		sum[i][4] = sum[i - 1][4] + ((i % 3 == 1 && s[i] != 'b') || (i % 3 == 2 && s[i] != 'c') || (i % 3 == 0 && s[i] != 'a'));
		sum[i][5] = sum[i - 1][5] + ((i % 3 == 1 && s[i] != 'c') || (i % 3 == 2 && s[i] != 'a') || (i % 3 == 0 && s[i] != 'b'));
		sum[i][6] = sum[i - 1][6] + ((i % 3 == 1 && s[i] != 'c') || (i % 3 == 2 && s[i] != 'b') || (i % 3 == 0 && s[i] != 'a')); 
	}
	while(m--){
		cin >> l >> r;
		cout << min({query(1, l, r), query(2, l, r), query(3, l, r), query(4, l, r), query(5, l, r), query(6, l, r)}) << endl;
	}
	return 0;
}

文章操作

相关推荐

评论

CF1555D 题解