RGB Substring (easy version)

Created by LXC on Fri Mar 8 11:07:57 2024

https://codeforces.com/problemset/problem/1196/D1

ranting: 1500

tag: implementation

problem

PS:此题目与类似的CF1196D2唯一的不同之处在于数据的范围。
给你$q$组询问（$1 \le q \le 2000$）
每组询问会先给你一个$n$和一个$k$（$1 \le k \le n \le 2000$）
下一行是一个字符串$s$（数据保证$s$只由大写字母$R$、$G$、$B$组成，输入数据保证所有$s$的长度和$ \le 2000$）
现在问你最少修改多少次$s$中的字母（一次只能修改一个字母），才能使得$s$的某一个子串是字符串$RGBRGBRGB…$的子串，同时该子串的长度$ \ge k$。

solution

滑动窗口，窗口大小为k，窗口内花费$O(3k)$求最少改变次数。

总复杂度$O(kn)$

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

const string C = "RGB";

auto check(auto& s, int l, int r) {
    int rt = r-l+1;
    for (int c=0; c<3; c++) {
        int cnt = 0;
        for (int i=l; i<=r; i++) {
            if (C[(c+i)%3] != s[i]) cnt++;
            // cout << s[i];
        }
        // cout << endl;
        rt = min(rt, cnt);
    }
    // cout << rt << "---\n";
    return rt;
}

void sol() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int ans = n;
    for (int i=0; i<=n-k; i++) {
        ans = min(ans, check(s, i, i+k-1));
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}