HDU 5536 Chip Factory 字典树+贪心

给你n个数,a1....an,求(ai+aj)^ak最大的值,i不等于j不等于k

思路:先建字典树,暴力i,j每次删除他们,然后贪心找k,再恢复i,j,每次和答案取较大的,就是答案,有关异或的貌似很多都用字典树,也是醉了

/*Problem : 5536 ( Chip Factory )     Judge Status : Accepted
RunId : 15506230 Language : G++ Author : qianbi08*/ #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include <algorithm>
#include<cstring>
using namespace std;
const int maxn=;
int node[maxn][],cnt,re[maxn];
int a[];
int newnode()
{
++cnt;
node[cnt][]=node[cnt][]=-;
re[cnt]=;
return cnt;
}
void update(int v,int d)
{
int u=;
for(int i=; i>=; --i)
{
int c=(v>>i)&;
if(node[u][c]==-)
node[u][c]=newnode();
u=node[u][c];
re[u]+=d;
}
}
int getans(int v)
{
int u=,ans=;
for(int i=; i>=; --i)
{
if(u==-)break;
int c=(v>>i)&;
if(node[u][c^]!=-&&re[node[u][c^]])
{
ans=(ans|(<<i));
u=node[u][c^];
}
else u=node[u][c];
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
cnt=;
node[][]=node[][]=-;
re[]=;
for(int i=; i<=n; ++i)
scanf("%d",&a[i]),update(a[i],);
int ans=;
for(int i=; i<n; ++i)
{
update(a[i],-);
for(int j=i+; j<=n; ++j)
{
update(a[j],-);
ans=max(ans,getans(a[i]+a[j]));
update(a[j],);
}
update(a[i],);
}
printf("%d\n",ans);
}
return ;
}
上一篇:uGUI练习(五) Draggable Object


下一篇:thinkphp---ajax实现删除