ACdream 1063 - 밸 런 스 트 리

1. 제목 의 대의: 데이터 구 조 를 설계 하고 하나의 수 를 삽입 하 는 것 을 지원 하 며 이 구조 에서 구조 중의 어느 수 와 주어진 수의 차이 나 값 이 가장 작은 지 조회 할 수 있 습 니 다.
2. 분석: 이것 은 어떻게 하 는 것 입 니까? 바로 trie 나무 입 니 다. 우 리 는 trie 나 무 를 만 들 고 나 무 를 01 진법 으로 저장 한 다음 에 조회 할 때...
저 희 는 욕심 내 서 트 리 에서 쭉 걸 어 요.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct Trie{
    int ch[1000000][3];
    int num;
    inline void insert(int k){
        int u = 0;
        for(int i = 30; i >= 0; i --){
            int s = ((1 << i) & k);
            if(s){
                if(!ch[u][1]){
                    num ++;
                    ch[u][1] = num; 
                }
                u = ch[u][1];
            }
            else{
                if(!ch[u][0]){
                    num ++;
                    ch[u][0] = num;
                }
                u = ch[u][0];
            }
        }
        return;
    }
    inline int qmin(int k){
        int u = 0;
        int ret = 0;
        for(int i = 30; i >= 0; i --){
            int s = ((1 << i) & k);
            if(s) {
                if(ch[u][1]){
                    u = ch[u][1];
                    ret += (1 << i);
                }
                else{
                    u = ch[u][0];
                }
            }
            else{
                if(ch[u][0]){
                    u = ch[u][0];
                }
                else{
                    u = ch[u][1];
                    ret += (1 << i);
                }
            }
        }
        return ret;
    }
    inline int qmax(int k){
        int u = 0;
        int ret = 0;
        for(int i = 30; i >= 0; i --){
            int s = ((1 << i) & k);
            if(s) {
                if(ch[u][0]){
                    u = ch[u][0];
                }
                else{
                    u = ch[u][1];
                    ret += (1 << i);
                }
            }
            else{
                if(ch[u][1]){
                    u = ch[u][1];
                    ret += (1 << i);
                }
                else{
                    u = ch[u][0];
                }
            }
        }
        return ret;
    }
} wt;
int main(){
    int T;
    scanf("%d", &T);
    while(T --){
        memset(wt.ch, 0, sizeof(wt.ch));
        wt.num = 0;
        int n;
        scanf("%d", &n);
        char str[10];
        int k;
        for(int i = 1; i <= n; i ++){
            scanf("%s", str);
            scanf("%d", &k);
            if(str[2] == 's'){
                wt.insert(k); 
            }
            else if(str[2] == 'i'){
                int ans = wt.qmin(k);
                printf("%d
", ans^k); } else { int ans = wt.qmax(k); printf("%d
", ans^k);; } } } return 0; }

좋은 웹페이지 즐겨찾기