HDU - 5536 Chip Factory（字典树）

超、凢脫俗 2022-06-08 10:10 96阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5536

题意：给一个长度为n的序列a，从这里选出三个序列ai,aj,ak使得（ai+aj）xor ak的值最大（不可重复选。

分析：昨天比赛写的时候想到用字典树写但是不知道怎么处理重复选的问题，然后然后想着看如果选到了重复的就回溯，but没搞出来啊，而且代码写的太丑了，后来就想着能不能先delete掉两个数，找完答案的时候再insert进去，结果a了吼吼吼。就是字典树模板题，insert delete query三个操作。

参考代码：

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    
    using namespace std;
    #define mem(a,b) memset(a,b,sizeof(a))
    #define inf 0x3f3f3f3f
    const int maxn = 1e3+10;
    int n;
    int s[maxn];
    //字典树
    int tt[maxn<<5][2];
    int cnt[maxn<<5];
    int node;
    
    void init()
    {
        mem(tt[0],0);
        mem(cnt,0);
        node = 1;
    }
    
    void insert( int num)
    {
        int rt = 0;
        for( int i = 30; i >= 0; i--)
        {
            int id = ((1<<i)&num)>>i;
            if( !tt[rt][id])
            {
                mem(tt[node],0);
                tt[rt][id] = node++;
            }
            rt = tt[rt][id];
            cnt[rt]++;
        }
    
    }
    
    void Delete( int num)
    {
        int rt = 0;
        for( int i = 30; i >= 0; i--)
        {
            int id = ((1<<i)&num)>>i;
            rt = tt[rt][id];
            cnt[rt]--;
        }
    
    }
    
    int query( int num, int p, int q)
    {
        int rt = 0;
        int ans = 0;
        for( int i = 30; i >= 0; i--)
        {
            int id = ((1<<i)&num)>>i;
            if( tt[rt][1-id] && cnt[tt[rt][1-id]] > 0)//相反的存在
            {
                ans += (1<<i);
                rt = tt[rt][1-id];
            }
            else
                rt = tt[rt][id];
        }
        return ans;
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while( T--)
        {
            init();
            scanf("%d",&n);
            for( int i = 0; i < n; i++)
            {
                scanf("%d",&s[i]);
                insert(s[i]);
            }
    
            int ans = -inf;
            for( int i = 0; i < n; i++)
            {
                for( int j = i+1; j < n; j++)
                {
                    Delete(s[i]);
                    Delete(s[j]);
                    ans = max(ans,query(s[i]+s[j],i,j));
                    insert(s[i]);
                    insert(s[j]);
                }
            }
    
            printf("%d\n",ans);
        }
    
        return 0;
    }