[图论记录]CF1849F XOR Partition

rlc202204 · 2023-07-30 17:07:17 · 个人记录

题意：

思路：

idea from 洛谷题解

那篇题解好像是受到了某个 LGM 大佬的评论的启发。

我们要求的是某个最小值的最大值，这让我们联想到二分。

现在我们就要判断是否能有一种划分使得价值 \ge x。

那对于确定的 x，我们可以将所有 a_i \oplus a_j < x 的 i 和 j 之间连一条边，然后判断这张图是否是一张二分图，如果是就可以，不是就不行。

但是这样建图的时间复杂度是 O(n^2) 的，所以我们还需要更进一步优化。

首先，异或运算有一个性质。

性质： 若 a < b < c，则 a \oplus c > \min\{a \oplus b,b \oplus c\}。

证明：

考虑 a,b,c 从高到低第一个不同的位是第 x 位。会有两种情况：

两种情况都成立，故结论正确。

这个性质相当于告诉我们：一组数中两两异或的最小值，相当于把这组书排序后，相邻数之间异或最小值。

现在我们将 a 从小到大排好序。

根据上面的性质，我们发现如果 i 和 i+k 之间连了边，说明对于所有 j \in [i+1,i+k-1]，j 都和 i 或 i+k 之间连了一条边。

如果 k 很大的话，这样的图应该不是二分图。

也就是说，k 有个上限，超过这个上限，就不是肯定二分图。并且这个上限应该不大。

考试时如果能推到这就随便弄个 k=10 就可以过了。

但是我们还是证明一下结论：

结论： 若 k \le 4，则图肯定不是二分图。

证明：

依然是考虑第一个不完全相同的位第 x 位，对于 a_i 到 a_{i+4}，总共有 4 种情况：(0,0,0,0,1)，(0,0,0,1,1)，(0,0,1,1,1)，(0,1,1,1,1)。

对于前两种情况，前三个数之间两两连边，构成了一个奇环；对于后两种情况，后三个数构成一个奇环。

有奇环说明不是二分图，故 k=4 时成立，k > 4 时肯定也不成立了。

对于 k=3 是有可能的，实测会 Wrong Answer on test 46。

所以我们对于 i 来说，只用判断是否能连 i+1 至 i+3 即可。

如果最后是二分图，则肯定不存在 k \le 4 的情况；否则，多连再多边也不是二分图。

所以边数降至 3n 条，判断二分图是很基础的图上深搜，总时间复杂度 O(n \log n)，是真的强，吊打标算。

这道题最关键的地方在于去掉没有用的边，简化边的数量。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 2e5 + 5;
int n;
pair<int, int> a[MAXN];

vector<int> e[MAXN]; 
void add_edge(int u, int v) {
    e[u].push_back(v);
    e[v].push_back(u);
} 
int clr[MAXN] = {0};
bool flg;
void dfs(int x, int c) {
    if (clr[x] != -1) {
        if (clr[x] != c)
            flg = false;
        return;
    }
    clr[x] = c;
    for (auto i: e[x])
        dfs(i, 1 - c);
}

bool chk(int x) {//能否分成两个集合使得总价值不小于 x 
    for (int i = 1; i <= n; i++)
        e[i].clear(), clr[i] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= i + 3 && j <= n; j++)
            if ((a[i].first ^ a[j].first) < x)
                add_edge(a[i].second, a[j].second);
    flg = true;
    for (int i = 1; i <= n; i++)
        if (clr[i] == -1)
            dfs(i, 0);
    return flg; 
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].first, a[i].second = i;
    sort(a + 1, a + n + 1);
    int l = 1, r = (1 << 30) + 1;//[l, r)
    while (l + 1 < r) {
        int mid = (1ll * l + r) / 2;
        if (chk(mid))
            l = mid;
        else
            r = mid;
    }
    for (int i = 1; i <= n; i++)
        e[i].clear(), clr[i] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= i + 3 && j <= n; j++)
            if ((a[i].first ^ a[j].first) < l)
                add_edge(a[i].second, a[j].second);
    flg = true;
    for (int i = 1; i <= n; i++) 
        if (clr[i] == -1)
            dfs(i, 0);
    for (int i = 1; i <= n; i++)
        cout << clr[i];
    return 0;
}