1 条题解

  • 0
    @ 2023-3-14 13:35:07
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXNODE = 100000 * 31; // 单词数*单词长度(最坏情况下节点数量)
    int tot, root, son[MAXNODE + 5][2];
    int tag[MAXNODE + 5]; // 存在几个单词
    void clearNode(int nId)
    {
        for (int i = 0; i < 2; i++)
            son[nId][i] = 0;
        tag[nId] = 0;
    }
    void ins(int s)
    {
        int now = root;
        for (int i = 30; i >= 0; i--)
        {
            // s的2^i位是多少
            int j = ((s >> i) & 1);
            if (!son[now][j])
            {
                son[now][j] = ++tot;
                clearNode(tot);
            }
            now = son[now][j];
        }
    }
    int check(int s)
    {
        int res = 0;
        int now = root;
        for (int i = 30; i >= 0; i--)
        {
            int j = ((s >> i) & 1);
            // 尽可能走不同的
            if (son[now][1 - j])
            {
                res += (1 << i);
                now = son[now][1 - j];
            }
            else
            {
                now = son[now][j];
            }
        }
        return res;
    }
    int n, x;
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        cin >> x;
        tot = root = 1;
        clearNode(tot);
        ins(x);
        int ans = 0;
        for (int i = 2; i <= n; i++)
        {
            cin >> x;
            ans = max(ans, check(x));
            ins(x);
        }
        cout << ans << "\n";
        return 0;
    }
    
    • 1

    信息

    ID
    692
    时间
    1000ms
    内存
    512MiB
    难度
    3
    标签
    递交数
    28
    已通过
    19
    上传者