题目传送门：http://codeforces.com/problemset/problem/1196/D2
题目大意：多组，每组给定一串仅由‘R’、‘G’、‘B’组成的字符串，以及字符串长度n和一个常数k（k<=n），设将一个字符串变成RGB形式循环的字符串需要改动a个字符，求该字符串的所有长度为k的字串的a的最小值。
十分丢人，打比赛的时候连前置的easy version都没写出来。easy version由于数据过小只要暴力即可，这里不多讲。
字符串匹配其实我先想到的是kmp，但是这里的匹配串并不是一个定长的字符串而是一个循环节，那么kmp就没办法了（弱鸡发言），大致看了一下大神的题解，然后恍然大悟，但因为看不懂代码（太困了），于是只好自己照看到的思路手写，改了一晚上终于ac了。
思路很简单，既然要求长度为k的字串的a，那我们就维护一个长度为k的区间，把这个区间套到给我们的字符串里，从头到尾挪一遍，因为每挪一格，我们只需要判断头部出去的那个元素和尾部进来的那个元素，所以复杂度大致为On,又由于只说按照RGB的顺序循环，并没有限定开头一定为R,所以每一个点要分三种情况讨论：R开头，G开头和B开头。可以看作dp，也比较像莫队，但其实都是挺基础的操作。我在储存每个点的值时开了个数组dp，然后这个dp千万不要用memset初始化，会tle，只需要在修改dp[0]的时候特判一下就行了。
讲述的可能不太清楚，欢迎邮箱上一起交流。
邮箱：332989890@qq.com
上代码
1 #include<iostream> 2 #include<cstdio> 3 #include<set> 4 #include<stdio.h> 5 #include<string.h> 6 #include<math.h> 7 #include<vector> 8 #include<stdlib.h> 9 #include<queue> 10 #include<algorithm> 11 #include<map> 12 #include<stack> 13 using namespace std; 14 char a[200005]; 15 int dp[200005][10]; 16 char c[]= {‘R‘,‘G‘,‘B‘}; 17 int k,n; 18 int plu(int p)//插入字符到队列尾 19 { 20 for(int j=0; j<3; j++) 21 { 22 if(p==0) 23 { 24 dp[p][j]=0; 25 } 26 else if(p>0&&p<k) 27 { 28 dp[p][j]=dp[p-1][j]; 29 } 30 if(a[p]!=c[(p+j)%3]) 31 { 32 dp[p][j]++; 33 } 34 } 35 return 0; 36 } 37 int mine(int s,int p)//取出队列头的字符 38 { 39 //printf("%d %d \n",s,p); 40 for(int j=0; j<3; j++) 41 { 42 43 dp[p][j]=dp[p-1][j]; 44 if(a[s]!=c[((s+j)%3)]) 45 { 46 dp[p][j]--; 47 } 48 } 49 return 0; 50 } 51 int main() 52 { 53 int q; 54 scanf("%d",&q); 55 while(q--) 56 { 57 scanf("%d%d",&n,&k); 58 scanf("%s",a); 59 if(k==1) 60 { 61 printf("0\n"); 62 } 63 else 64 { 65 int s=0;//队列头的位置 66 int p=0;//队列尾的位置 67 while(p<k) 68 { 69 plu(p); 70 p++; 71 } 72 int ans=k; 73 ans=min(min(min(dp[p-1][0],dp[p-1][1]),dp[p-1][2]),ans); 74 //printf("%d\n",ans); 75 while(p<n) 76 { 77 mine(s,p); 78 plu(p); 79 ans=min(min(min(dp[p][0],dp[p][1]),dp[p][2]),ans); 80 //printf("%d\n",ans); 81 p++; 82 s++; 83 } 84 printf("%d\n",ans); 85 } 86 } 87 return 0; 88 }
Codeforces 1196D2 RGB Substring (hard version)(维护队列)
原文：https://www.cnblogs.com/forever3329/p/11257022.html