P7862 [COCI2015-2016#2] DRŽAVA

pikiuk · 2023-08-31 19:39:56 · 题解

分享一种确定性做法。

首先对于 d 二分，问题转化为判定性问题。

可以发现，若一个县的大小大于等于 k，那么他一定合法，理由是一定能找到两个余数互补的城市（鸽巢原理）。

考察一个边长为 d\times d 的矩形，我们可以发现，若其中有不少于 4k 个点，那么 d 一定合法。证明可以同样是鸽巢原理，具体的，我们把一个矩形划分为四个子矩形，那么每个子矩形内的点一定可以构成一个县，且至少存在一个子矩形内的点多于 k 个。

我们对点的 x 轴扫描线，维护以当前点为右边界中点的矩形，并把当前点向当前矩形内所有点连边，可以用 set 维护，由上述分析发现，每个点的出边不超过 k 条。

连边结束后，对现有连通块做背包即可，单次检验时间复杂度是 \mathcal{O}(nk)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
using i64 = long long;
const int N = 5e4 + 7, K = 37;
int f[N][K], n, k, col[N], cnt;
vector<int> e[N], vec;
struct Point {
    int x, y, z;
} p[N];
struct cmp {
    bool operator () (const int &u, const int &v) const {
        return ((p[u].y == p[v].y) ? u > v : p[u].y < p[v].y);
    }
};
set <int, cmp> st;
void add (int &x, int y) { x = (x + y) >= k ? x + y - k : x + y; }
i64 dis (int u, int v) {
    return 0ll + 1ll * (p[u].x - p[v].x) * (p[u].x - p[v].x) + 1ll * (p[u].y - p[v].y) * (p[u].y - p[v].y);
}
void dfs (int u) {
    col[u] = cnt; vec.push_back (p[u].z);
    for (auto v : e[u]) if (! col[v]) dfs (v);
}
bool subset () {
    int m = (int) vec.size ();
    if (m > k) return true;
    for (int i = 1; i < k; i ++) f[m][i] = 0;
    f[m][0] = 1;
    for (int i = m - 1; ~i; i --) {
        for (int j = 0; j < k; j ++) {
            f[i][j] = f[i + 1][j];
            f[i][j] |= f[i + 1][(vec[i] + j) % k];
        }
        if (f[i + 1][vec[i]]) return true;
    }
    return false;
}
bool check (i64 d) {
    int sqrtd = (double) (sqrt (d) + 1);
    for (int i = 1; i <= n; i ++) e[i].clear (), col[i] = 0;
    cnt = 0; st.clear ();
    for (int i = 1, j = 1; i <= n; i ++) {
        for (; p[i].x - p[j].x > sqrtd and j <= i; ) 
            st.erase (j ++);
        if (st.empty ()) { st.insert (i); continue; }

        p[n + 1] = {0, p[i].y - sqrtd, 0}; int res = 0;
        for (auto it = st.lower_bound (n + 1); it != st.end (); it ++) {
            auto k = *it;
            if (p[k].y - p[i].y > sqrtd) break;
            if (++ res >= 4 * k) return true;
            if (dis (i, k) <= d) e[i].push_back (k), e[k].push_back (i);
        }
        st.insert (i);
    }
    for (int i = 1; i <= n; i ++) {
        vec.clear ();
        if (col[i]) continue;
        ++ cnt, dfs (i);
        if (subset ()) return true;
    }
    return false;
}
signed main () {
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) {
        cin >> p[i].x >> p[i].y >> p[i].z;
        p[i].z %= k;
    }
    sort (p + 1, p + n + 1, [&] (const Point &u, const Point &v) {
        return u.x == v.x ? u.y < v.y : u.x < v.x;
    });
    i64 l = 0, r = 1e18, ans = -1;
    while (l <= r) {
        i64 mid = (l + r) >> 1;
        if (check (mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }   
    cout << fixed << setprecision (3) << sqrt (ans);
}