Hướng dẫn giải của Bedao Regular Contest 04 - CLOWN AND BALLS


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.

Tác giả: bedao

Xét ~n~ số nguyên đã cho dưới dạng nhị phân của chúng.

Với mỗi số nguyên, quy ước bit nhỏ nhất là bit ~0~ (tương ứng với ~2^0~). Khi đó bit thứ ~i~ tương ứng với ~2^i~.

Xét ~n~ số, nếu bit thứ ~i~ là bit ~1~ trong lẻ số thì khi chia ra ~2~ tập ~W~ và ~B~, ta thấy một trong hai tập sẽ có lẻ bit ~1~ thứ ~i~ và tập còn lại sẽ có chẵn bit ~1~ thứ ~i~. (Vì lẻ = chẵn + lẻ hoặc lẻ + chẵn).

Khi đó, vì ta lấy XOR ở mỗi tập, nên ở tập chẵn không còn ~2^i~ (chẵn bit ~1~ XOR sẽ là bit ~0~). Ngược lại, ở tập lẻ sẽ còn ~2^i~. Cho nên khi lấy kết quả tổng ~W + B~, luôn có ~2^i~ trong kết quả.

Vậy với những bit ~i~ xuất hiện lẻ lần, ở trong mọi trường hợp đều tính vào kết quả cuối cùng một lượng là ~2^i~. Ta gọi tổng của lượng không đổi này là ~ans_1~.

Điều này tương tự với việc ta không cần quan tâm đến những bit xuất hiện lẻ lần nữa. Đi lần lượt ~n~ số và tắt hết những bit xuất hiện lẻ lần của chúng.

Giờ những bit còn lại đều xuất hiện chẵn lần. Có ~2~ trường hợp là chẵn = chẵn + chẵn hoặc = lẻ + lẻ. Nghĩa là nếu ~W~ có bit ~1~ tại bit thứ ~i~ (hay nói cách khác, tập ~W~ có lẻ số có bit ~1~ tại vị trí này) thì ~B~ cũng có bit ~1~ tại bit thứ ~i~.

Từ đây suy ra ~W = B~. Khi đó, việc tối đa hóa ~W + B~ tương tự như tối đa hóa ~W~.

Bài toán trở thành cho ~n~ số ~a_i~. Hãy tìm một tập số mà tổng XOR của chúng là lớn nhất.

Bài toán trên là một bài toán cổ điển dùng Khử Gauss. Bạn đọc có thể tham khảo tại:

Cơ bản ý tưởng là: coi ~n~ số trên thành một ma trận ~n \times 61~ (Tính từ bit ~0~ tới bit ~60~). Tìm dạng ma trận bậc thang của ma trận trên bằng ~khử \ Gauss\ XOR~.

Gọi ~ans_2~ là kết quả của tổng ~XOR~ lớn nhất. Bắt đầu bằng ~ans_2 = 0~, sau đó lần lượt đi từ hàng trên cùng xuống dưới của ma trận (Gọi ~x~ là số ở hàng hiện tại), thực hiện ~ans_2 = max(ans_2, ans_2 \ XOR \ x)~.

Vì ~ans_2 = W~. Nên ~W + B = 2 \times ans_2~.

Vậy đáp án cuối cùng là: ~ans_1 + 2 \times ans_2~.

Độ phức tạp: ~O(N \times 61 \times log_2 (61))~ (Thao tác khử Gauss cần xét ~61~ bit)

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

const int N = 1e5 + 5, LG = 60;
int n, res, ans;
int a[N], basis[65];

void insertVector(int msk) {
    for2(i,LG,0) {
        if (!(msk & (1ll << i))) continue;
        if (!basis[i]) {
            basis[i] = msk;
            return;
        }
        msk ^= basis[i];
    }
}

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

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

    cin >> n;
    for1(i,1,n) {
        cin >> a[i];
        res ^= a[i];
    }

    for1(j,1,n) a[j] &= ~res;

    for1(i,1,n) insertVector(a[i]);

    for2(i,LG,0) {
        if (!basis[i]) continue;
        if (ans & (1ll << i)) continue;
        ans ^= basis[i];
    }

    cout << res + ans * 2;
}

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.