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

思路

首先特判

a=b

的情况，则此时

a

至少要操作一次才能得到

b

。

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

对于所有 $1\le i\le n$ 有 $a_i\ \&\ b_i=b_i$ 。
存在一个排列 $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

级别的，可以通过。

代码

CPP

#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;
}

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

文章操作

思路

代码

相关推荐

评论

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