Đề bài: $\href{https://codeforces.com/contest/676/problem/C}{đây}$
Tóm tắt: Cho một chuỗi chỉ gồm 2 kí tự a và b. Cho tối đa k phép biến đổi: Biến a thành b hoặc b thành a. Hỏi độ dài xâu con (liên tục) gồm các kí tự bằng nhau dài nhất là bao nhiêu ?
Lời giải: Ở bài này, ta sẽ xử dụng 2 con trỏ để giải quyết - Một kĩ thuật khá kinh điển.
Source:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- int main(){
- ll n,k;
- cin>>n>>k;
- string s;
- cin>>s;
- ll i;
- ll res=0;
- ll st=0,cnt_a=0,cnt_b=0;
- for(i=0;i<n;i++){
- if(s[i]=='a') cnt_a++; else cnt_b++;
- if(min(cnt_a,cnt_b)<=k) res=max(res,cnt_a+cnt_b);
- else (s[st++]=='a'?cnt_a--:cnt_b--);
- }
- cout<<res;
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét