Hướng dẫn giải của Bedao Mini Contest 19 - SUMF

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Subtask 1 ~(n \le 20)~:

  • Vì có tối đa ~20~ ký tự ~?~ nên ta chỉ cần duyệt qua tất cả ~2^{cntQ}~ ~(cntQ \le 20)~ trường hợp của xâu ~S~ rồi đếm số xâu con độ dài ~k~ gồm toàn ~1~ theo đúng mô tả của đề bài~.~

  • Cách làm này có độ phức tạp là ~O(n \times 2^{cntQ}).~

Subtask 2 ~(n \le 1000)~:

  • Gọi ~f(i, j)~ là tổng ~\sum f(S, k)~ nếu xâu ~S~ chỉ gồm ~i~ ký tự đầu của nó và hậu tố toàn ~1~ dài nhất của ~S~ có độ dài là ~j.~

  • Hàm ~f(i, j)~ ~(1 \le i, j \le n)~ có thể tính bằng quy hoạch động với độ phức tạp là ~O(n^2).~

Subtask 3:

  • Ta cần tính contribution của mỗi xâu con độ dài ~k~ vào tổng ~\sum f(S, k),~ nói cách khác với mỗi xâu con độ dài ~k~ của ~S~ thì có bao nhiêu cách thay số vào các dấu ~?~ mà đảm bao xâu con đó gồm toàn số ~1.~

  • Dễ thấy trong trường hợp xâu con đang xét chứa số ~0~ thì ta bỏ qua~,~ nên ta chỉ quan tâm các xâu con độ dài ~k~ chứa 2 loại ký tự ~?~ và ~1.~

  • Giả sử ta đang xét xâu con ~S[i] \dots S[i+k-1]~ chỉ chứa 2 loại ký tự ~?~ và ~1.~ Gọi ~cntQ'~ là số ký tự ~?~ nằm bên trong ~S[i] \dots S[i+k-1]~, hiển nhiên contribution của xâu đó là số trường hợp mà toàn bộ ~cntQ'~ dấu ~?~ đều được thay bằng ~1~ và có tổng cộng là ~2^{cntQ-cntQ'}~ trường hợp như thế~.~

  • Cách làm này có độ phức tạp là ~O(n).~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int mod = 1e9 + 9; 
const int maxn = 2e5 + 5; 

int n, k; 
int pw2[maxn]; 
int cntq[maxn]; 
int cnt0[maxn]; 
int cnt1[maxn]; 

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k; 
    pw2[0] = 1; 
    for(int i = 1; i <= n; i++) { 
        char c; 
        cin >> c; 
        cntq[i] = cntq[i - 1]; 
        cnt0[i] = cnt0[i - 1]; 
        cnt1[i] = cnt1[i - 1]; 
        if(c == '0') cnt0[i]++; 
        if(c == '1') cnt1[i]++; 
        if(c == '?') cntq[i]++; 

        pw2[i] = pw2[i - 1] * 2 % mod; 
    }

    int ans = 0; 
    for(int i = 1; i <= n - k + 1; i++) { 
        if(cnt0[i + k - 1] > cnt0[i - 1]) { 
            continue; 
        }
        ans += pw2[cntq[n] - cntq[i + k - 1] + cntq[i - 1]]; 
        ans %= mod; 
    }
    cout << ans; 

    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -1
    l1i3nh  đã bình luận lúc 19, Tháng 9, 2023, 0:53

    orz


  • -9
    tonblan  đã bình luận lúc 4, Tháng 6, 2023, 18:21

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.