专栏文章

题解：CF755F PolandBall and Gifts

WWTR2007
CF755F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqdoto5
此快照首次捕获于
2025/12/04 03:06
3 个月前
此快照最后确认于
2025/12/04 03:06
3 个月前
查看原文
给出一种新的复杂度证明。
最大值容易直接贪心计算，最小值需要判断环长能否恰凑成 kk，暴力背包的复杂度无法通过。
记环长形成的集合为 SS，由 ∣S∣≤n|S| \le \sqrt{n} 可以发现种类数不多，原题被转化为了多重背包，若用单调队列优化复杂度为 O(nn)\mathcal{O}(n\sqrt{n})，无法通过。
若使用二进制优化解决，记长度为 ii 的环个数为 cic_i，则时间复杂度为 O(n∑popc(cx)w)\mathcal{O}(\frac{n\sum\limits \text{popc}(c_x)}{w})。
下面证明在 ∑x∈Sxcx≤n\sum\limits_{x \in S} xc_x \le n 的条件下，∑xpopc(cx)≤n\sum\limits_x \text{popc}(c_x) \le \sqrt{n}。
不妨设 cx=2z−1c_x = 2^z-1，其中 zz 为非负整数，设 tzt_z 为 cx=2z−1c_x = 2^z - 1 的个数。若令 hzh_z 为 tzt_z 的后缀和，易得 ∑zhz22z≤n\sum\limits_z h_z^22^z \le n 时，则 ∑xpopc(cx)=∑hz≤∑hz2≤∑hz22z≤n\sum\limits_x \text{popc}(c_x) = \sum\limits h_z \le \sqrt{\sum\limits h_z^2} \le \sqrt{\sum\limits h_z^22^z} \le \sqrt{n}，证毕。
因此最终时间复杂度为 O(nnw)\mathcal{O}(\frac{n\sqrt{n}}{w})。
CPP
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define MULT_TEST 0
using namespace std;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const int N = 1000005;
int cnt[N];
bitset<N> R;
struct dsu {
    vector<int> fa, siz;
    dsu(int n) : fa(n + 2), siz(n + 2, 1) { iota(fa.begin(), fa.end(), 0); };
    inline int Find(int r) {
        while (r != fa[r]) r = fa[r] = fa[fa[r]];
        return r;
    }
    inline bool Merge(int x, int y) {
        x = Find(x); y = Find(y);
        if (x == y) return true;
        else return fa[y] = x, siz[x] += siz[y], false;
    }
};
inline int read() {
    int w = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        w = (w << 1) + (w << 3) + ch - 48;
        ch = getchar();
    }
    return w * f;
}
inline int lowbit(int x) {
    return x & (-x);
}
inline void Solve() {
    int n, k;
    n = read(); k = read();
    if (k == 0) {
        printf("0 0\n");
        return ;
    }
    dsu A(n + 1);
    vector<int> b, q;
    for (int i = 1; i <= n; i++) {
        int p = read();
        A.Merge(p, i);
    }
    for (int i = 1; i <= n; i++)
        if (A.Find(i) == i) b.push_back(A.siz[i]);
    int m = b.size(), sum = 0, opt = 0, ans = 0;
    sort(b.begin(), b.end());
    for (int i = 0; i < m; i++) cnt[b[i]]++;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 20; j++) {
            if (cnt[i] > (1 << j)) {
                q.push_back(i * (1 << j));
                cnt[i] -= (1 << j);
            }
        }
        if (cnt[i]) q.push_back(i * cnt[i]);
    }
    R.set(0);
    for (auto x : q) R |= R << x;
    if (R.test(k)) printf("%lld ", k);
    else printf("%lld ", k + 1);
    for (int i = 0; i < m; i++) {
        int x = b[i] / 2;
        if (b[i] & 1) opt++;
        if (sum + x < k) ans += 2 * x, sum += x;
        else {
            ans += 2 * (k - sum);
            printf("%lld\n", ans);
            return ;
        }
    }
    k -= sum;
    if (opt <= k) printf("%lld\n", n);
    else printf("%lld\n", ans + k);
}
signed main() {
    int T = 1;
#if MULT_TEST
    T = read();
#endif 
    while (T--) Solve();
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...