题解：P13712 淘汰（Easy ver.）

分析

先不考虑代价，题目就只有两种操作：

把 $x$ 变为 $x\operatorname{AND}a$ 。
把 $x$ 变为 $x\operatorname{OR}b$ 。

容易考虑其性质：操作任意多次和操作一次的效果是一样的！
那么我们就简化了问题，把操作任意多次转化为了每个操作最多进行一次。 接下来就可以分讨了。

码

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	int T;
	cin>>T;
	while(T--){
		int x,y,a,b,c,d,cost=LLONG_MAX;
		cin>>x>>y>>a>>b>>c>>d;
		if(x==y){//不需要操作
			cout<<0<<endl;//这个endl居然硬控我
			continue;
		}
		if((x|b)==y)cost=min(cost,d);//操作2一次
		if((x&a)==y)cost=min(cost,c);//操作1一次
		if(((x&a)|b)==y)cost=min(cost,c+d);//先1后2
		if(((x|b)&a)==y)cost=min(cost,c+d);//先2后1
		cout<<(cost==LLONG_MAX?-1:cost)<<endl;//可能无解
	}
	return 0;
}

补充证明

过程

设

s

是某种可以将

x

变为

y

的包含

\operatorname{AND}

与

\operatorname{OR}

的操作序列。

易得：

(x\operatorname{OR}n)\operatorname{OR}n=x \operatorname{OR}n

(x\operatorname{AND}n)\operatorname{AND}n=x \operatorname{AND}n

使用这两条性质后，我们可以保证

s

中不存在连续的

\operatorname{AND}

与

\operatorname{OR}

操作。

又有如下性质：

[(x\operatorname{AND}a) \operatorname{OR}b]\operatorname{AND}a=(x\operatorname{OR}a) \operatorname{AND}b

[(x\operatorname{OR}a) \operatorname{AND}b]\operatorname{OR}a=(x\operatorname{AND}a) \operatorname{OR}b

（只需要简单的分配律即可证明）

使用这两条性质后，我们可以保证

s

中至多只有一对相邻的

\operatorname{AND}

和

\operatorname{OR}

操作。

所以最终的

s

满足：

x,\ x\operatorname{AND} a,\ x\operatorname{OR} b,\ (x\operatorname{AND} a) \operatorname{OR} b,\ (x\operatorname{OR} b) \operatorname{AND} a \right\}$$

题解：P13712 淘汰（Easy ver.）

文章操作

分析

码

补充证明

相关推荐

评论

题解：P13712 淘汰（Easy ver.）