樟树网站建设/精准获客
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