F.Lisa and the Martians

题意

求给定的公式的最大值。

思路

观察给定的公式，想想每一位，很容易就发现规律了。

可以转化成数组中，求两个数的同或最大值。于是可以无脑字典树。

更简单的做法是：

排序，直接比对相邻的数，这样也能得到最大的同或的对。

int a[N];
int trie[N * 30 + 2][2];
int sum = 1;
int k;
void insert(int x)
{
    int p = 1;
    for (int i = k - 1; i >= 0; i--) {
        int ch = x >> i & 1;
        if (trie[p][ch] == 0) trie[p][ch] = ++sum;
        p = trie[p][ch];
    }
}
pair<int, int> search(int x)
{
    int ans = 0;
    int p = 1;
    int y = 0;
    for (int i = k - 1; i >= 0; i--) {
        int ch = x >> i & 1;
        int f = ch ^ 1;
        if (trie[p][ch]) {
            ans |= (1ll << i);
            y |= (1ll << i) * ch;
            p = trie[p][ch];
        }
        else if (trie[p][f]) {
            y |= (1ll << i) * f;
            p = trie[p][f];
        }
        else break;
    }
    return {ans, y};
}
void solve()
{
    int n;
    cin >> n >> k;
    int x = 1, y = 2;
    int ma = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i == 1) {
        insert(a[i]);
            continue;
        }
        auto ret = search(a[i]);
        if (ret.first > ma) {
            x = a[i];
            y = ret.second;
            ma = ret.first;
        }
        insert(a[i]);
    }
    int X = 0;
    for (int i = k - 1; i >= 0; i--) {
        if ((x >> i & 1) == (y >> i & 1)) {
            X |= (1ll << i) * ((x >> i & 1) ^ 1);
        }
    }
    int I = -1, J = -1;
    for (int i = 1; i <= n; i++) {
        if (a[i] == x) {
            if (I == -1) {
                I = i;
                continue;
            }
        }
        if (a[i] == y) {
            if (J == -1) {
                J = i;
            }
        }
    }

    // cout << "ma = " << ma << '\n';
    // cout << x << " " << y << "\n";
    if (ma) cout << I << " " << J << " " << X << "\n";
    else cout << "1 2 0\n";
    for (int i = 1; i <= sum + 5; i++) {
        trie[i][0] = trie[i][1] = 0;
    }
    sum = 1;
}

G. Vlad and the Mountains

题意

给定一张图，并不一定联通。图是无向图，且有点权。对于图的边权，是这样定义的：

$x$ 到 $y$ 的花费是 $x$ 的点权减去 $y$ 的点权。边权可以为负数。

$q$ 次询问，初始体力是 $e$，起点 $x$ 能否走到 $y$。

做法

应该是很经典的套路了吧。

让边权为 $max(a[x], a[y])$，然后按照边权排序。

之后对询问以关键字 $a[x] + e$进行排序，此时遍历上面排序的边，进行并查集。最后只要 $x,y$ 在一个联通块内，那么答案就是 $YES$

int a[N];
struct node {
    int x, y, val;
    bool operator < (const node &k) const {
        return val < k.val;
    }
}b[N];
struct Que {
    int x, y, val;
    int pos;
    bool operator < (const Que &k) const {
        return val < k.val;
    }
}que[N];
bool ok[N];
int fa[N];
int getf(int x) {
    if (x == fa[x]) return x;
    return fa[x] = getf(fa[x]);
}
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        int x, y, val;
        cin >> x >> y;
        val = max(a[x], a[y]);
        b[i] = {x, y, val};
    }
    sort(b + 1, b + 1 + m);
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int x, y, val;
        cin >> x >> y >> val;
        que[i] = {x, y, val + a[x], i};
    }
    sort(que + 1, que + 1 + q);
    int r = 1;
    for (int i = 1; i <= q; i++) {
        while(r <= m && b[r].val <= que[i].val) {
            int fx = getf(b[r].x), fy = getf(b[r].y);
            r++;
            if (fx == fy) continue;
            fa[fx] = fy;
        }
        ok[que[i].pos] = (getf(que[i].x) == getf(que[i].y));
    }
    for (int i = 1; i <= q; i++) {
        if (ok[i]) cout << "YES\n";
        else cout << "NO\n";
    }
}