Hướng dẫn cho TEAMBUILDING (OLP MT&TN 2023 Sơ Loại Chuyên Tin)

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: Flower_On_Stone

Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).

Tutorial

Với \(n\) đủ nhỏ, ta có thể vét cạn tất cả cách chia nhóm khác nhau và đếm số lượng cách chia nhóm thỏa mãn điều kiện đề cho. Ta có thể vét cạn bằng phương pháp quay lui.

Độ phức tạp: \(\mathcal{O}(2^{n - 1})\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

int n, K;
int answer = 0;
string student;

void backtrack(int left) {
    if (left == n + 1) {
        answer++;
        return;
    }
    int diff = 0;
    for (int right = left; right <= n; right++) {
        diff += (student[right] == '1') - (student[right] == '0');
        if (abs(diff) <= K) {
            backtrack(right + 1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> K;
    cin >> student;
    student = " " + student;

    backtrack(1);

    cout << answer;

    return 0;
}

Subtask \(2\) (\(30\%\) số điểm): \(n \leq 500\).

Tutorial

Đây là một bài toán quy hoạch động có thể nói là cổ điển. Gọi dp[i] là số cách chia nhóm cho dãy từ \(1\) tới \(i\). Cho dp[0] = 1, dễ thấy dp[n] chính là đáp án. dp[i] sẽ bằng tổng các dp[j - 1] sao cho \(j \leq i\) và nhóm các học sinh từ \(j\) tới \(i\) có độ chênh lệch nam nữ không quá \(k\).

Độ phức tạp: \(\mathcal{O}(n^{3})\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5005;
const int MOD = 1e9 + 7;

int n, K, dp[MAX_N];
string student;

void add(int &x, int y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> K;
    cin >> student;
    student = " " + student;

    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            int diff = 0;
            for (int k = j; k <= i; k++) {
                diff += (student[k] == '1') - (student[k] == '0');
            }
            if (abs(diff) <= K) {
                add(dp[i], dp[j - 1]);
            }
        }
    }

    cout << dp[n];

    return 0;
}

Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Tutorial

Ta có thể cải tiến thuật toán của subtask 2 bằng cách tính chênh lệch nam nữ của một đoạn \([j,i]\) nhanh hơn. Ta có thể áp dụng phương pháp tổng tiền tố để có thể tìm tổng của một dãy liên tiếp bất kỳ trong \(\mathcal{O}(1)\). Ở đây tác giả sẽ chia sẻ một cách khác đó là duyệt \(j\) giảm dần thay vì tăng dần như trước, để có thể cập nhật chênh lệch của đoạn đang xét nhanh hơn.

Độ phức tạp: \(\mathcal{O}(n^{2})\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5005;
const int MOD = 1e9 + 7;

int n, K, dp[MAX_N];
string student;

void add(int &x, int y) {
    x += y;
    if (x >= MOD) {
        x -= MOD;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> K;
    cin >> student;
    student = " " + student;

    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        int diff = 0;
        for (int j = i; j >= 1; j--) {
            diff += (student[j] == '1') - (student[j] == '0');
            if (abs(diff) <= K) {
                add(dp[i], dp[j - 1]);
            }
        }
    }

    cout << dp[n];

    return 0;
}

Bình luận

Không có bình luận nào.