Hướng dẫn giải của Mật khẩu (Đề chọn ĐTQG Phú Thọ 2014-2015)


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.

Hướng dẫn giải

Đếm các đoạn con (i, j) có độ dài ít nhất 6 và chứa đủ ba loại: chữ hoa, chữ thường, chữ số.

Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 2000~

Với mỗi i, mở rộng j và theo dõi đã gặp đủ ba loại chưa. Mỗi khi độ dài đạt ít nhất 6 và đủ ba loại thì cộng một. Nếu chỉ nộp sub này: đúng 16/28 test.

Sub 2: Nguyên lý bù trừ — ~O(n)~

Đáp án bằng tổng với dấu đan xen của số đoạn con dài ít nhất 6 không chứa các loại ký tự trong tập F, với F là tập con của ba loại. Số đoạn con dài ít nhất 6 trong một đoạn liên tiếp dài r là (r-5)(r-4)/2. Duyệt chuỗi một lần cho mỗi tập F. Đúng 28/28 test.

Chương trình hoàn chỉnh

Hàm main đọc chuỗi S. Nếu n \le 2000 gọi sub 1, còn lại gọi sub 2.

#include <bits/stdc++.h>
using namespace std;

string s;
int n;

// Phân loại ký tự: 0 = chữ hoa, 1 = chữ thường, 2 = chữ số
int typeOf(char c) {
    if (c >= 'A' && c <= 'Z') return 0;
    if (c >= 'a' && c <= 'z') return 1;
    return 2;
}

// Sub 1: vét cạn O(n^2). Với mỗi i, mở rộng j và ghi nhận đã gặp đủ ba loại chưa.
// Dùng khi n <= 2000.
void sub1() {
    long long cnt = 0;
    for (int i = 0; i < n; i++) {
        bool seen[3] = {false, false, false};
        int kinds = 0;
        for (int j = i; j < n; j++) {
            int t = typeOf(s[j]);
            if (!seen[t]) {
                seen[t] = true;
                kinds++;
            }
            int len = j - i + 1;
            if (len >= 6 && kinds == 3) cnt++;
        }
    }
    cout << cnt << "\n";
}

// Số đoạn con có độ dài >= 6 nằm trong một đoạn liên tiếp dài r: (r-5)(r-4)/2 (khi r >= 6)
long long countInRuns(int forbidMask) {
    long long res = 0;
    long long run = 0;
    for (int i = 0; i <= n; i++) {
        bool allowed = (i < n) && !((forbidMask >> typeOf(s[i])) & 1);
        if (allowed) {
            run++;
        } else {
            if (run >= 6) res += (run - 5) * (run - 4) / 2;
            run = 0;
        }
    }
    return res;
}

// Sub 2: nguyên lý bù trừ O(n). Đáp án = sum over F ⊆ {hoa, thường, số} (-1)^|F| * count(F),
// với count(F) là số đoạn con dài >= 6 không chứa loại ký tự nào trong F.
void sub2() {
    long long ans = 0;
    for (int F = 0; F < 8; F++) {
        int bits = __builtin_popcount(F);
        long long c = countInRuns(F);
        ans += (bits % 2 == 0 ? 1 : -1) * c;
    }
    cout << ans << "\n";
}

int main() {
    freopen("CAU5.INP", "r", stdin);
    freopen("CAU5.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> s;
    n = s.size();
    if (n <= 2000) sub1();
    else sub2();
    return 0;
}

Bình luận

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


Không có bình luận tại thời điểm này.