最大值

贪心 Tire

题面

给定$n$个数和$c$，求两数间最大运算值。

• $c=1$：与运算($\&$)
• $c=2$：异或运算($\bigotimes$)
• $c=3$：或运算($|$)

数据范围

• $30pts\ n\leq1000$
• $60pts\ a_i\leq1024$
• $100pts\ n\leq10^5,a_i\leq2^{20}$

解析

$30pts$算法

$O(n^2)$枚举

$60pts$算法

注意到数的个数对答案没有影响。
开个桶存这$1024$个数。
然后$O(1024^2)$枚举。
（注意答案可能为两个相等数的运算值）

与运算

从高位开始枚举，查询该位为$1$的数有$x$个。
如果$x<2$，说明这一位凑不出$1$，答案这一位为$0$。
如果$x=2$，说明这一位只能由两数凑出，答案就是这两数的运算值。
如果$x>2$，说明答案这一位为$1$，同时可以把这一位为$0$的数排除掉，因对答案无贡献。

fp(i,1,n) vis[i]=1;
  fq(i,20,0)
    {
      top=0;
      fp(j,1,n)
    if(vis[j])
    if(a[j]&(1<<i)) sta[++top]=a[j];
      if(top<2) continue;
      if(top==2) {ans=sta[1]&sta[2];return;}
      if(top>2) ans|=(1<<i);
      fp(j,1,n)
    if(!(a[j]&(1<<i))) vis[j]=0;
    }

异或运算

对于一个数，我们很清楚使运算值最大的另一数是多少。
于是从高位往低位构建一棵$Tire$树（二叉树）。
显然无脑尽量走更优边。

il void Build(re int x,re int d,re int num)
{
  if(d<0) return;
  if(num&(1<<d))
    {
      if(!t[x][1]) t[x][1]=++tot;
      Build(t[x][1],d-1,num);
    }
    else
      {
    if(!t[x][0]) t[x][0]=++tot;
        Build(t[x][0],d-1,num);
      }
}
il int dfs(re int x,re int now,re int d)
{
  if(d<0) return 0;
  if(now&(1<<d))
    {
      if(t[x][0]) return (1<<d)|dfs(t[x][0],now,d-1);
      if(t[x][1]) return dfs(t[x][1],now,d-1);
    }
  else
    {
      if(t[x][1]) return (1<<d)|dfs(t[x][1],now,d-1);
      if(t[x][0]) return dfs(t[x][0],now,d-1);
    }
  return 0;
}
il void work2()
{
  fp(i,1,n) Build(0,20,a[i]);
  fp(i,1,n) ans=max(ans,dfs(0,a[i],20));
}

或运算

首先标记每个数本身和真子集（即本身改几个$1$为$0$后所形成的数），代表这些数能对结果提供的有效（即另一数对应位为$0$，而不是$1$）影响。
具体方法是先标记本身。
然后枚举数位，从大到小枚举数，把该位为$1$的数的这一位改为$0$后形成的数赋标记。

接下来，对每个数从高位往低位枚举，并设一补集$E$。
如果第$i+1$位为$0$，且$E|(1<<i)$这一数可被提供出来，则$E|=(1<<i)$。
其实也是贪心。

memset(tong,0,sizeof(tong)); 
  fp(i,1,n) tong[a[i]]=1;
  fp(i,0,20)
    fq(j,1<<20,0)
    if(j&(1<<i)) tong[j^(1<<i)]|=tong[j];
  fp(j,1,n)
    {
      re int E=0;
    fq(i,20,0)
    if(!(a[j]&(1<<i))&&tong[E|(1<<i)]) E|=(1<<i);    
      ans=max(ans,E|a[j]);
    }

$100pts$算法

以上三算法复杂度均为$O(20n)$。
于是一道模板题就被$AC$了。
然而我在考场上犯了好多逗逼错误