백준 16903번: 수열과 쿼리 20

Seungil Kim·2022년 4월 26일
0

PS

목록 보기
191/206

수열과 쿼리 20

백준 16903번: 수열과 쿼리 20

아이디어

0이랑 1만 있는 트라이를 만든다. 입력받는 정수의 맨 앞쪽 비트 (2^29)부터 쭉 훑으면서 둘 다 있으면 XOR값을 최대로 할 수 있도록 선택, 둘 중 하나만 있으면 그거 선택. 다 더하면 정답!
삭제 연산은 cnt를 감소시킨다. cnt가 0이면 그냥 없는거임.

코드

#include <bits/stdc++.h>

using namespace std;

struct Trie {
    Trie* child[2];
    bool end;
    int cnt;

    Trie() {
        memset(child, 0, sizeof(child));
        end = false;
        cnt = 1;
    }

    ~Trie() {
        for (int i = 0; i < 2; i++) {
            if (child[i]) delete child[i];
        }
    }

    void insert(int x, int idx) {
        if (idx < 0) {
            end = true;
            return;
        }
        bool next = x&(1<<idx);
        if (!child[next]) child[next] = new Trie();
        else child[next]->cnt++;
        child[next]->insert(x, idx-1);
    }

    void remove(int x, int idx) {
        cnt--;
        if (idx < 0) return;
        bool next = x&(1<<idx);
        child[next]->remove(x, idx-1);
    }
};

int solve(Trie* node, int x, int idx) {
    if (idx < 0) return 0;
    bool next = x&(1<<idx);
    if (node->child[0] && node->child[0]->cnt && node->child[1] && node->child[1]->cnt) return solve(node->child[!next], x, idx-1) + (1<<idx);
    else return node->child[0] && node->child[0]->cnt ? solve(node->child[0], x, idx-1) + (x&(1<<idx))^0 : solve(node->child[1], x, idx-1) + (x&(1<<idx))^(1<<idx);
}

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

    Trie root;
    root.insert(0, 29);
    int m;
    cin >> m;
    while (m--) {
        int q, x;
        cin >> q >> x;
        if (q == 1) root.insert(x, 29);
        else if (q == 2) root.remove(x, 29);
        else if (q == 3) cout << solve(&root, x, 29) << '\n';
    }
    
    return 0;
}

여담

맨 처음에 숫자 0이 하나 들어가 있으니 주의.
cnt가 0이 되면 메모리 해제하면서 멋있게 짜고싶었는데 실패했다. 나중에 재도전 해봐야겠다.

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

0개의 댓글