题解：CF2077F AND x OR

NyaingCBC · 2026-05-20 20:50:24 · 题解

思路分析

这道题要求 a 内部通过位运算得到 b，于是显然我们也只能从判定入手：什么样的 a,b 是满足要求的？

一个显然可行的方式是 a=b，但是还有没有别的呢？我们需要思考 a 内部的变化的本质特征：

如果想要选择一个 a_i 保持不变，那么我们选择一个 a_i 的超集，并将这个集合或到 a_j 上；或者选择 a_i 的子集，并将这个集合与到 a_j 上。

不难证明：如果同时使得 a_i,a_j 变化的话，那么可以只使用上述两种操作凑出来。

关注第二种操作，他告诉我们我可以将任意一个数变成 0，关注第一种操作，他告诉我们我可以将任意一个数变成另一个数的超集。

也就是说，如果在 b 中存在子集关系，那么就有解。具体来说，我们将超集元素设置为 0，利用 0 将其他元素先变成 0，再变成目标。最后我们利用子集元素将超集还原到想要的状态。

容易注意到变成 0 的操作空间显然是严格强于另外的任何数的，因此，这种构造在 a\neq b 的条件下是充要的。

于是此题就变成了使 b 中的某个元素变成另外某个元素的子集或者超集的最小代价。

这个代价怎么算呢？我们可以先将一个元素增大，得到某一个元素增大到某一个位置的最小代价，然后将这个代价向子集与超集分别扩张，就求完了。

此题可解，时间复杂度是单个 \log，代码如下：

#include<bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
//#define int long long
constexpr bool online=0;
#define _rw_file ""
#define sipt //signed-input
#define sopt //signed-output
struct IO {
#define mxsz (1 << 21)
    char buf[mxsz], * p1, * p2;
    char pbuf[mxsz], * pp; bool acc[128];
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
    inline char gc() {
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, mxsz, stdin);
        return p1 == p2 ? ' ' : *p1++;
    }
    inline void setacc(const char* c) { while (*c) acc[*c++] = 1; }
    inline char getc() { char c; while (!acc[c = gc()]); return c; }
#ifndef sipt
    inline int read() {
        int r = 0; char c = gc(); while (c < '0' || c>'9') c = gc();
        while (c >= '0' && c <= '9') r = r * 10 + (c ^ 48), c = gc();
        return r;
    }
#else
    inline int read() {
        int r = 0; char c = gc(); bool rev = 0;
        while (c < '0' || c>'9') rev |= (c == '-'), c = gc();
        while (c >= '0' && c <= '9') r = r * 10 + (c ^ 48), c = gc();
        return rev ? ~r + 1 : r;
    }
#endif
    inline void push(const char& c) {
        if (pp - pbuf == mxsz) fwrite(pbuf, 1, mxsz, stdout), pp = pbuf;
        *pp++ = c;
    }
    inline void write(int x) {
        static char sta[22]; int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) push(sta[--top] ^ 48);
    }
    inline void write(int x, char opc) {
#ifdef sopt
        if (x < 0) push('-'), x = ~x + 1;
#endif
        write(x), push(opc);
    }
    inline void puts(const char* c) { while (*c) push(*c++); }
} io;
int t,n,m,a[1ll<<22|2],b[1ll<<22|2],ans,tt;
struct minval{
    int v1,p1,v2,p2;
    inline void emplace(int p,int v){
        if(!p) return;
        if(p1==p){
            if(v<v1) v1=v;
            return;
        }
        if(v<=v1) v2=v1,p2=p1,v1=v,p1=p;
        else if(v<v2) v2=v,p2=p;
    }
}v[1ll<<22|2],v2[1ll<<22|2],v3[1ll<<22|2];
signed main(){
    if(online)
        freopen(_rw_file ".in","r",stdin),
        freopen(_rw_file ".out","w",stdout);
    ios::sync_with_stdio(0);
    /*
    @2030
    首先，较为套路的，我们先考虑怎么检验 a,b 是合法的？
    我们可以将一个 a 置为 0，后续再去恢复他。
    恢复方式：找到一个目标值的子集目标值，然后就可以恢复了。
    也就是说，基本上，如果在 b 中存在子集关系，那么就是可行的。
    不过显然这并不是充要的。比如说二者直接相等了。
    @2051 give up
  <- 不是哪个神人想到的？这东西能是对的？？？
    */
    for(tt=t=io.read();t;t--){
        n=io.read(); m=io.read(); ans=0;
        for(int i=1;i<=n;++i) a[i]=io.read();
        for(int i=1;i<=n;++i) b[i]=io.read();
        m=pow(2,1+ceil(log2(m)));
        for(int i=0;i!=m;++i)
            v[i].v1=v[i].v2=1e9,v[i].p1=v[i].p2=0;
        for(int i=1;i<=n&&ans<=m;++i) ans+=abs(a[i]-b[i]);
        for(int i=1;i<=n;++i) v[b[i]].emplace(i,0);
        for(int i=1;i!=m;++i)
            v[i].emplace(v[i-1].p1,v[i-1].v1+1),
            v[i].emplace(v[i-1].p2,v[i-1].v2+1);
        // for(int i=0;i!=m;++i){
        //  cerr<<i<<":";
        //  if(v[i].p1) cerr<<v[i].p1<<" "<<v[i].v1<<"  ";
        //  if(v[i].p2) cerr<<v[i].p2<<" "<<v[i].v2<<"  ";
        //  cerr<<endl;
        // }
        memcpy(v2,v,sizeof(minval)*m);
        memcpy(v3,v,sizeof(minval)*m);
        for(int d=21;d>=0;d--)
            for(int i=0;i!=m;++i)
                if(!(i>>d&1))
                    v2[i|(1ll<<d)].emplace(v2[i].p1,v2[i].v1),
                    v2[i|(1ll<<d)].emplace(v2[i].p2,v2[i].v2);
        // for(int i=0;i!=m;++i){
        //  cerr<<i<<":";
        //  if(v2[i].p1) cerr<<v2[i].p1<<" "<<v2[i].v1<<"  ";
        //  if(v2[i].p2) cerr<<v2[i].p2<<" "<<v2[i].v2<<"  ";
        //  cerr<<endl;
        // }
        for(int d=21;d>=0;d--)
            for(int i=0;i!=m;++i)
                if(i>>d&1)
                    v3[i^(1ll<<d)].emplace(v3[i].p1,v3[i].v1),
                    v3[i^(1ll<<d)].emplace(v3[i].p2,v3[i].v2);
        // for(int i=0;i!=m;++i){
        //  cerr<<i<<":";
        //  if(v3[i].p1) cerr<<v3[i].p1<<" "<<v3[i].v1<<"  ";
        //  if(v3[i].p2) cerr<<v3[i].p2<<" "<<v3[i].v2<<"  ";
        //  cerr<<endl;
        // }
        for(int i=1;i<=n;++i){
            if(v2[b[i]].p1!=i) ans=min(ans,v2[b[i]].v1); 
            if(v2[b[i]].p2!=i) ans=min(ans,v2[b[i]].v2); 
        }
        for(int i=1;i<=n;++i){
            if(v3[b[i]].p1!=i) ans=min(ans,v3[b[i]].v1); 
            if(v3[b[i]].p2!=i) ans=min(ans,v3[b[i]].v2); 
        }
        io.write(ans,'\n');
    }
}