P14178 Jueves题解

- 前置知识

1. $a \operatorname{and} b= a \lor b$;
2. $a \operatorname{or} b=a \land b$;
3. $a \operatorname{xor} b=a\oplus b=a \lor b - a \land b$;

- 公式推导

$a \operatorname{and} b+a \operatorname{or} b+a \operatorname{xor} b$=

$a \lor b+a \land b+a \lor b - a \land b$=

$2\times (a \lor b)$;

- 结论

• 注意！！！题目中的$0\le a_i\le 10^{18}$,且对于任意的$a_u,a_v$,都有$a\oplus b+a \lor b+a \land b=2 \times(a \lor b)=2 \times a \mid b \ge 0$, 所以$s$到$t$最小贡献就是$2\times(a[u]+a[t])$ ( 若$s=t$,则贡献为0 ).
• 代码如下

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
ll T,n,s,t,i,j;
ll a[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>T;
	while(T--)
	{
		cin>>n>>s>>t;
		for(i=1;i<=n;i++) cin>>a[i];
		if(s==t){
			cout<<0<<'\n';continue;
		}
		cout<<2*(a[s]|a[t])<<'\n';
	}
	return 0;
}