백준 13504번: XOR 합

Seungil Kim·2022년 4월 30일
0

PS

목록 보기
195/206

XOR 합

백준 13504번: XOR 합

아이디어

입력받은 수열의 누적 XOR을 계산해놓는다. 이 값을 전부 트라이에 삽입하고, 각각의 값과 XOR했을 때 최댓값이 부분수열 XOR의 최댓값이다.

코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int MAX = 1e5+1;
int trie[31*MAX][2];
int node = 0;

void insert(int x) {
    int idx = 0;
    for (int i = 30; i >= 0; i--) {
        bool bit = x&(1<<i);
        if (trie[idx][bit] == -1) {
            trie[idx][bit] = ++node;
        }
        idx = trie[idx][bit];
    }
}

int solve(int x) {
    int ret = 0;
    int idx = 0;
    for (int i = 30; i >= 0 ; i--) {
        bool bit = x&(1<<i);
        if (trie[idx][!bit] != -1) {
            idx = trie[idx][!bit];
            ret += (1<<i);
        }
        else {
            idx = trie[idx][bit];
        }
    }
    return ret;
}

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> v(n+1);
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            v[i] = v[i-1]^x;
        }
        memset(trie, -1, sizeof(trie));
        node = 0;
        for (int i = 0; i <= n; i++) {
            insert(v[i]);
        }
        int ans = 0;
        for (int i = 0; i <= n; i++) {
            ans = max(ans, solve(v[i]));
        }
        cout << ans << '\n';
    }
    return 0;
}

여담

trie를 이런식으로 만드는게 훨씬 간편한듯. 노드 번호를 전역 변수로 관리한다. 새로운 노드를 만들어야 하면 번호를 부여해준다.
tc가 여러개이므로 전역변수 초기화를 잊지 말자.
https://www.secmem.org/blog/2021/07/17/various-technic-solving-xor-problem/

profile
블로그 옮겼어용 https://ks1ksi.io/

0개의 댓글