[题解]RGB Substring (hard version)-前缀和（codeforces 1196D2）

题目链接：https://codeforces.com/problemset/problem/1196/D2

 

---

 

题意：

q 个询问，每个查询将给你一个由 n 个字符组成的字符串s，每个字符都是 “R”、“G” 或 “B”。

求出更改初始字符串 s 中的最小字符数，以便更改后将有一个长度为 k 的字符串，该字符串是 s 的子字符串，也是无限字符串 “RGBRGBRGB…” 的子字符串

 

思路：

在无限字符串中有三种子串：“RGB...”，“GBR...”，“BRG...”

在这三种不同情况下，将所求字符串与原字符串比较

若不同，则贡献为 1，否则为 0

然后计算三种情况下的前缀和，枚举区间最小值

 

#include
using namespace std;
typedef long long ll;
int sum[200006][3];

int main()
{
    int t,n,m;
    string p="RGB",s;
    cin>>t;
    while(t--){
        int ans=2000000;
        cin>>n>>m;
        cin>>s;
        for(int j=0;j<3;j++){
            for(int i=1;i<=n;i++){
                if(s[i-1]!=p[(i+j)%3])
                    sum[i][j]=sum[i-1][j]+1;
                else
                    sum[i][j]=sum[i-1][j];
            }
        }
        for(int i=0;i<3;i++)
            for(int j=m;j<=n;j++)
                ans=min(sum[j][i]-sum[j-m][i],ans);
        cout<endl;
        }
    return 0;
}