D2.RGBSubstring(hardversion)(尺取)

Problem - 1196D2 - Codeforces

通用领域

医学

计算机

金融经济

你有一个包含n个字符的字符串s，每个字符是'R'， 'G'或'B'。

你还得到一个整数k。你的任务是改变初始字符串s中的最小字符数，这样在改变之后，将会有一个长度为k的字符串，它是s的子字符串，也是无限字符串“RGBRGBRGB…”的子字符串。

字符串A是字符串b的子字符串，如果存在正整数i，使得a1=bi, a2=bi+1, a3=bi+2，…、| | = bi + | |−1。例如，字符串“GBRG”，“B”，“BR”是无限字符串“RGBRGBRGB…”的子字符串，而“GR”，“RGR”和“GGG”不是。

你必须回答q个独立的问题。

输入

输入的第一行包含一个整数q(1≤q≤2⋅105)——查询次数。然后是q次查询。

查询的第一行包含两个整数n和k(1≤k≤n≤2⋅105)——字符串的长度s和子字符串的长度。

查询的第二行包含一个字符串s，由n个字符'R'， 'G'和'B'组成。

保证所有查询的n个数之和不超过2⋅105(∑n≤2⋅105)。

输出

对于每个查询，打印一个整数-初始字符串s中需要更改的最小字符数，这样更改后将有一个长度为k的子字符串s，该子字符串也是无限字符串“RGBRGBRGB…”的子字符串。

例子

inputCopy

3.

5个2

BGGGG

5个3

RBRGR

５ ５

BBBRR

outputCopy

1

0

3.

请注意

在第一个例子中，可以将第一个字符改为'R'，得到子字符串“RG”，或者将第二个字符改为'R'，得到子字符串“BR”，或者将第三、第四或第五个字符改为'B'，得到子字符串“GB”。

在第二个例子中，子字符串是“BRG”。

题解: 我们枚举以三种字母开头的方式,尺取每k段的不一样需要修改的最小值

#include<iostream> #include<algorithm> #include<string> #include<queue> #include<vector> #include<map> #include<cstring> #include<cmath> #include<set> using namespace std; #define int long long typedef pair<int,int> PII; char s[200005]; char p []={"RGB"}; int cnt[200050]; void solve() { int n,k; cin >> n >> k; cin >> s; int ans = 1e9; for(int d = 0;d < 3;d ++) { int c = 0; for(int i = 0;i < n;i++) { cnt[i] = (s[i]!=p[(d+i)%3]); c += cnt[i]; if(i - k >= 0) { c -= cnt[i-k]; } if(i >= k-1) { ans = min(ans,c); } } } cout << ans<<"\n"; } //1 2 3 4 5 signed main(){ // ios::sync_with_stdio(false); // cin.tie(0); // cout.tie(0); int t = 1; cin >> t; while(t--) { solve(); } } //5 2 //3 12