题目传送门

先说一下题意吧：有

T

组数据，每组数据包含

x,y,a,b,c,d

六个数，我们可以给

x

进行无数次操作：令

x\leftarrow x \operatorname{AND} a

或者令

x\leftarrow x \operatorname{OR} b

的操作，第一种操作所需要的代价为

c

，第二种操作所需要的代价为

b

，你需要求出将

x

变为

y

的最小代价，如果做不到，输出

-1

。

就是这样。

思路

这道题可以有多种情况，我们可以进行分类讨论：

$x\operatorname{AND} a=y$ ，如果是这样，那么一次操作一即可完成，代价为 $c$ 。
$x\operatorname{OR} b=y$ ，如果是这样，那么一次操作二可完成，代价为 $d$ 。
$x\operatorname{AND} a\operatorname{OR} b=y$ ，这种也是极为简单的，代价为 $c+d$ 。
$x\operatorname{OR} b\operatorname{AND} a=y$ ，这种情况同上，代价为 $c+d$ 。

有的童鞋可能会问了，有可能使

x

变为

y

需要多次运算，那该怎么办。

咳咳，这种情况是可以的，但是这样肯定不会使代价小于前面说的四种操作。

不妨用 1 15 2 14 3 5 模拟一下。

这道题考验的是二进制，所以先把

x,y,a,b

转化为二进制计算。

x

用二进制表示是

001

;

y

用二进制表示是

111

；

a

用二进制表示是

010

；

b

用二进制表示是

101

。

用

x\operatorname{AND} a

的操作，使得

x

变为二进制下的

000

，如果再使用一次，结果依旧是

000

。

用

x\operatorname{OR} b

的操作，使得

x

变为二进制下的

101

，如果再使用一次，结果依旧是

101

。

很明显，连续多次的同一个操作，答案都会相等，所以不会有同一操作连续两次进行的情况。

童鞋：那如果不连续呢？

不连续的情况会有两种:

操作一后操作二再是操作一，事实上这个做出来的答案等于操作二再操作一。
操作二后操作一再是操作二，这个做出来的答案等于操作一再操作二。

可以发现能出现的情况只有四种能得到代价最小值。

注意还要特判

x=y

，这种情况不需要任何操作，直接输

0

即可。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int n;//10 的 5 次方不用 long long。
int x,y,a,b;//2 的 30 次方。
long long minn;//记录代价最小值，最大可以是两个二的 30 次方的和，不开 long long 见祖宗。
long long c,d;//需要和 minn 比较，所以也要开 long long。

int main(){
	cin>>n;
	while(n--){
		minn=1000000005;//比较大的值，用来存最小代价。
		cin>>x>>y>>a>>b>>c>>d;
        if(x==y){//特判。
            cout<<0<<endl;
            continue;
        }
		if(((x&a)|b)==y||((x|b)&a)==y){//注意要用括号括起来，不然会出问题。
			minn=c+d;
		}
		if((x&a)==y){
			minn=min(minn,c);
		}
		if((x|b)==y){
			minn=min(minn,d);
		}
        if(minn==1000000005){//如果无解输出 -1。
            cout<<-1<<endl;
            continue;
        }
		cout<<minn<<endl;
	}	
	return 0;
}

请勿抄袭题解。这会失去学术诚信，同时浪费洛谷评测资源。如果被发现抄题解，可能会被处以棕名惩罚或者被封号。——摘自《洛谷新用户必读》

题解：P13712

文章操作

思路

AC CODE

相关推荐

评论

题解：P13712