考虑枚举每一个位置作为可能子段的起点，然后对以这个位置为起点的所有情况下的答案取 $min$
当固定了起点 $i$ 并且固定了起点 $i$ 最终的字符时，答案也固定了
发现对于所有与 $i \mod 3$ 相同的位置的字符和 $i$ 位置的字符是一样的
所有 $j \mod 3 = (i+1) \mod 3$位置的字符也都是一样的并且是可以确定的
所有 $j \mod 3 = (i+2) \mod 3$位置的字符也都是一样的并且是确定的
维护 $cnt[0/1/2][0/1/2]$ 表示当前子段所有位置 $\mod 3$ 意义下为 $0/1/2$ ，全部变成 $0/1/2$ （分别对应 $R,G,B$）的代价
那么答案可以很快计算
动态维护 $cnt$ 即可，具体看代码，很简单
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=4e5+7,INF=1e9; int Q,n,m,cnt[3][3],ans; char s[N]; inline void up(int i,int v) { if(s[i]==‘R‘) cnt[i%3][1]+=v,cnt[i%3][2]+=v; if(s[i]==‘G‘) cnt[i%3][0]+=v,cnt[i%3][2]+=v; if(s[i]==‘B‘) cnt[i%3][0]+=v,cnt[i%3][1]+=v; } int main() { Q=read(); while(Q--) { n=read(),m=read(); scanf("%s",s+1); ans=INF; memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n;i++) { up(i,1); if(i>m) up(i-m,-1); if(i<m) continue; for(int j=0;j<3;j++) { int t=0; for(int k=0;k<3;k++) t+=cnt[k][(j+k)%3]; ans=min(ans,t); } } printf("%d\n",ans); } return 0; }
Codeforces 1196D2. RGB Substring (hard version)
原文：https://www.cnblogs.com/LLTYYC/p/11603133.html