题目链接：https://codeforces.ml/contest/1196/problem/D2
题意：由一个RGB无限重复构成的字符串， 给定一个字符串s 问最少更换多少个字母使得其中的一个长度为k的子串 是 RGB无限重复的字符串的 子串
思路：因为只有3种可能的开头其他都是重复的， 所以外层枚举 3 种不同的可能， 然后要o (n) 处理出结果， 考虑 处理的是子串 是一段连续的区间
要o (n) 处理的话不难想到用前缀和维护， 值得注意的就是三种枚举的时候怎么才最简便
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define ull unsigned long long 5 const int maxn =2e5+10; 6 #define pb push_back 7 char t[10]={‘R‘,‘G‘,‘B‘}; 8 char s[maxn]; 9 int pre[maxn]; 10 11 int main() 12 { 13 ios::sync_with_stdio(false); 14 cin.tie(0); 15 int q; 16 cin>>q; 17 while(q--) 18 { 19 int n,k; 20 cin>>n>>k; 21 cin>>(s+1); 22 int ans=1e9; 23 for(int i=0;i<3;i++) 24 { 25 for(int j=1;j<=n;j++) 26 { 27 if(s[j]!=t[(i+j)%3]) 28 pre[j]=1; 29 else 30 pre[j]=0; 31 } 32 for(int j=1;j<=n;j++) 33 { 34 pre[j]+=pre[j-1]; 35 } 36 for(int j=k;j<=n;j++) 37 { 38 ans=min(ans,pre[j]-pre[j-k]); 39 } 40 } 41 42 cout<<ans<<‘\n‘; 43 } 44 45 46 47 48 49 50 }
Codeforces Round #575 (Div. 3) D2. RGB Substring (hard version)
原文：https://www.cnblogs.com/winfor/p/13332600.html
