求问:为什么贪心不行
查看原帖
求问:为什么贪心不行
531650
emmc楼主2025/1/20 09:33

楼主尝试了一下贪心解法,从高位到低位,能异就异, 理论上应该没有问题?感谢各位巨佬!

#include <bits/stdc++.h>
using namespace std;
const int N = 3 * 1e6 + 100;
int n, q, T;
int pp = 0;
int tp[N];
int ls[N];
char s[N];
int t[N][4];
void build(int len) {
    int p = 0;

    for (int i = 1; i <= len; i++) {
        if (!t[p][tp[i]]) {
            t[p][tp[i]] = ++pp;
            p = pp;
        } else
            p = t[p][tp[i]];
    }
}
int solve(int p1, int p2, int i) {
    int len = 32;

    if (i == 33)
        return 0;

    if (t[p1][0] && t[p1][1]) {
        if (t[p2][0] && t[p2][1]) {
            int ret1 = solve(t[p1][1], t[p2][0], i + 1);
            int ret2 = solve(t[p1][0], t[p2][1], i + 1);
            return max(ret1, ret2) + (1 << (len - i));
        } else if (t[p2][0] || t[p2][1]) {
            return solve(t[p1][!(t[p2][0] == 0)], t[p2][(t[p2][0] == 0)], i + 1) + (1 << (len - i));
        }
    } else if (t[p1][0] || t[p1][1]) {
        if (t[p2][0] && t[p2][1]) {
            p1 = t[p1][(t[p1][0] == 0)];
            p2 = t[p2][!(t[p1][0] == 0)];
            return solve(p1, p2, i + 1) + (1 << (len - i));
        } else if (t[p2][0] || t[p2][1]) {
            int ret = 0;

            if (!((t[p1][0] == 0) == (t[p2][0] == 0))) {
                ret += (1 << (len - i));
            }

            p1 = t[p1][(t[p1][0] == 0)];
            p2 = t[p2][(t[p2][0] == 0)];
            ret += solve(p1, p2, i + 1);
            return ret;
        }
    }
}
int main() {
    for (int i = 0; i <= pp; i++)
        for (int j = 0; j <= 12; j++)
            t[i][j] = 0;

    pp = 0;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int num = 0;
        cin >> num;

        for (int j = 32; j >= 0; j--) {
            tp[j] = (num & 1);
            num >>= 1;
        }

        build(32);
    }

    cout << solve(0, 0, 1) << endl;

}
2025/1/20 09:33
加载中...