与 (and)

题目描述

给你一个长度为 \(n\) 的序列 \(A\), 请你求出一对 \(A_i, A_j\) (\(1 \leq i \lt j \leq n\)) 使 \(A_i\) “与”\(A_j\) 最大.

P. S.: “与” 表示位运算 and, 在 C++中表示为&.

输入描述

第一行为 \(n\). 接下来 \(n\) 行, 一行一个数字表示 \(A_i\).

输出描述

输出最大的 \(A_i\) “与”\(A_j\) 的结果.

样例输入

3
8
10
2

样例输出

8

样例解释

8 and 10=8 8 and 2=0 10 and 2=2

数据范围

20% 的数据保证 \(n \leq 5000\) 100% 的数据保证 \(n \leq 3 \cdot 10^5, 0 \leq A_i \leq 10^9\)

Explanation

最开始想了个 Trie 树的做法, 然后就直接滚粗了 (雾)

其实最开始我先到的机房, 然后后来 @xmcp, @MisakiYanayo, @JerrySkywalker 才陆陆续续地到了. 但是他们一看到我在写一个叫 class BinaryTrie 的东西当场就懵了. 然后我一本正经地和他们解释 Trie 树是一个正确的写法.

虽然这也可以是正确的, 但是 Trie 树毕竟还要各种维护, 然后进行了负优化. 这样看来, 本来就是 Trie+暴力的算法何不直接用暴力 (不然还有一个 32 的常数). 结果我们一行人就这样被我坑了 (233).

最后当然是用暴力~

顺便贴一下写错的代码 (雾):


// You can pass A+B problem with Trie.

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 300100, maxm = 11000000;

class BinaryTrie
{
public:
    struct node
    {
        node *ch[2], *par;
        int dat, cnt;
        bool flag;
    }; // Depth should not exceed 2^31 - 1.
    node *root, npool[maxm];
    int ncnt;
    node* make_node(node* par, int dat)
    {
        node *p = &npool[++ncnt];
        p->ch[0] = p->ch[1];
        p->par = par;
        p->cnt = 0;
        p->flag = false;
        p->dat = dat;
        if (p->par)
            p->par->ch[dat] = p;
        return p;
    }
    bool insert(lli dat)
    { // Returns true if insertion figures out the return value...
        int dig = 30;
        node *p = root;
        while (dig >= 0) {
            int dat = (dat >> dig) & 1;
            p->cnt++;
            if (!p->ch[dat])
                p = make_node(p, dat);
            else
                p = p->ch[1];
        }
        p->cnt++;
        if (p->flag)
            return true;
        p->flag = true;
        return false;
    }
    void build_tree(void)
    {
        root = make_node(NULL, 0);
        root->par = NULL;
        return ;
    }
} tree;

int n;

lli work_result(void)
{
    for (int i = 1; i <= n; i++) {
        lli a; scanf("%lld", &a);
        if (tree.insert(a))
            return a;
    }
    // Brute forcing nodes, select them greedily
    BinaryTrie::node *p = tree.root;
    for (int i = 1; i <= 31; i++) {
        if (!p->ch[0]) {
            p = p->ch[1];
            continue;
        } else if (!p->ch[1]) {
            p = p->ch[0];
            continue;
        }
        // Has many children, checking whether to goto #1 or not.
        if (p->ch[1]->cnt >= 2) {
            p = p->ch[1];
            continue;
        }
    }
    return 0;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    tree.build_tree();
    lli res = work_result();
    printf("%lld\n", res);
    return 0;
}

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 300100;

int n;
lli res_bin[32];
lli arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    // Calculating, using greedy
    int top = n;
    for (int i = 31; i >= 0; i--) {
        int cnt = 0;
        for (int j = 1; j <= top; j++)
            if (arr[j] & (1 << i))
                cnt++;
        // Either there be no 1, either there be 1 one, all affecting none
        // of the results
        if (cnt <= 1)
            continue;
        res_bin[i] = 1;
        // Flushing data to grid
        int stk = 0;
        for (int j = 1; j <= top; j++)
            if (arr[j] & (1 << i))
                arr[++stk] = arr[j];
        top = stk;
        continue;
    }
    lli res = 0;
    for (int i = 31; i >= 0; i--)
        res ^= (res_bin[i] << i);
        // cout << res_bin[i] << ' ';
    printf("%lld\n", res);
    return 0;
}