题解：P14457 [ICPC 2025 Xi'an R] Killing Bits

· · 题解

思路

首先特判 a=b 的情况，则此时 a 至少要操作一次才能得到 b。

通过惊人注意力可以得出该问题的充要条件即为：

  1. 对于所有 1\le i\le n 有 a_i\ \&\ b_i=b_i。

  2. 存在一个排列 p 对于所有 1\le i\le n 有 p_i\ \&\ b_i=b_i。

先证必要性：

当存在 i 有 a_i\ \&\ b_i\neq b_i 时，也就意味着 a_i 的某一位为 0 但是 b_i 该位为 1，由于与运算的特殊性，该位无论如何操作都不可能再变成 1 了，所以此时 a 无论如何都不能变成 b。

当不存在排列 p 满足条件时，对于所有排列 p 都存在一个 i 有 p_i\ \&\ b_i\neq b_i。于是 a 选择任意一个排列 p 操作后都会存在 i 有 a_i 的某一位为 0 但是 b_i 该位为 1，同样不能变成 b。

再证充分性：

此时我们已经得到了满足条件的排列 p。由于 p_i\ \&\ b_i=b_i，所以一定有 b_i\le p_i，也就是说 b_i 一定在排列 p 中出现过。

对于某个 a_i\neq b_i 的位置 i，我们找到原排列中 b_i 的出现位置 j 使得 p_j=b_i，然后交换 p_i 和 p_j 得到排列 p'，选择 p' 对 a 进行操作得到 a'。容易发现 a'_i=b_i，且 a' 仍然满足合法的充要条件。于是我们对所有位置都进行该操作，便可以将 a 转换为 b。

问题变成了如何求出合法的排列 p。对于一个数 x，它可以填入所有满足 x\ \&\ b_i=b_i 的 p_i 上，这启发我们建图跑二分图匹配，当匹配为完美匹配时，存在一个合法的 p。

直接建图匹配边数是 n^2 级别的，时间复杂复杂度较大，需要优化建图。

由于 b_i 是 x 的子集，所以我们可以将每个数向它的二进制中去掉一位 1 的数连边，将源点连向 x，b_i 连向汇点跑网络流即可。此时的边数是 n\log n 级别的，可以通过。

代码

#include <bits/stdc++.h>
using namespace std;
namespace mf{
    const int N=50005,INF=0x3f3f3f3f;
    struct node{
        int x,w,rev;
    };
    vector<node> t[N];
    int dep[N],gap[N],maxflow;
    int n,S,T;
    void init(int nn){
        for(int i=1;i<=nn+2;i++)
            t[i].clear();
        n=nn+2,S=nn+1,T=nn+2;
    }
    void add(int x,int y,int w){
        t[x].push_back({y,w,t[y].size()});
        t[y].push_back({x,0,t[x].size()-1});
    }
    void bfs(){
        for(int i=0;i<=n;i++)
            gap[i]=0,dep[i]=-1;
        queue<int> q;
        q.push(T),dep[T]=0,gap[dep[T]]++;
        while(!q.empty()){
            int u=q.front();q.pop();
            for(node v:t[u])
                if(!~dep[v.x])
                    dep[v.x]=dep[u]+1,gap[dep[v.x]]++,q.push(v.x);
        }
    }
    int dfs(int x,int flow){
        if(x==T) return maxflow+=flow,flow;
        int used=0;
        for(auto&[v,w,rev]:t[x]){
            if(w&&dep[v]+1==dep[x]){
                int mn=dfs(v,min(w,flow-used));
                if(mn) w-=mn,t[v][rev].w+=mn,used+=mn;
                if(flow==used) return used;
            }
        }
        gap[dep[x]]--;
        if(!gap[dep[x]]) dep[S]=n+1;
        dep[x]++,gap[dep[x]]++;
        return used;
    }
    int isap(){
        maxflow=0;
        bfs();
        if(dep[S]==-1) return 0;
        while(dep[S]<n) dfs(S,INF);
        return maxflow;
    }
}
int T,n,a[50005],b[50005];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            cin>>b[i];
        bool flag=0,flag2=0;
        for(int i=1;i<=n;i++)
            if(a[i]!=b[i]) flag2=1;
        for(int i=1;i<=n;i++)
            if((a[i]&b[i])!=b[i]){
                flag=1;
                break;
            }
        if(!flag2) cout<<"Yes"<<endl;
        else if(flag) cout<<"No"<<endl;
        else{
            mf::init(n);
            for(int i=1;i<=n;i++)
                mf::add(mf::S,i,1);
            for(int i=1;i<=n;i++)
                mf::add(b[i]+1,mf::T,1);
            for(int i=0;i<n;i++)
                for(int j=0;(1<<j)<=i;j++)
                    if(i&(1<<j)) mf::add(i+1,(i^(1<<j))+1,mf::INF);
            if(mf::isap()==n) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}