【01字典树】hdu-5536 Chip Factory

【题目链接】

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

【题意】

求一个式子,给出一组数,其中拿出ai,aj,ak三个数,使得Max{ (ai+aj) ^ ak }

【题解】

其实这里就需要大家做一个删除的操作;

类似于dfs的恢复现场的操作即可。

【代码】

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+;
int Son[N*][];
int a[N],idx;
int Cnt[N*];
void Insert( int x ){
int p = ;
for(int i=;~i;i--){
int t = x >> i & ;
if( !Son[p][t] ){
Son[p][t] = ++idx;
}
p = Son[p][t];
Cnt[p] ++ ;
}
}
void Delete( int x ){
int p = , tmp ;
for(int i=;~i;i--){
int t = x >> i & ;
if( !Son[p][t] ) break;
tmp = p ;
p = Son[tmp][t] ;
Cnt[Son[tmp][t]] --;
}
}
int Query(int x ){
int res = , p = ;
for(int i=;~i;i--){
int t = x >> i & ;
if( Son[p][t^] && Cnt[Son[p][t^]]){
res += << i;
p = Son[p][t^];
}else if( Son[p][t] && Cnt[Son[p][t]] ){
p = Son[p][t] ;
}else{
break;
}
}
return res ;
}
void Init(){
idx = ;
memset( Son , ,sizeof Son );
memset( Cnt , ,sizeof Cnt );
}
int main()
{
int T,n;
scanf("%d",&T);
while(T--){
Init();
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
Insert(a[i]);
}
int tmp,res=;
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
tmp = a[i] + a[j] ;
Delete(a[i]);
Delete(a[j]);
res = max( res , Query(tmp) );
Insert(a[i]);
Insert(a[j]);
}
}
printf("%d\n",res);
}
return ;
}
上一篇:HDU-5536 Chip Factory (字典树)


下一篇:转-【exp/imp】将US7ASCII字符集的dmp文件导入到ZHS16GBK字符集的数据库中