东云侑子

感觉最直观最显然的做法，不知道为什么没有人提。

考虑手玩一下样例，一个二的次幂减掉数

x

，我们反过来考虑

x

加上什么数会变成

2

的次幂。

容易发现其实是这样，首先 lowbit 不变，比 lowbit 低的位也都不变，因为需要进位。

然后到你打算变成的二的次幂的前一位打止，所有位都取反。

然后考虑我们知道这个变化规则之后怎么来做这个题。

lowbit 不同

显然我们只能先消成 0，再合并回我要变成的数，那么也就是两个数变成 0 的次数加和。

lowbit 相同

考虑我们可以通过消除其中一些前缀连续段使得后缀连续段相同。

所以有一个自然而然的想法就是把 lowbit 扔掉之后建立反向 01trie 然后直接搜，然后他是假的。

然后你考虑为什么，其实是因为我只关心连续段而并不关系其具体数值，所以我们考虑对其二进制位做异或差分，然后再建立反向 01trie，此时即可直接搜索计算答案。

时间复杂度

O(n\log V)

。

可能稍微有一点点细节和边界判断。

CPP

#include<bits/stdc++.h>
using namespace std;
int n;
int A[200005];
int lowbit(int x){return x&-x;}
int get0(int x){
   if(!x)return 0;
   int tmp=1;
   while(!(x&1))x>>=1;
   x>>=1;
   while(x){
      tmp++;
      if(x&1){
         while(x&1)x>>=1;
      }
      else{
         while(!(x&1))x>>=1;
      }
   }
   return tmp;
}
int calc(int x,int y){
   if(lowbit(x) xor lowbit(y)){
      return get0(x)+get0(y);
   }
   bool flg=false;
   int num=0;
   for(int i=__lg(lowbit(x))+1;i<=30;i++){
      if((((x>>i)&1)xor((x>>(i+1))&1))xor(((y>>i)&1)xor((y>>(i+1))&1))){
         flg=true;
      }
      if(flg){
         num+=((((x>>i)&1)xor((x>>(i+1))&1)));
         num+=((((y>>i)&1)xor((y>>(i+1))&1)));
      }
   }
   return num;
}
pair<int,int> tmp;
vector<int> id[100];
struct node{
   int x,y,z;
   bool friend operator < (const node &a,const node &b){
      return a.z<b.z;
   }
};
class trie01{
   public:
   int ch[200005<<5][2];
   int Max[200005<<5];
   int Maxid[200005<<5];
   int tot;
   void clear(){
      for(int i=0;i<=tot;i++){
         ch[i][0]=ch[i][1]=Max[i]=0;
      }
      tot=0;
      return;
   }
   void insert(int id,int x,int j){
      int now=0;
      for(int k=j+1;k<=30;k++){
         int nxt=((((x>>k)&1)xor((x>>(k+1))&1)));
         if(!ch[now][nxt])ch[now][nxt]=++tot;
         now=ch[now][nxt];
      }
      Maxid[now]=id;
      return;
   }
   void getMax(int cur){
      if(ch[cur][0]){
         getMax(ch[cur][0]);
         if(Max[ch[cur][0]]>=Max[cur]){
            Maxid[cur]=Maxid[ch[cur][0]];
            Max[cur]=Max[ch[cur][0]];
         }
      }
      if(ch[cur][1]){
         getMax(ch[cur][1]);
         if(Max[ch[cur][1]]+1>=Max[cur]){
            Maxid[cur]=Maxid[ch[cur][1]];
            Max[cur]=Max[ch[cur][1]]+1;
         }
      }
      return;
   }
   node getans(int cur){
      node ans={0,0,0};
      if(ch[cur][0])ans=max(getans(ch[cur][0]),ans);
      if(ch[cur][1])ans=max(getans(ch[cur][1]),ans);
      if(ch[cur][0]&&ch[cur][1])ans=max(ans,node{Maxid[ch[cur][0]],Maxid[ch[cur][1]],Max[ch[cur][0]]+Max[ch[cur][1]]+1});
      return ans;
   }
}T;
node ans;
int pmax;
void solve(int j){
   T.clear();
   for(int i=0;i<id[j].size();i++){
      int tmp=A[id[j][i]];
      T.insert(id[j][i],tmp,j);
   }
   T.getMax(0);
   node tmp=T.getans(0);
   ans=max(ans,tmp);
   if(pmax){
      for(int i=0;i<id[j].size();i++){
         int tmp=A[id[j][i]];
         ans=max(ans,node{id[j][i],pmax,get0(tmp)+get0(A[pmax])});
      }
   }
   for(int i=0;i<id[j].size();i++){
      int tmp=A[id[j][i]];
      if(get0(tmp)>get0(A[pmax]))pmax=id[j][i];
   }
   return;
}
int main(){
   scanf("%d",&n);
   for(int i=1;i<=n;i++){
      scanf("%d",&A[i]);
   }
   for(int i=1;i<=n;i++){
      if(!A[i]){
         pmax=i;
         continue;
      }
      id[__lg(lowbit(A[i]))].push_back(i);
   }
   for(int j=0;j<=30;j++){
      solve(j);
   }
   printf("%d %d %d\n",ans.x,ans.y,ans.z);
   return 0;
}

文章操作

相关推荐

评论

东云侑子