Hướng dẫn cho Kaninho tập đếm với xâu

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: cuom1999

Hint 1: Với mỗi \(i\), hãy tìm \(j\) lớn nhất mà \(S[i..j]\) thỏa mãn điều kiện đề bài.

Hint 2: Có thể tìm được \(j\) bằng cách nào?

Hint 3: Làm sao để kiểm tra \(S[i..j]\) thỏa mãn điều kiện?

Lời giải:

Chúng ta sẽ dùng kỹ thuật 2 con trỏ để xử lý bài toán này. Hai con trỏ \(i, j\) sẽ lưu vị trí mà \(S[i..j]\) thỏa mãn điều kiện. Trong quá trình di chuyển hai con trỏ, cần lưu mảng \(cnt[a..z]\) là số lần xuất hiện của mỗi ký tự trong xâu con hiện tại.

Đô phức tạp: \(O(n)\)


Bình luận


  • 0
    phamducanh    4:55 p.m. 30 Tháng 7, 2021

    Có thể sử dụng tìm kiếm nhị phân đc k vậy?


    • 0
      tk22nguyenquangthanh    4:26 p.m. 6 Tháng 10, 2024

      /**

      contest: https://codeforces.com/group/FxFJrQUeaZ/contest/527641
      problem: https://codeforces.com/group/FxFJrQUeaZ/contest/527641/problem/F
      rank: https://codeforces.com/group/FxFJrQUeaZ/contest/527641/standings/groupmates/true
      profile(me): https://codeforces.com/profile/ThanhSteve2k11 (k1ngch0m-imissmath-nguyenquangthanh)
      ideone: https://ideone.com/uaGOsi
      date/school/country: (SUN/06/OCT/2024-ChuVanAnSecondarySchool-DANANG-VIETNAM)
      **/

      include <bits/stdc++.h>

      using namespace std;

      define int long long

      define double long double

      define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)

      define endl "\n"

      define sz(s) (int)s.size()

      define gl(s) string s;getline(cin,s)

      define cin(n) int n;cin >> n

      define __lcm(a,b) a/__gcd(a,b)*b

      define fset(x) fixed << setprecision(x)

      define MOD (int)1e9+7

      define maxn (int)1e5+1

      void FREOPEN(){freopen(".inp","r",stdin);freopen(".out","w",stdout);}
      int cnt[255+1], pref[255+1][maxn];
      bool ok(int l,int r,int k) {
      // kt doan l->r co ok ko
      // tinh nhanh so luong tung chu cai & kt chung co vuot qua k ko
      for(int i='a';i<='z';i++) {
      // dem so luong kitu i trong doan l->r
      int cnt = pref[i][r] - pref[i][l-1];
      if (cnt>k) return false;
      }
      return true;
      }
      void k1ngch0m() {
      string s; cin >> s;
      int SZ = sz(s);
      s = '1'+s;// dich vi tri xau s ve 1
      cin(k);
      for(int i='a';i<='z';i++) {
      // mang cong don cho kitu i
      // pref[i][j] dung cho kitu da tinh so luong kitu i tu 1->j
      for(int j=1;j<=SZ;j++) {
      int x;
      if (s[j]==i) x=1;
      else x=0;
      pref[i][j] = pref[i][j-1]+x;
      }
      }
      // dem so cap i j sao cho tu i->j ko co kitu nao xuat hien qua k lan
      int ans=0;
      for(int i=1;i<=SZ;i++) {
      int l=i, r=SZ, mid, pos=i-1;
      while(l<=r) {
      mid = (l+r)/2;
      // kt doan tu i->mid co ok ko
      if (ok(i,mid,k)) pos=mid, l=mid+1;
      else r = mid-1;
      }
      ans+=pos-i+1;
      }
      cout << ans << endl;
      // C2: binary_search + prefix_sum
      }
      signed main() {
      /FREOPEN();/ FAST;
      int test=1; cin >> test;
      while (test--) k1ngch0m();
      }
      đây nha


      • 0
        thanhnkt1611    9:52 p.m. 28 Tháng 8, 2024

        được nha.
        với mỗi chỉ số i bạn tknp thằng j xa nhất thoả mãn sao cho:
        f[j]['a'] - f[i-1]['a'] <= k
        f[j]['b'] - f[i-1]['b'] <= k
        f[j]['c'] - f[i-1]['c'] <= k
        ...
        f[j]['z'] - f[i-1]['z'] <= k
        rồi áp dụng công thức tính số lượng đoạn con là được

        1 bình luận nữa