[题解]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<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int sum[][];

 int main()

 {

     int t,n,m;

     string p="RGB",s;

     cin>>t;

     while(t--){

         int ans=;

         cin>>n>>m;

         cin>>s;

         for(int j=;j<;j++){

             for(int i=;i<=n;i++){

                 if(s[i-]!=p[(i+j)%])

                     sum[i][j]=sum[i-][j]+;

                 else

                     sum[i][j]=sum[i-][j];

             }

         }

         for(int i=;i<;i++)

             for(int j=m;j<=n;j++)

                 ans=min(sum[j][i]-sum[j-m][i],ans);

         cout<<ans<<endl;

         }

     return ;

 }

巴特西

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

最新文章

热门文章