P14178 Jueves题解

HNO_3 · 2025-10-07 21:34:18 · 题解

P14178 Jueves题解

- 前置知识

1. a \lor b$;
3. ### - **公式推导**

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);

- 结论

即a\oplus b+a \lor b+a \land b=2 \times(a \lor b)=2 \times a \mid 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;
  }

  QwQ