首页 > 代码库 > 玲珑学院OJ 1028 - Bob and Alice are playing numbers 字典树,dp

玲珑学院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 + 5;const double eps = 1e-9;const double INF = 1e12;int ch[N*60][2],cnt[N*60],tot,a[N],n,T,op,kase;bool dp[(1<<21)+5];inline int newnode(){  ++tot;  ch[tot][0]=ch[tot][1]=-1;  cnt[tot]=0;  return tot;}void insert(int x){  int ptr = 0;  for(int i=20;i>=0;--i){    int nx = (x&(1<<i))?1:0;    if(ch[ptr][nx]==-1)      ch[ptr][nx]=newnode();    ptr = ch[ptr][nx];++cnt[ptr];  }}void Union(int &x,int y){  if(y==-1)return;  if(x==-1)x = newnode();  cnt[x]+=cnt[y];  Union(ch[x][0],ch[y][0]);  Union(ch[x][1],ch[y][1]);}int ask_xor(int x){   int ret=0,ptr=0;   for(int i=20;i>=0;--i){      int nx = (x&(1<<i))?1:0;      if(ch[ptr][nx^1]!=-1){        ret|=(1<<i);        ptr=ch[ptr][nx^1];      }      else ptr=ch[ptr][nx];      if(ptr==-1)break;   }   return ret;}int ask_and(){  int ret=0,ptr=0;  for(int i=20;i>=0;--i){    if(ch[ptr][1]!=-1&&cnt[ch[ptr][1]]>=2)      ret|=(1<<i);    else Union(ch[ptr][1],ch[ptr][0]);    ptr=ch[ptr][1];  }  return ret;}void ask_or(){  memset(dp,false,sizeof(dp));  for(int i=1;i<=n;++i)dp[a[i]]=true;  for(int i=(1<<20);i>=1;--i){    for(int j=0;j<=20;++j)      if(!(i&(1<<j)))dp[i]|=dp[i|(1<<j)];  }  int ret=0,p=0;  int tmp[25];  for(int i=1;i<=n;++i){    p=0;    for(int j=20;j>=0;--j)      if(!(a[i]&(1<<j)))tmp[++p]=(1<<j);    int x=0;    for(int j=1;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=-1;newnode();int ret_xor=0;    for(int i=1;i<=n;++i){      scanf("%d",&a[i]);      if(op==2)ret_xor=max(ret_xor,ask_xor(a[i]));      insert(a[i]);    }    printf("Case #%d: ",++kase);    if(op==2)printf("%d\n",ret_xor);    else if(op==1)printf("%d\n",ask_and());    else ask_or();  }  return 0;}
View Code

 

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