Chef and Bitwise Product 贪心+位运算

(Updated: )
(4 mins to read)

给两个数x,y($x, y <= 10^{12}$),要求找到一个数z,最大化(x&z)*(y&z)同时最小化z,且$L\leq z\leq R$,L和R由题目给出($L, R \leq 10^{12}$)

做法

先不考虑上下界限制,那么z全取1肯定最优,再加入上界限制,然而并不是取R最优,比如x = 7, y = 12, l = 0, r = 8, 此时z=7可以想到一种贪心的做法,让R的某一位1变成0,然后让R的低位全变1,然后交一发会发现0分其实这个时候已经可以最大化(x&z)*(y&z),下面要最小化z,可以发现如果x和y的某一位同时为0,此时z的该位为1也没用.所以只要在保证>=下界的情况下通过该条件最小化z即可.另外好像要特判一下下界为最优解的情况.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 15;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
void solve()
{
  ll x, y, l, r;
  scanf("%lld%lld%lld%lld", &x, &y, &l, &r);
  ll ans = (x&r)*(y&r), z = r;
  for(int i=40; i>=0; i--)
  {
    int b = (r>>i)&1;
    if(b)
    {
      ll c = (r>>(i+1)<<(i+1)) + (1ll<<i) - 1;
      for(int i=40; i>=0; i--)
      {
        int aa = (x>>i)&1, bb = (y>>i)&1, cc = (c>>i)&1;
        if(!aa && !bb && cc)
          if((c^(1ll<<i))>=l) c ^= (1ll<<i);
      }
      if(c<l) continue;
      if((x&c)*(y&c)>ans || (((x&c)*(y&c))==ans&&c<z)) ans = (x&c)*(y&c), z = c;
    }
  }
  if(!ans) z = l;
  printf("%lld\n", z);
}
int main()
{
  int T; scanf("%d", &T);
  while(T--) solve();
  return 0;
}