01 사전 트 리 학습

01 사전 트 리 의 응용 범위
질문: 하나의 수 치 를 집합 시 킨 다음 에 하나의 수 K 를 제시 하고 집합 중 어느 수 와 K 의 차이 점 이나 가장 큰 지 물 어 봅 니 다.문제 풀이: 수치 집합 중의 수 를 모두 바 이 너 리 문자열 로 바 꿉 니 다.그리고 이 '문자열' 을 사전 트 리 에 삽입 합 니 다.조회 할 때 뿌리 노드 에서 잎 결점 까지 옮 겨 다 니 며 매번 K 값 의 현재 숫자 와 다른 결점 을 걷는다.
01 사전 트 리 삽입 값

//  a       
int ch[32*maxn][2];//   
ll val[32*maxn];//               
int sz;

void init()//       0   
{
    memset(ch[0],0,sizeof(ch[0]));
    sz=1;
}

void insert(ll a)
{
    int u=0;//        
    for(int i=32;i>=0;i--)//     33 
    {
        int c=((a>>i)&1);//    0  1（        ）
        if(!ch[u][c])//    ，    
        {
            // sz         
            memset(ch[sz],0,sizeof(ch[sz]));//          
            val[sz]=0;
            ch[u][c]=sz++;
        }
        u=ch[u][c];//   u  c     
    }
    val[u]=a;//      
}

01 사전 트 리 조회

//   a       
ll query(ll a)
{
    int u=0;
    for(int i=32;i>=0;i--)
    {
        int c=((a>>i)&1);//     （        ）
        if(ch[u][c^1]) u=ch[u][c^1];//              (        ）
        else u=ch[u][c];
    }
    return val[u];//      ，         
}

예제: HDU 4825
http://acm.hdu.edu.cn/showproblem.php?pid=4825 Zeus 와 Prometheus 는 게임 을 했 습 니 다. Prometheus 는 Zeus 에 게 집합 을 주 었 습 니 다. 집합 에는 N 개의 정수 가 포함 되 어 있 습 니 다. 그 다음 에 Prometheus 는 Zeus 에 게 M 번 질문 을 할 것 입 니 다. 매번 질문 에 정수 S 가 포함 되 어 있 습 니 다. 그 다음 에 Zeus 는 집합 에서 정수 K 를 찾 아 K 와 S 의 차이 나 결 과 를 가장 크게 만들어 야 합 니 다.프로 메 테 우 스 는 제우스 에 게 인간 의 위대 함 을 보 여주 기 위해 제우스 가 인간 에 게 도움 을 청 할 수 있다 는 데 동의 했다.당신 은 인간 의 지혜 를 증명 할 수 있 습 니까?
Input 입력 은 여러 그룹의 테스트 데 이 터 를 포함 하고 각 그룹의 테스트 데 이 터 는 몇 줄 을 포함 합 니 다.입력 한 첫 줄 은 T 그룹 데이터 가 있 음 을 나타 내 는 정수 T (T < 10) 입 니 다.각 그룹의 데이터 의 첫 줄 에 두 개의 정수 N, M (< 1 = N, M < = 100000) 을 입력 하고 다음 줄 에는 N 개의 정수 가 포함 되 어 있 으 며 Zeus 가 얻 은 집합 을 대표 합 니 다. 그 다음 에 M 줄 은 각 줄 의 정수 S 로 Prometheus 가 묻 는 정 수 를 대표 합 니 다.모든 정수 가 2 ^ 32 를 초과 하지 않 습 니 다.
출력 은 각 그룹의 데이터 에 대해 먼저 한 줄 의 "Case \ #?:" 를 출력 해 야 합 니 다.그 중에서 물음표 에 현재 데이터 그룹 수 를 입력 하고 그룹 수 는 1 부터 계산 해 야 한다.질문 마다 정수 K 를 출력 하여 K 와 S 가 다 르 거나 값 이 가장 큽 니 다.
Sample Input 2 3 2 3 4 5 1 5 4 1 4 6 5 6 3
Sample Output Case #1: 4 3 Case #2: 4
AC 코드

#include 
#include 
#include 
#include 
typedef long long ll;
using namespace std;

const int maxn=1e5+7;

int ch[32*maxn][2];
ll val[32*maxn];
int sz;

void init()
{
    memset(ch[0],0,sizeof(ch[0]));
    sz=1;
}

void insert(ll a)
{
    int u=0;//        
    for(int i=32;i>=0;i--)//     33 
    {
        int c=((a>>i)&1);//    0  1（        ）
        if(!ch[u][c])//    ，    
        {
            // sz         
            memset(ch[sz],0,sizeof(ch[sz]));//          
            val[sz]=0;
            ch[u][c]=sz++;
        }
        u=ch[u][c];//   u  c     
    }
    val[u]=a;//      
}

ll query(ll a)
{
    int u=0;
    for(int i=32;i>=0;i--)
    {
        int c=((a>>i)&1);//     （        ）
        if(ch[u][c^1]) u=ch[u][c^1];//              (        ）
        else u=ch[u][c];
    }
    return val[u];//      ，         
}

ll a[maxn];
int main()
{
    int t,n,m,kase=0;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            insert(a[i]);
        }
        printf("Case #%d:
",++kase);
        for(int i=1;i<=m;i++)
        {
            ll x;
            scanf("%lld",&x);
            printf("%lld
",query(x));
        }
    }
    return 0;
}

debug
MLE 가 되면 memset 를 for 순환 으로 바 꿀 수 있 습 니 다. memset 은 공간 으로 시간 을 바 꾸 는 작업 이기 때 문 입 니 다.MLE 라면 int 가 터 지지 않 는 다 는 것 을 알 게 되면 롱 롱 롱 을 켜 지 마 세 요.MLE 가 그대로 라면 지침 판 01 사전 트 리 를 쓰 세 요.사 활 MLE 라면... 평소에 무엇 을 했 는 지 되 돌아 보 세 요.