hdu 5536 Chip Factory (字典樹)

題目連結

http://acm.hdu.edu.cn/showproblem.php?pid=5536

題意

給定一個數列，從數列中取出坐标不同的三個數，其中兩個求和，再和另外一個數異或，求異或值的最大值。

思路

和hdu4825相似，隻不過因為要三個坐标不同，如果直接去字典樹上比對的話不能判斷坐标，是以再比對之前先将s[i]和s[j]删除，比對完之後再添加上。

代碼

#define push_back pb
#define make_pair mk
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<string.h>
#include<set>
#include<queue>
#include<stack>
#include<functional>
using std::pair;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>PII;
const double PI=acos(-);
const int maxn =  + ;
const int maxm =  + ;
const int INF = ;
const int mod =+;
const ll inf =;
using namespace std;
int n;
struct Trie
{
    int son[maxn*][],cnt,sum[maxn*],end[maxn*];

    void init()
    {
        memset(son,,sizeof(son));
        cnt=;
        memset(sum,,sizeof(sum));
        memset(end,,sizeof(end));
    }

    void insert(int n)
    {
        int rt=;
        for(int i=;i>=;i--)
        {
            int t=(n>>i)&;
            if(son[rt][t]==) son[rt][t]=++cnt;
            rt=son[rt][t];
            sum[rt]++;
        }
        end[rt]=;
    }
    void del(int n)
    {
        int rt=;
        for(int i=;i>=;i--)
        {
            int t=(n>>i)&;
            rt=son[rt][t];
            sum[rt]--;
        }
    }

    int query(int n)
    {
        int rt=;
        int ans=;
        for(int i=;i>=;i--)
        {
            int t=((n>>i)&)^;
            if(son[rt][t]==||sum[son[rt][t]]==) t^=;
            ans|=(t<<i);
            rt=son[rt][t];
        }
        return ans;
    }
}trie;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        trie.init();
        scanf("%d",&n);
        int a[];
        for(int i=;i<n;i++)
        {
            scanf("%d",&a[i]);
            trie.insert(a[i]);
        }
        int ans=;
        for(int i=;i<n-;i++)
        {
            for(int j=i+;j<n;j++)
            {
                trie.del(a[i]);
                trie.del(a[j]);
                int res=trie.query(a[i]+a[j]);
                res^=(a[i]+a[j]);
                ans=max(ans,res);
                trie.insert(a[i]);
                trie.insert(a[j]);
            }
        }
        printf("%d\n",ans);
    }
}
           

當然這個題因為9s的時限，用暴力也不會逾時，時間為4s，而字典樹為3.8s，字典樹對這個題并沒有太大的優勢。

#define push_back pb
#define make_pair mk
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<string.h>
#include<set>
#include<queue>
#include<stack>
#include<functional>
using std::pair;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>PII;
const double PI=acos(-);
const int maxn =  + ;
const int maxm =  + ;
const int INF = ;
const int mod =+;
const ll inf =;
using namespace std;
int n;
int a[];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%d",&n);
        for(int i=;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        int res=;
        for(int i=;i<n-;i++)
        {
            for(int j=i+;j<n-;j++)
            {
                for(int k=j+;k<n;k++)
                {
                    res=max(res,(a[i]+a[j])^a[k]);
                    res=max(res,(a[i]+a[k])^a[j]);
                    res=max(res,(a[k]+a[j])^a[i]);
                }
            }
        }
        printf("%d\n",res);
    }
}