题解：Maximum AND

naughty-naught / 2024-11-20 / 原文

Problem Link

Maximum AND

题外话

用 sort 肘过去了？

题面翻译

给定数组 $a$ 和 $b$，重排 $b$ 数组，求 $a_i \oplus b_i$ 之后与和的最大值。

Solution

不难想到按位贪心。从最高位开始，逐位讨论是否能为 $1$。

接下来有一个做法：

先将 $a$ 数组升序排序， $b$ 数组降序排序。为什么这么排？因为这样最高位越容易异或成 $1$。

接下来按位计算，如果可以使该位值为 $1$，那么就让答案加上该位，反之，跳过该位，除去该位影响后再排序，具体怎么做到？很简单，所有 $a_i$ 和 $b_i$ 都把这位变为 $1$ 或 $0$ 即可。

Code

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string.h>
#include <cstring>
using namespace std;

typedef long long ll;
#define Maxn 100005
#define Maxlen 30
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define fr(i, r, l) for (int i = l; i >= r; --i)
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}

int n, a[Maxn], b[Maxn], ans;

bool smaller(int a, int b) { return a < b; }

bool bigger(int a, int b) { return a > b; }

int main()
{
    int _ = read();
    while(_--)
    {
        n = read(); ans = 0;
        fo(i, 1, n) a[i] = read();
        fo(i, 1, n) b[i] = read();
        sort(a + 1, a + n + 1, smaller),
        sort(b + 1, b + n + 1, bigger);
        fr(pos, 0, Maxlen) { // 从高到低位考虑。
            bool could_be_one = true; int pos_num = (1 << pos);
            fo(i, 1, n) if( (a[i] & pos_num) == (b[i] & pos_num) ) { could_be_one = false; break; }
            if( could_be_one ) ans |= pos_num; // 可以，则加上该位
            else // 不可以
            {
                fo(i, 1, n) a[i] |= pos_num, b[i] |= pos_num; // 把所有数的该位都变为 1 。
                sort(a + 1, a + n + 1, smaller), 
                sort(b + 1, b + n + 1, bigger); // 重新排序。
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}