Hướng dẫn cho Cặp số thân thiện

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.

Tóm tắt đề bài

Cho dãy số \(a_1, a_2, \ldots, a_n\). Hai vị trí \(i\) và \(j\) (\(i < j\)) được gọi là "thân thiện" nếu tồn tại một dãy chỉ số \(i = p_1 < p_2 < \ldots < p_k = j\) sao cho \(a_{p_t} \ \& \ a_{p_{t+1}} > 0\) với mọi \(1 \leq t < k\). Với \(q\) truy vấn \((x, y)\), hãy kiểm tra xem \(x\) và \(y\) có thân thiện hay không.

Phân tích

Điều kiện: \(n, q \leq 3 \cdot 10^5\), \(a_i \leq 10^9\) (tương đương tối đa 30 bit).
Nhận xét 1: Điều kiện \(a_u \ \& \ a_v > 0\) nghĩa là tồn tại ít nhất một vị trí bit \(b\) mà cả \(a_u\) và \(a_v\) đều có bit \(b\) được bật (bằng 1).
Nhận xét 2: Bài toán có thể quy về bài toán tìm đường đi trên đồ thị. Mỗi vị trí là một đỉnh, có cạnh nối giữa \(u\) và \(v\) nếu \(a_u \ \& \ a_v > 0\). Tuy nhiên, số lượng cạnh có thể lên tới \(O(n^2)\), quá lớn để xây dựng đồ thị tường minh.
Nhận xét 3: Thay vì xét cạnh giữa các số, ta xét các bit. Một số \(a_i\) có thể "nhảy" tới bất kỳ số \(a_j\) nào đứng sau nó mà chia sẻ chung ít nhất một bit 1.

Cách làm đơn giản (Brute Force)

Ý tưởng

Với mỗi truy vấn \((x, y)\), ta sử dụng thuật toán tìm kiếm theo chiều rộng (BFS) hoặc chiều sâu (DFS) để kiểm tra xem có đường đi từ \(x\) đến \(y\) hay không. Để tối ưu một chút, ta chỉ xét các vị trí \(j > i\) mà \(a_i \ \& \ a_j > 0\).

Độ phức tạp

Thời gian: \(O(q \cdot (n + m))\) với \(m\) là số cạnh. Trong trường hợp xấu nhất là \(O(q \cdot n^2)\).
Đánh giá: Chỉ vượt qua Subtask 1 và 2 (\(n, q \leq 3000\)).

Code Brute Force

C++

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    while (q--) {
        int x, y;
        cin >> x >> y;
        vector<bool> visited(n + 1, false);
        queue<int> que;
        que.push(x);
        visited[x] = true;
        bool found = false;

        while (!que.empty()) {
            int u = que.front();
            que.pop();
            if (u == y) {
                found = true;
                break;
            }
            for (int v = u + 1; v <= y; v++) {
                if (!visited[v] && (a[u] & a[v]) > 0) {
                    visited[v] = true;
                    que.push(v);
                }
            }
        }
        if (found) cout << "Yes\n";
        else cout << "No\n";
    }
}

Python

import collections

n, q = map(int, input().split())
a = [0] + list(map(int, input().split()))

for _ in range(q):
    x, y = map(int, input().split())
    visited = [False] * (n + 1)
    queue = collections.deque([x])
    visited[x] = True
    found = False

    while queue:
        u = queue.popleft()
        if u == y:
            found = True
            break
        for v in range(u + 1, y + 1):
            if not visited[v] and (a[u] & a[v]) > 0:
                visited[v] = True
                queue.append(v)

    print("Yes" if found else "No")

Hướng giải quyết (Tối ưu)

Ý tưởng

Ta cần một cách để kiểm tra nhanh xem từ \(x\) có thể đến được \(y\) hay không. Vì \(a_i\) chỉ có tối đa 30 bit, ta sẽ tập trung vào việc di chuyển giữa các bit.

Gọi \(can\_go[i][bit]\) là vị trí nhỏ nhất \(j \geq i\) sao cho từ vị trí \(i\) có thể đi đến một vị trí \(j\) mà \(a_j\) có bit thứ \(bit\) đang bật.

Nếu \(a_i\) có bit thứ \(bit\) đang bật, thì \(can\_go[i][bit] = i\).
Nếu không, từ \(i\) ta phải nhảy đến một vị trí \(k > i\) nào đó mà \(a_i \ \& \ a_k > 0\), sau đó từ \(k\) tìm cách đi đến bit thứ \(bit\).

Các bước thực hiện

