Thứ Tư, 18 tháng 11, 2020

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 ?

Đề 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:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main(){
  5. ll n,k;
  6. cin>>n>>k;
  7. string s;
  8. cin>>s;
  9. ll i;
  10. ll res=0;
  11. ll st=0,cnt_a=0,cnt_b=0;
  12. for(i=0;i<n;i++){
  13. if(s[i]=='a') cnt_a++; else cnt_b++;
  14. if(min(cnt_a,cnt_b)<=k) res=max(res,cnt_a+cnt_b);
  15. else (s[st++]=='a'?cnt_a--:cnt_b--);
  16. }
  17. cout<<res;
  18. return 0;
  19. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...