算法设计基础（八）

集合思维，甚至用一些群论的思想
常常能够帮助我们分析问题，并且找到开创性的思维方式来解决问题

集合思维与增量法

Acwing115

const int maxn = 1000 + 10;
const int inf = 0x3f3f3f3f;
int n, root, ans = 0;

class A {
public:
    int pa;
    int sum, sz;
    double avg;
} a[maxn];

void init() {
    ans = 0;
}

int getMax() {
    double res = 0;
    int ans = 0;
    _rep(i, 1, n) {
        if (i == root) continue;
        if (a[i].avg > res) {
            res = a[i].avg;
            ans = i;
        }
    }
    return ans;
}

void rmv(int u, int pa) {
    a[u].avg = -inf;
    for (int i = 1; i <= n; i++) {
        if (a[i].pa == u) a[i].pa = pa;
    }

    a[pa].sz += a[u].sz;
    a[pa].sum += a[u].sum;
    a[pa].avg = (double)a[pa].sum / a[pa].sz;
}

void solve() {
    _for(step, 0, n-1) {
        int u = getMax();
        if (u == 0) return;

        int pa = a[u].pa;
        int delta = a[pa].sz * a[u].sum;
        ans += delta;

        // then remove u
        rmv(u, pa);
    }
    printf("%d\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    init();

    // get data
    scanf("%d%d", &n, &root);
    _rep(i, 1, n) {
        scanf("%d", &a[i].sum);
        ans += a[i].sum;
        a[i].sz = 1, a[i].avg = 1.0 * a[i].sum;
    }
    _for(i, 0, n-1) {
        int x, y;
        scanf("%d%d", &x, &y);
        a[y].pa = x;
    }

    // then solve
    // debug(ans);
    solve();
}

KDTree 解决平面问题

KDTree 的本质其实是中位数和分治算法

KDTree找平面最近点对

HDU5992

const int maxn = (200000 + 5) * 2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int CD = 0, K = 2, n, m;
int root;

class Node {
public:
    int x[2], cld[2];
    int cost, id;

    bool operator< (const Node &rhs) const {
        return x[CD] < rhs.x[CD];
    }
} t[maxn];

int build(int l, int r, int dep) {
    if (l > r) return 0;
    int mid = (l + r) >> 1;
    CD = dep % K;

    nth_element(t+l, t+mid, t+r+1);
    t[mid].cld[0] = t[mid].cld[1] = 0;
    if (l < mid) t[mid].cld[0] = build(l, mid-1, dep+1);
    if (r > mid) t[mid].cld[1] = build(mid + 1, r, dep+1);

    return mid;
}

inline ll euclid(const Node& u, const Node& g) {
    ll ans = 0;
    _for(i, 0, K) ans += 1ll*(u.x[i] - g.x[i])*(u.x[i] - g.x[i]);
    return ans;
}

inline bool valid(const Node& u, const Node& g) {
    return u.cost <= g.cost;
}
typedef pair<ll, Node> PR;
PR ans;
// ans: (dist, Node)

void query(int u, const Node& g, int dep) {
    if (!u) return;

    ll dist = euclid(t[u], g);
    if (dist == ans.first && valid(t[u], g) && t[u].id < ans.second.id) ans = make_pair(dist, t[u]);
    if (dist < ans.first && valid(t[u], g)) ans = make_pair(dist, t[u]);

    int cd = dep % K;
    ll delta = 1ll * (t[u].x[cd] - g.x[cd]);
    if (delta > 0) {
        query(t[u].cld[0], g, dep+1);
        if (delta * delta < ans.first) query(t[u].cld[1], g, dep+1);
    }
    else {
        query(t[u].cld[1], g, dep+1);
        if (delta * delta < ans.first) query(t[u].cld[0], g, dep+1);
    }
}

void solve() {
    // get query data
    for( ; m; m--) {
        Node g;
        scanf("%d%d%d", &g.x[0], &g.x[1], &g.cost);
        //debug(g.cost);
        ans = make_pair(inf, Node());

        query(root, g, 0);
        _for(i, 0, K) printf("%d ", ans.second.x[i]);
        printf("%d\n", ans.second.cost);
    }
}

void init() {
    K = 2;
    CD = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;

    while (kase--) {
        init();

        // get hotel data
        scanf("%d%d", &n, &m);
        //debug(m);
        _rep(i, 1, n) {
            scanf("%d%d%d", &t[i].x[0], &t[i].x[1], &t[i].cost);
            t[i].id = i;
        }

        // build kdtree
        root = build(1, n, 0);

        // then solve
        solve();
    }
}

KDTree找K近邻

HDU4347

const int maxn = (50000 + 5) << 1;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, K, q, CD = 0;

class Node {
public:
    int x[6], cld[2];

    bool operator< (const Node &rhs) const {
        if (x[CD] != rhs.x[CD]) return x[CD] < rhs.x[CD];
        _for(i, CD, K) if (x[i] != rhs.x[i]) return x[i] < rhs.x[i];
        _for(i, 0, CD) if (x[i] != rhs.x[i]) return x[i] < rhs.x[i];
        return x[CD] < rhs.x[CD];
    }
} t[maxn];

int root = 0;
int build(int l, int r, int dep) {
    if (l > r) return 0;
    int mid = (l + r) >> 1;
    CD = dep % K;

    nth_element(t+l, t+mid, t+r+1);
    t[mid].cld[0] = t[mid].cld[1] = 0;
    if (l < mid) t[mid].cld[0] = build(l, mid-1, dep+1);
    if (r > mid) t[mid].cld[1] = build(mid+1, r, dep+1);

    return mid;
}

inline ll euclid(const Node &u, const Node &g) {
    ll ans = 0;
    _for(i, 0, K) ans += 1ll*(u.x[i]-g.x[i]) * (u.x[i]-g.x[i]);
    return ans;
}

typedef pair<ll, Node> PR;
priority_queue<PR> ans;

void initans(int m) {
    while (ans.size()) ans.pop();
    _for(_, 0, m) ans.push(make_pair(inf, Node()));
}

void query(int u, const Node &g, int dep) {
    if (!u) return;

    ll dist = euclid(t[u], g);
    //debug(dist);
    if (dist < ans.top().first) ans.pop(), ans.push(make_pair(dist, t[u]));

    int cd = dep % K;
    ll delta = t[u].x[cd] - g.x[cd];
    //debug(delta);

    if (delta > 0) {
        query(t[u].cld[0], g, dep+1);
        if (delta * delta < ans.top().first) query(t[u].cld[1], g, dep+1);
    }
    else {
        query(t[u].cld[1], g, dep+1);
        if (delta * delta < ans.top().first) query(t[u].cld[0], g, dep+1);
    }
}

void solve() {
    scanf("%d", &q);
    while (q--) {
        Node g;
        _for(i, 0, K) scanf("%d", &g.x[i]);
        int m;
        scanf("%d", &m);
        initans(m);
        assert(ans.size() == m);

        query(root, g, 0);
        stack<PR> res;
        while (!ans.empty()) res.push(ans.top()), ans.pop();

        printf("the closest %d points are:\n", m);
        while (!res.empty()) {
            PR u = res.top();
            res.pop();
            _for(i, 0, K) {
                //debug(x.first);
                printf("%d", u.second.x[i]);
                i != K-1 ? printf(" ") : printf("\n");
            }
        }
    }
}

void init() {
    CD = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (~scanf("%d%d", &n, &K)) {
        init();

        // get data
        _rep(i, 1, n) _for(j, 0, K) scanf("%d", &t[i].x[j]);

        // build kdtree
        root = build(1, n, 0);
        // solve
        solve();
    }
}

平面分治算法

Acwing119

const int maxn = 200000 + 10;
const double inf = 1e10;
int n;

class A {
public:
    double x, y;
    bool type;

    bool operator< (const A &rhs) const {
        return x < rhs.x;
    }
} a[maxn], buf[maxn];

double dist(A &a , A &b) {
    if (a.type == b.type) return inf;
    double dx = a.x-b.x, dy = a.y-b.y;
    return sqrt(dx*dx + dy*dy);
}

double dfs(int l, int r) {
    if (l >= r) return inf;
    int mid = (l+r)>>1;
    //debug(mid);
    double mid_x = a[mid].x;
    double res = min(dfs(l, mid), dfs(mid+1, r));

    {
        // merge
        int i = l, j = mid+1;
        for (int k = l; k <= r; k++) {
            if (j > r || (i <= mid && a[i].y < a[j].y)) buf[k] = a[i++];
            else buf[k] = a[j++];
        }

        for (int k = l; k <= r; k++) a[k] = buf[k];
    }

    vector<A> tmp;
    _rep(i, l, r) {
        if (a[i].x >= mid_x - res && a[i].x <= mid_x + res) tmp.push_back(a[i]);
    }
    for (int i = 1; i < tmp.size(); i++) {
        for (int j = i; j >= 0 && tmp[i].y - tmp[j].y < res; j--) {
            res = min(res, dist(tmp[i], tmp[j]));
        }
    }
    //debug(res);
    return res;
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;

    while (kase--) {
        init();
        scanf("%d", &n);

        // get data
        _for(i, 0, n) {
            scanf("%lf%lf", &a[i].x, &a[i].y);
            a[i].type = 0;
        }
        _for(i, n, n << 1) {
            scanf("%lf%lf", &a[i].x, &a[i].y);
            a[i].type = 1;
        }

        // then sort and dfs
        sort(a, a+(n<<1));
        printf("%.3lf\n", dfs(0, (n<<1)-1));
    }
}