Maximum

GameFreak · 2022-07-21 08:35:03 · 题解

Maximum最大值 TJ

这垃圾题目，放在字典树题单里面却用一堆乱七八糟的东西。。。

题目大意

给你N个数，一种位运算，任选两数计算，求出能得到的最大值

思路

三个位运算，我们分类讨论做一波：

• xor 这个简单，Trie就可以做，更方便的是把B题的核心代码粘过来
• and 与运算非常鬼畜特别，两个都为1时才为1，于是整体N个数的情况如下：

  1. 当前这位有两个及以上的1，可以通过与运算凑出一个1来
  2. 当前这位凑不出1，怎么选也不影响计算结果
  3. 于是我们可以用BFS的思想，从高位到低位逐一判断。遇见情况1，就只保留队列中的情况1（高位为1一定比低位为1更优）；否则全部保留（结果尚不确定）

• or 或运算采取了更为玄学巧妙的贪心，其思想如下：

  1. 对于一个数每一位，若当前位有一位为1，那么这一位怎么也搞不成0了，于是不用管它；若当前位为0，就能够通过查找党前位为1的数字，把他变成1
  2. 对于一个数，二进制表示后，若它的某一子集某位为1，他这一位也为1
  3. 我们只关心最终答案，而不在乎是哪两个数把答案乱搞出来的
  4. 基于上述，我们可以预处理出每个数的子集，就能O（1）查询某一位是否可以存在为1的情况，一路贪心到最低位，就可以得到最终答案

得出算法后，我们就开始写代码：

核心代码：

注：inline和快读是我平时卡常用的优化时间的，但你也可以不写只是没我快而已

另外，我的数字是用now数组存的，老是写混。。。

• xor

  //xor 太简单，不做注释
  inline void insert(int n){
  int p=0;
  for(int i=20;i>=0;i--){
      int op=(n>>i)&1;
      if(!trie[p][op]) trie[p][op]=++cnt;
      p=trie[p][op];
  }
  }
  inline int searchxor(int n){
  int p=0,num=0;
  for(int i=20;i>=0;i--){
      int op=(n>>i)&1;
      if(trie[p][op^1]) p=trie[p][op^1],num=num<<1|1;
      else p=trie[p][op],num<<=1;
  }
  return num;
  }

• and

  inline int searchand(int n){
  memset(vis,0,sizeof vis);//vis表示这个数字是否已被排除。多组数据记得清空
  for(int i=20;i>=0;i--){//从高到低
      int cnt=0;
    //判断1的个数
      for(int j=1;j<=n;j++) if(!vis[j]) cnt+=(now[j]>>i)&1;//没有被排除，判断更改（用加法代替了）
      if(cnt==2){//刚好两个1，直接得答案（不特判问题应该也不大。。。）
          int f=-1;
          for(int j=1;j<=n;j++)
              if(!vis[j]&&((now[j]>>i)&1)&&f==-1) f=now[j];//找第一个
              else if(!vis[j]&&((now[j]>>i)&1)&&f!=-1) return f&now[j];//找另一个并得答案
      }
      else if(cnt>2)//把与运算后不为1的排除（不可能比为1更优）
          for(int j=1;j<=n;j++) if(!((now[j]>>i)&1)) vis[j]=1;
  }
  int f=-1;
  for(int i=1;i<=n;i++)
      if(!vis[i]&&f==-1) f=now[i];
      else if(!vis[i]&&f!=-1) return f&now[i];//最后跑完，计算答案（都一样了，任选两个即可）
  return 1;//这一行可以不要，只是我开了全警告，不要会报错。。。
  }

• or

  inline void init(int n){//预处理枚举子集，用的老师的方法（时间复杂度好像是O(3^n)，没炸开就奇怪）
  for(int i=1;i<=n;i++)
      for(int j=now[i];j;j=(j-1)&now[i]) f[j]=1;//f标记是否存在
  }
  inline int searchor(int n){
  memset(f,0,sizeof f);//多组数据，不请空就无了
  init(n);
  int ans=0;//答案
  for(int i=1;i<=n;i++){//遍历每个数
      int t=0;//当前找到的最合适的值（与now[i]做或运算后最大且存在）
      for(int j=20;j>=0;j--){
          if((now[i]>>j)&1) continue;//这一位为1，跳过
          else if(f[t|(1<<j)]) t|=(1<<j);//在原基础上，匹配新的最优值，存在则更新
      }
      ans=Max(ans,now[i]|t);//更新答案
  }
  return ans;
  }

然后即可得到正解：（注释就不写了）

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while('0'>ch||'9'<ch){if(ch=='-') f=-f;ch=getchar();}
    while('0'<=ch&&'9'>=ch){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
inline int Max(int x,int y){
    return x>y?x:y;
}
int trie[1600001][2],cnt;
int now[100001];
inline void insert(int n){
    int p=0;
    for(int i=20;i>=0;i--){
        int op=(n>>i)&1;
        if(!trie[p][op]) trie[p][op]=++cnt;
        p=trie[p][op];
    }
}
inline int searchxor(int n){
    int p=0,num=0;
    for(int i=20;i>=0;i--){
        int op=(n>>i)&1;
        if(trie[p][op^1]) p=trie[p][op^1],num=num<<1|1;
        else p=trie[p][op],num<<=1;
    }
    return num;
}
bool vis[100001];
inline int searchand(int n){
    memset(vis,0,sizeof vis);
    for(int i=20;i>=0;i--){
        int cnt=0;
        for(int j=1;j<=n;j++) if(!vis[j]) cnt+=(now[j]>>i)&1;
        if(cnt==2){
            int f=-1;
            for(int j=1;j<=n;j++)
                if(!vis[j]&&((now[j]>>i)&1)&&f==-1) f=now[j];
                else if(!vis[j]&&((now[j]>>i)&1)&&f!=-1) return f&now[j];
        }
        else if(cnt>2)
            for(int j=1;j<=n;j++) if(!((now[j]>>i)&1)) vis[j]=1;
    }
    int f=-1;
    for(int i=1;i<=n;i++)
        if(!vis[i]&&f==-1) f=now[i];
        else if(!vis[i]&&f!=-1) return f&now[i];
    return 1;
}
bool f[10000001];
inline void init(int n){
    for(int i=1;i<=n;i++)
        for(int j=now[i];j;j=(j-1)&now[i]) f[j]=1;
}
inline int searchor(int n){
    memset(f,0,sizeof f);
    init(n);
    int ans=0;
    for(int i=1;i<=n;i++){
        int t=0;
        for(int j=20;j>=0;j--){
            if((now[i]>>j)&1) continue;
            else if(f[t|(1<<j)]) t|=(1<<j);
        }
        ans=Max(ans,now[i]|t);
    }
    return ans;
}
int main(){
    int T=read();
    while(T--){
        memset(trie,0,sizeof trie);
        int n=read(),c=read(),ans=0;
        for(int i=1;i<=n;i++){
            now[i]=read();
            insert(now[i]);
        }
        if(c==1) ans=searchand(n);
        else if(c==2) for(int i=1;i<=n;i++) ans=max(ans,searchxor(now[i]));
        else ans=searchor(n);
        printf("%d\n",ans);
    }
    return 0;
}

这万恶的绝世好题终于完了！！！