玲珑学院OJ 1028 - Bob and Alice are playing numbers 字典树，dp

http://www.ifrog.cc/acm/problem/1028

题解处：http://www.ifrog.cc/acm/solution/4

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + ;

const double eps = 1e-;

const double INF = 1e12;

int ch[N*][],cnt[N*],tot,a[N],n,T,op,kase;

bool dp[(<<)+];

inline int newnode(){

  ++tot;

  ch[tot][]=ch[tot][]=-;

  cnt[tot]=;

  return tot;

}

void insert(int x){

  int ptr = ;

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

    int nx = (x&(<<i))?:;

    if(ch[ptr][nx]==-)

      ch[ptr][nx]=newnode();

    ptr = ch[ptr][nx];++cnt[ptr];

  }

}

void Union(int &x,int y){

  if(y==-)return;

  if(x==-)x = newnode();

  cnt[x]+=cnt[y];

  Union(ch[x][],ch[y][]);

  Union(ch[x][],ch[y][]);

}

int ask_xor(int x){

   int ret=,ptr=;

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

      int nx = (x&(<<i))?:;

      if(ch[ptr][nx^]!=-){

        ret|=(<<i);

        ptr=ch[ptr][nx^];

      }

      else ptr=ch[ptr][nx];

      if(ptr==-)break;

   }

   return ret;

}

int ask_and(){

  int ret=,ptr=;

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

    if(ch[ptr][]!=-&&cnt[ch[ptr][]]>=)

      ret|=(<<i);

    else Union(ch[ptr][],ch[ptr][]);

    ptr=ch[ptr][];

  }

  return ret;

}

void ask_or(){

  memset(dp,false,sizeof(dp));

  for(int i=;i<=n;++i)dp[a[i]]=true;

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

    for(int j=;j<=;++j)

      if(!(i&(<<j)))dp[i]|=dp[i|(<<j)];

  }

  int ret=,p=;

  int tmp[];

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

    p=;

    for(int j=;j>=;--j)

      if(!(a[i]&(<<j)))tmp[++p]=(<<j);

    int x=;

    for(int j=;j<=p;++j){

      if(dp[x|tmp[j]])x|=tmp[j];

    }

    ret=max(ret,x|a[i]);

  }

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

}

int main(){

  scanf("%d",&T);

  while(T--){

    scanf("%d%d",&n,&op);

    tot=-;newnode();int ret_xor=;

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

      scanf("%d",&a[i]);

      if(op==)ret_xor=max(ret_xor,ask_xor(a[i]));

      insert(a[i]);

    }

    printf("Case #%d: ",++kase);

    if(op==)printf("%d\n",ret_xor);

    else if(op==)printf("%d\n",ask_and());

    else ask_or();

  }

  return ;

}