题解：CF755F PolandBall and Gifts

_saltFish_ · 2024-09-07 15:21:12 · 题解

简要题意

给出若干个有向环，共 n 个点。选择 k 个不同的点，删除与这些点相连边，求最少删除多少条边和最多删除多少条边。

思路

按照送礼顺序连边能得到很多个有向环。一个人没带礼物相当于删除这个与点相连的所有边，答案就是删除的边的数量。最小化当然是尽量让同一个环中的人不带，这样可以使删除的边尽量重复。最多只会有 k+1 个人收不到礼物，取决于能否恰好填满若干个环，也就是用若干个数凑出 k。做 0-1 背包，时间复杂度 O(nk)。最大值明显是每两个相邻的删一个，还能删就删拿到了礼物的，剩下的对答案没有贡献。

优化求最小答案的过程。瓶颈在于 0-1 背包，貌似可以直接考虑分组背包。设大小不同的环有 m 个，最坏情况下环的大小是 2,3,4\dots 那么 \frac{(2+m+1)\times m}{2}=n 也就是说 m\le\sqrt{n}，直接二进制分组的复杂度为 O(n\log{n}+mk\log{\frac{n}{m}}) 实际上根本跑不满。

code

丑陋的考场代码，轻喷。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int n, k, fa[N], siz[N], num[N], tot, w[N];
bool used[N], f[N];

int fnd(int x) {
    if(fa[x] == x) {
        return x;
    }
    return fa[x] = fnd(fa[x]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int _T = 1;//考场上有多测

    while(_T--) {
        cin >> n >> k;

        for(int i = 1; i <= n; i++) {
            siz[i] = 1;
            fa[i] = i;
            used[i] = 0;
            f[i] = 0;
            num[i] = 0;
        }

        for(int i = 1; i <= n; i++) {
            int p;

            cin >> p;

            if(fnd(p) != fnd(i)) {
                siz[fnd(p)] += siz[fnd(i)];
                fa[fnd(i)] = fnd(p);
            }
        }

        f[0] = 1;

        int ans = 0, now = k, cnt = 0;

        for(int i = 1; i <= n; i++) {
            if(!used[fnd(i)]) {
                used[fnd(i)] = 1;

                int x = siz[fnd(i)];

                // for(int j = k; j - x >= 0; j--) {//70pts
                //     f[j] |= f[j - x];
                // }
                num[x]++;

                int can = min(now, siz[fnd(i)] / 2);

                ans += can * 2;
                now -= can;

                if(siz[fnd(i)] % 2 == 1) {
                    cnt++;
                }
            }
        }

        ans += min(now, cnt);

        tot = 0;

        for(int i = 1; i <= n; i++) {//mlogn
            if(num[i]) {//m
                for(int j = 1; j <= num[i]; j <<= 1) {//logn
                    w[++tot] = i * j;
                    num[i] -= j;
                }

                if(num[i]) {
                    w[++tot] = i * num[i];
                }
            }
        }

        // cout << tot << ' ';

        for(int i = 1; i <= tot; i++) {//mklogm 100pts
            for(int j = k; j - w[i] >= 0; j--) {
                f[j] |= f[j - w[i]];
            }
        }

        if(f[k]) {
            cout << k << ' ';
        } else {
            cout << k + 1 << ' ';
        }

        cout << ans << '\n';
    }
}