题面

\(q\) 个询问&＃xff0c;每个询问给出一个字符串 \(s\)&＃xff0c;要你在 \(s\) 中用最小替换得到无穷字符串 RGBRGBRGB... 的长度为定值 \(k\) 的子串。

题解

一眼看过去可能是编辑距离什么的&＃xff0c;但是仔细看 Hard 下的时间复杂度不允许&＃xff0c;然后进行了一波分析...

上图模式串 2 同理。
从上图可以发现&＃xff0c;其实就是主串往后移动一位的同时模式串也往后移动一位匹配&＃xff0c;同时去掉无用信息即可。

代码

#include
#include
#include
#include
const int MAXN&＃61;2e5&＃43;5;
int q,n,m,tot[3],v[3][2],value[MAXN],ans;char str[MAXN];
int main()
{scanf("%d",&q);for(;q>&＃61;1;q--){memset(tot,0,sizeof(tot));memset(v,0,sizeof(v));ans&＃61;INT_MAX;scanf("%d %d",&n,&m);scanf("%s",str&＃43;1);for(int i&＃61;0;i<3;i&＃43;&＃43;)v[i][0]&＃61;v[i][1]&＃61;i;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){value[i]&＃61;(str[i]&＃61;&＃61;&＃39;R&＃39;)?0:(str[i]&＃61;&＃61;&＃39;G&＃39;?1:2);}for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;)for(int j&＃61;0;j<3;j&＃43;&＃43;) {if(value[i]&＃61;&＃61;v[j][1]){tot[j]&＃43;&＃43;;}v[j][1]&＃61;(v[j][1]&＃43;1)%3;//printf("%d %d %d %d %d %d\n",i,j,v[j][0],v[j][1],value[j],tot[j]);if(i&＃61;&＃61;m){ans&＃61;std::min(ans,m-tot[j]);}}for(int i&＃61;m&＃43;1;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;0;j<3;j&＃43;&＃43;){if(value[i-m]&＃61;&＃61;v[j][0]){tot[j]--;}if(value[i]&＃61;&＃61;v[j][1]){tot[j]&＃43;&＃43;;}v[j][1]&＃61;(v[j][1]&＃43;1)%3;v[j][0]&＃61;(v[j][0]&＃43;1)%3;ans&＃61;std::min(ans,m-tot[j]);//printf("%d %d %d %d %d %d\n",i,j,v[j][0],v[j][1],value[j],tot[j]);}}printf("%d\n",ans);}return 0;
}