[HDU5536] Chip Factory

传送门：>Here<

题意：给出一个长度为N的序列，求$Max\{ (a_i + a_j) ⊕ a_k \}$ (i,j,k均不相同) （$N \leq 1000$）

解题思路

　　既然$O(n^3)$不行，就考虑$O(n^2 \ log \ n)$的做法。

　　网上说得很对，凡是和xor有关的80%都是Trie……

　　将所有数的二进制建立Trie树，枚举$i,j$——此时在trie树中删去$a_i, a_j$，然后用上一篇文章的方法求得最大的异或。

　　那么这道题的关键问题就在于如何删去$a_i, a_j$？每次重新建树显然又$O(n^3)$了（还不止）。

　　考虑维护一个cnt数组，代表每个节点出现的次数。每一次删去的时候就像插入一样走一遍把对应节点的cnt减掉，然后在query的时候判定只能访问cnt>0的。这样很方便地处理好了问题

Code

　　数组要清零

/*By DennyQi*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

#define  r  read()

#define  Max(a,b)  (((a)>(b)) ? (a) : (b))

#define  Min(a,b)  (((a)<(b)) ? (a) : (b))

using namespace std;

typedef long long ll;

const int MAXN = ;

const int INF = ;

inline int read(){

    int x = ; int w = ; register int c = getchar();

    while(c ^ '-' && (c < '' || c > '')) c = getchar();

    if(c == '-') w = -, c = getchar();

    while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar(); return x * w;

}

int T,N;

int a[],ch[MAXN][],cnt[MAXN],End[MAXN],num_node;

bool b[];

inline void Convert(int x){

    memset(b, , sizeof(b));

    for(int i = ; x > ; --i){

        b[i] = x%;

        x >>= ;

    }

}

inline void Insert(int x){

    Convert(x);

    int u=;

    for(int i = ; i <= ; ++i){

        if(!ch[u][b[i]]){

            ch[u][b[i]] = ++num_node;

        }

        u = ch[u][b[i]];

        ++cnt[u];

    }

    End[u] = x;

}

inline void Clear(int x){

    Convert(x);

    int u=;

    for(int i = ; i <= ; ++i){

        u = ch[u][b[i]];

        --cnt[u];

    }

}

inline void Add(int x){

    Convert(x);

    int u=;

    for(int i = ; i <= ; ++i){

        u = ch[u][b[i]];

        ++cnt[u];

    }

}

inline int Query(int k){

    Convert(k);

    int u = ;

    for(int i = ; i <= ; ++i){

        if(!cnt[ch[u][!b[i]]]){

            u = ch[u][b[i]];

        }

        else{

            u = ch[u][!b[i]];

        }

    }

    return (k^End[u]);

}

inline void Init(){

    memset(ch,,sizeof(ch));

    memset(cnt,,sizeof(cnt));

    memset(End,,sizeof(End));

    num_node = ;

}

int main(){

    T=r;

    while(T--){

        Init();

        N=r;

        for(int i = ; i <= N; ++i){

            a[i]=r;

            Insert(a[i]);

        }

        int ans = -;

        for(int i = ; i < N; ++i){

            for(int j = i+; j <= N; ++j){

                Clear(a[i]);

                Clear(a[j]);

                ans = Max(ans, Query(a[i]+a[j]));

                Add(a[i]);

                Add(a[j]);

            }

        }

        printf("%d\n", ans);

    }

    return ;

}

巴特西

[HDU5536] Chip Factory

最新文章

热门文章