【 01 사전 트 리 】 HDU 4825 Xor Sum

HDU 4825 Xor Sum
  • 제목: N 개 수 와 x 이 또는 최대 수
  • 를 구하 십시오.
  • 사고방식: 01 사전 나무
  • [주의]
  • N 개 수 는 각 수가 최대 32 자리 이 고 먼저 int 를 초과 한 것 이 분명 하기 때문에 결 과 는 반드시 longlong 을 사용 해 야 한다.
  • N 개 수 는 각각 최대 32 자리 입 니 다. 그러면 tire 는 최대 N * 32 개의 노드 레이 블, 즉 32e 5 가 있 기 때문에 우리 tire 배열 은 4e6 를 열 수 있 습 니 다.
  • 따로 val 배열 을 열 었 습 니 다. val [i] = x 는 i 레이 블 의 결점 을 저장 하 는 곳 이 x 의 마지막 입 니 다.
  • #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #define INF 0x3f3f3f3f
    #define P(x) x>0 ? x : 0
    #define MID l + r >> 1
    #define lsn rt << 1
    #define rsn rt << 1 | 1
    #define Lson lsn, l, mid
    #define Rson rsn, mid+1, r
    #define QL Lson, ql, qr
    #define QR Rson, ql, qr
    
    using namespace std;
    typedef long long ll;
    typedef vector<int>:: iterator VITer;
    const int maxN=4e6+5;
    ll T,N,M;
    ll tire[maxN][2],val[maxN],rt,tot;
    
    void init()
    {
        memset(tire, 0, sizeof(tire));
        memset(val, 0, sizeof(val));
        tot=0;
    }
    
    void Insert(ll x)
    {
        rt=0;
        for(ll i = 31; i >= 0; i--)
        {
            ll id = (x >> i) & 1;
            if(! tire[rt][id]) tire[rt][id] = ++tot;
            rt = tire[rt][id];
        }
        val[rt] = x;
    }
    
    ll Search(ll x)
    {
        rt=0;
        for(ll i=31 ; i >= 0; i--)//      ,      
        {
            ll id= (x >> i) & 1;
            if( tire[rt][id ^ 1] )//0 ^ 1 = 1 ; (id 0 1) 1 ^ 1 = 0; (id 1 0)
                rt = tire[rt][id ^ 1];//           rt     
            else
                rt = tire[rt][id];//           id ,    ,        。          
        }
        return val[rt];
    }
    
    int main()
    {
        scanf("%lld", &T);
        for(ll Case = 1; Case <= T; Case ++)
        {
            init();
            scanf("%lld%lld", &N, &M);
            for(ll i = 1 ; i <= N; i++)
            {
                ll d; scanf("%lld", &d);
                Insert(d);
            }
            printf("Case #%lld:
    "
    , Case); for(ll i=1 ; i <= M ; i++) { ll d; scanf("%lld", &d); printf("%lld
    "
    , Search(d)); } } return 0; }

    2 브러시 1A 코드
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #define INF 0x3f3f3f3f
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int maxN = 3200000 + 7;
    int n, m;
    int tire[maxN][2], tot;
    ll val[maxN];
    void Clear(int rt)
    {
        for(int i = 0; i <= 1; i ++ ) tire[rt][i] = 0;
    }
    void Insert(ll num)
    {
        int rt = 0;
        for(int i = 31; i >= 0; i -- )
        {
            int id = num >> i & 1;//        
            if(!tire[rt][id]) { tire[rt][id] = ++ tot; Clear(tot); }
            rt = tire[rt][id];
        }
        val[rt] = num;
    }
    ll Search(ll num)
    {
        int rt = 0;
        for(int i = 31; i >= 0; i -- )
        {
            int id = num >> i & 1;
            if(tire[rt][id ^ 1]) rt = tire[rt][id ^ 1];
            else rt = tire[rt][id];
        }
        return val[rt];
    }
    int main()
    {
        int cas = 0;
        int TAT; scanf("%d", &TAT);
        while(TAT -- )
        {
            tot = 0; Clear(0);
            scanf("%d%d", &n, &m);
            for(int i = 0; i < n; i ++ )
            {
                ll num; scanf("%lld", &num);
                Insert(num);
            }
            printf("Case #%d:
    "
    , ++cas); for(int i = 0; i < m; i ++ ) { ll num; scanf("%lld", &num); printf("%lld
    "
    , Search(num)); } } return 0; }

    좋은 웹페이지 즐겨찾기