Tiền xử lý mảng \(next\_pos[i][bit]\): Là vị trí \(j > i\) gần nhất mà \(a_j\) có bit thứ \(bit\) được bật. Ta có thể tính mảng này bằng cách duyệt ngược từ \(n\) về 1.
Quy hoạch động tính \(can\_go[i][bit]\): Duyệt \(i\) từ \(n\) về 1:
- Nếu bit \(u\) có trong \(a_i\): \(can\_go[i][u] = i\).
- Nếu không: \(can\_go[i][u] = \min(can\_go[next\_pos[i][v]][u])\) với mọi bit \(v\) mà \(a_i\) có bit \(v\) được bật.
Trả lời truy vấn \((x, y)\): \(x\) và \(y\) thân thiện nếu tồn tại ít nhất một bit \(i\) mà \(a_y\) có bit \(i\) được bật VÀ \(can\_go[x][i] \leq y\). Điều này có nghĩa là từ \(x\) ta có thể đi tới một vị trí \(j \leq y\) mà \(a_j\) có bit \(i\), và từ \(j\) ta có thể nhảy trực tiếp tới \(y\) (vì cả \(a_j\) và \(a_y\) đều có bit \(i\)).

Độ phức tạp

Thời gian: \(O((n + q) \cdot \log^2(\max A_i))\) với \(\log(\max A_i) \approx 30\).
Bộ nhớ: \(O(n \cdot \log(\max A_i))\).

Code tham khảo

C++

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

const int MAXN = 300005;
const int MAXBIT = 30;
const int INF = 1e9;

int a[MAXN];
int next_pos[MAXN][MAXBIT];
int can_go[MAXN][MAXBIT];

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

    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // Bước 1: Tìm vị trí tiếp theo có bit j bật
    for (int j = 0; j < MAXBIT; j++) next_pos[n][j] = n + 1;
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 0; j < MAXBIT; j++) {
            if ((a[i + 1] >> j) & 1) next_pos[i][j] = i + 1;
            else next_pos[i][j] = next_pos[i + 1][j];
        }
    }

    // Bước 2: Quy hoạch động can_go
    for (int i = n; i >= 1; i--) {
        for (int u = 0; u < MAXBIT; u++) {
            if ((a[i] >> u) & 1) {
                can_go[i][u] = i;
            } else {
                can_go[i][u] = n + 1;
                for (int v = 0; v < MAXBIT; v++) {
                    if (((a[i] >> v) & 1) && next_pos[i][v] <= n) {
                        can_go[i][u] = min(can_go[i][u], can_go[next_pos[i][v]][u]);
                    }
                }
            }
        }
    }

    // Bước 3: Trả lời truy vấn
    while (q--) {
        int x, y;
        cin >> x >> y;
        bool possible = false;
        for (int i = 0; i < MAXBIT; i++) {
            if (((a[y] >> i) & 1) && can_go[x][i] <= y) {
                possible = true;
                break;
            }
        }
        if (possible) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}

Python

import sys

def solve():
    input = sys.stdin.read().split()
    if not input: return

    n = int(input[0])
    q = int(input[1])
    a = [0] * (n + 1)
    for i in range(1, n + 1):
        a[i] = int(input[i + 1])

    queries = []
    idx = n + 2
    for _ in range(q):
        queries.append((int(input[idx]), int(input[idx+1])))
        idx += 2

    max_bit = 30
    next_pos = [[n + 1] * max_bit for _ in range(n + 1)]

    for i in range(n - 1, 0, -1):
        for j in range(max_bit):
            if (a[i + 1] >> j) & 1:
                next_pos[i][j] = i + 1
            else:
                next_pos[i][j] = next_pos[i + 1][j]

    can_go = [[n + 1] * max_bit for _ in range(n + 1)]
    for i in range(n, 0, -1):
        bits_in_ai = [bit for bit in range(max_bit) if (a[i] >> bit) & 1]
        for u in range(max_bit):
            if (a[i] >> u) & 1:
                can_go[i][u] = i
            else:
                best = n + 1
                for v in bits_in_ai:
                    nxt = next_pos[i][v]
                    if nxt <= n:
                        if can_go[nxt][u] < best:
                            best = can_go[nxt][u]
                can_go[i][u] = best

    results = []
    for x, y in queries:
        possible = False
        for i in range(max_bit):
            if ((a[y] >> i) & 1) and can_go[x][i] <= y:
                possible = True
                break
        results.append("Yes" if possible else "No")

    sys.stdout.write("\n".join(results) + "\n")

solve()

Bình luận

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

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