Hướng dẫn cho LQDOJ CUP 2022 - Round 7 - QRTAB

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

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

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

Tutorial

Sử dụng duyệt trâu và duyệt nhánh cận để giải quyết bài toán.

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

Solution

C++

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

const int MAX_N = 5e1 + 2;

int n;
char b[MAX_N][MAX_N];
bool used[MAX_N];
int a[MAX_N], t[MAX_N];

bool check() {
    for (int i = 1; i <= n; i++) {
        copy(a + 1, a + n + 1, t + 1);
        for (int j = i - 1; j >= 1; j--) {
            if ((t[j + 1] < t[j] && t[j + 1] > t[j - 1]) || (t[j + 1] > t[j] && t[j + 1] < t[j - 1])) {
                t[j] = t[j + 1];
            }

            if (t[j] != a[i] && b[j][a[i]] == '1') {
                return false;
            }
        }

        for (int j = i + 1; j <= n; j++) {
            if ((t[j - 1] < t[j] && t[j - 1] > t[j + 1]) || (t[j - 1] > t[j] && t[j - 1] < t[j + 1])) {
                t[j] = t[j - 1];
            }

            if (t[j] != a[i] && b[j][a[i]] == '1') {
                return false;
            }
        }
    }

    return true;
}

int ans[MAX_N];

void backtrack(int i) {
    if (i == n + 1) {
        if (check()) {
            copy(a + 1, a + n + 1, ans + 1);
        }

        return;
    }

    for (int j = 1; j <= n; j++) {
        if (b[i][j] == '0' || used[j]) {
            continue;
        }

        a[i] = j;
        used[j] = true;
        backtrack(i + 1);
        used[j] = false;
    }
}

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

    freopen("QRTAB.inp", "r", stdin);
    freopen("QRTAB.out", "w", stdout);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> b[i][j];
        }
    }

    backtrack(1);

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';

    return 0;
}

Subtask \(3\) (\(25\%\) số điểm): \(n \leq 400\).

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

Tutorial

Nếu \(a_i=median(a_{i-1},a_i,a_{i+1})\) thì thực hiện 1 thao tác ở \(i\) sẽ không thay đổi gì
Nếu \(a_i=min(a_{i-1},a_i,a_{i+1})\) thì thực hiện 1 thao tác ở \(i\) sẽ biến \(a_i=min(a_{i-1},a_i,a_{i+1})\)
Nếu \(a_i=max(a_{i-1},a_i,a_{i+1})\) thì thực hiện 1 thao tác ở \(i\) sẽ biến \(a_i = max(a_{i-1},a_{i+1})\)
Rút ra được nhận xét 1: nếu \(a_i>a_{i+1}\) thì sẽ không bao giờ xảy ra \(a_i<a_{i+1}\) và ngược lại.
Thế nên nếu thao tác ở \(i\) có thể khiến \(a_i\) giảm, chắc chắn \(a_{i-1} < a_i > a{i+1}\) và tương tự với \(a_i\) tăng.
Và cũng có thể chắc chắn rằng \(a_i\) luôn giảm, luôn tăng hoặc giữ nguyên.
\(\Rightarrow a_i\) chỉ có thể bằng giá trị min và max của các giá trị j thỏa mãn \(B(i, j) = 1\). Gọi hai giá trị này lần lượt là \(L_i\) và \(R_i\).
Dễ thấy nếu \(L_i=R_i\) thì \(a_i=median(a_{i-1},a_i,a_{i+1})\)
Với \(L_i \neq R_i\) thì:

Nếu \(a_i=L_i\) thì \(a_{i-1} > a_i < a_{i+1}\)
Nếu \(a_i=R_i\) thì \(a_{i-1} < a_i > a_{i+1}\)
Nên chỉ cần thử các trường hợp của \(a_1\) ta có thể dễ dàng biết được các phần tử liền sau của dãy \(a\) qua các mối quan hệ ràng buộc.

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

Solution

C++

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

const int MAX_N = 5e3 + 2;

char b[MAX_N][MAX_N];
int L[MAX_N], R[MAX_N], ans[MAX_N];

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

    freopen("QRTAB.inp", "r", stdin);
    freopen("QRTAB.out", "w", stdout);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> b[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        L[i] = n + 1;
        R[i] = 0;
        for (int j = 1; j <= n; j++) {
            if (b[i][j] == '1') {
                L[i] = min(L[i], j);
                R[i] = max(R[i], j);
            }
        }
    }

    ans[1] = R[1];
    ans[n] = R[n];
    for (int i = 2; i <= n - 1; i++) {
        if (R[i] >= ans[i - 1] && ans[i - 1] <= L[i]) {
            ans[i] = R[i];
        } else {
            ans[i] = L[i];
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';

    return 0;
}

Bình luận

Tải bình luận...

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