题解：P13712 淘汰（Easy ver.）

· · 题解

分析

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

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

码

:::info[代码]{open}

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

::::

补充证明

::::info[过程] 设 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\}

::::