首页 > 代码库 > 玲珑学院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;}
玲珑学院OJ 1028 - Bob and Alice are playing numbers 字典树,dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。