题目链接：https://codeforces.com/problemset/problem/1196/D2
题意：
q个询问，每个查询将给你一个由n个字符组成的字符串s，每个字符都是“R”、“G”或“B”。
求出更改初始字符串s中的最小字符数，以便更改后将有一个长度为k的字符串，该字符串是s的子字符串，也是无限字符串“RGBRGBRGB…”的子字符串
思路：
在无限字符串中有三种子串：“RGB...”，“GBR...”，“BRG...”
在这三种不同情况下，将所求字符串与原字符串比较
若不同，则贡献为1，否则为0
然后计算三种情况下的前缀和，枚举区间最小值
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int sum[200006][3]; 5 6 int main() 7 { 8 int t,n,m; 9 string p="RGB",s; 10 cin>>t; 11 while(t--){ 12 int ans=2000000; 13 cin>>n>>m; 14 cin>>s; 15 for(int j=0;j<3;j++){ 16 for(int i=1;i<=n;i++){ 17 if(s[i-1]!=p[(i+j)%3]) 18 sum[i][j]=sum[i-1][j]+1; 19 else 20 sum[i][j]=sum[i-1][j]; 21 } 22 } 23 for(int i=0;i<3;i++) 24 for(int j=m;j<=n;j++) 25 ans=min(sum[j][i]-sum[j-m][i],ans); 26 cout<<ans<<endl; 27 } 28 return 0; 29 }
[题解]RGB Substring (hard version)-前缀和（codeforces 1196D2）
原文：https://www.cnblogs.com/Yanick/p/11290518.html