Editorial for Bedao Mini Contest 10 - STONE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Đầu tiên để thuận tiện xử lý, ta chuyển các số dưới dạng hệ nhị phân thành hệ thập phân.

Xét bài toán dưới dạng đồ thị, ta có một đồ thị ~G~ gồm ~2^K~ đỉnh, ~2~ đỉnh bất kỳ sẽ có cạnh nối khi và chỉ khi chỉ số của ~2~ đỉnh đó khác nhau đúng ~1~ bit.

Ta tiến hành ~BFS~ từ tất cả các ~N~ đỉnh đã cho. Gọi ~x~ là giá trị lớn nhất của tất cả các đỉnh sau khi đã ~BFS~, rõ ràng đỉnh mang giá trị ~x~ sẽ tương ứng với việc đỉnh đó khác ~x~ bit so với ~N~ đỉnh ban đầu.

Với việc ta đã có được giá trị khác nhau ít nhất với toàn bộ ~N~ tính chất ban đầu, vậy kết quả bài toán sẽ là ~K - x~.

Độ phức tạp: ~O(N \times K + 2^K)~

Các bạn có thể tham khảo hàm ~BFS~ sau:

int d[1 << 21];
queue<int> q;

int bfs() {
    int u, v, ans = 0;
    while(!q.empty()) {
        u = q.front(), q.pop();
        for(int v, i = 0; i < m; i++) {
            v = u ^ (1 << i);
            if (d[v] > d[u] + 1) {
                d[v] = d[u] + 1, ans = max(ans, d[v]);
                q.push(v);
            }
        }
    }
    return ans;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.