专栏文章

题解：P4934 礼物

MMrkn_chenyx12
P4934题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miqn48dm
此快照首次捕获于
2025/12/04 07:30
3 个月前
此快照最后确认于
2025/12/04 07:30
3 个月前
查看原文

解题思路

首先我们可以发现，假设 a>ba>b，那么 abitand⁡b≥min⁡(a,b)a \operatorname{bitand} b \ge \min(a, b) 当且仅当 abitand⁡b=ba\operatorname{bitand}b=b。显然地，如果 a=∑i∈S2ia=\sum_{i\in S}2^i，那么 aa 就不能与 b=∑i∈T2ib=\sum_{i\in T}2^i 存在于同一个箱子，其中 TT 是 SS 的子集。
考虑拓扑排序，每个数字 uu 向所有比它小且不能与它共存的数字 vv 连边，并且置 ansv←max⁡(ansv,ansu+1)ans_v\gets\max(ans_v,ans_u+1)，其中 ansxans_x 表示数字 xx 放在哪一个箱子中。
但是这样每个数字连出边的量级是 2popcount⁡x2^{\operatorname{popcount}x} 的，显然在后面几组数据中不可行。于是考虑每个数字只向二进制下只比它少一位 11 且不能与它共存的数字连边，无论目标数字是否存在，可以证明那些被忽略的边必然会被间接连接。这样每个数字连出边的量级只有 popcount⁡x\operatorname{popcount} x，可以通过。
另外，注意使用这种方式连边需要为 1…2k−11\ldots2^k-1 中的每一个数字而不仅仅是输入的数字连边。拓扑排序时，如果 uu 不属于输入，则应该更新 ansvans_v 为 max⁡(ansv,ansu)\max(ans_v,ans_u)，而不是 max⁡(ansv,ansu+1)\max(ans_v,ans_u+1)。

参考代码

CPP
#include <bits/stdc++.h>
using namespace std;

int n, k, a[1000024], r[1050024], in[1050024], msv[1050024];
int ev[22000024], ex[22000024], es[1050024], ecnt;
vector<int> ans[24];

void add(int u, int v) {
    ev[++ecnt] = v;
    ex[ecnt] = es[u];
    es[u] = ecnt;
    in[v]++;
}

#define lowbit(x) ((x) & -(x))

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        r[a[i]] = i;
    }
    sort(a + 1, a + n + 1);
    for (int i = 0; i < (1 << k); i++) {
        int tmp = i;
        while (tmp) {
            int x = lowbit(tmp);
            add(i, i - x);
            tmp -= x;
        }
    }
    queue<int> q;
    q.push((1 << k) - 1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        int t = r[u];
        if (t) ans[msv[u] + 1].push_back(u);
        for (int i = es[u]; i; i = ex[i]) {
            int v = ev[i];
            if (t) msv[v] = max(msv[v], msv[u] + 1);
            else msv[v] = max(msv[v], msv[u]);
            if (!--in[v]) q.push(v);
        }
    }
    int x = 1;
    for (; ans[x].size(); x++);
    x--;
    printf("1\n%d\n", x);
    for (int i = 1; i <= x; i++) {
        printf("%d", ans[i].size());
        for (auto u : ans[i]) {
            printf(" %d", u);
        }
        puts("");
    }
    return 0;
}

评论

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

正在加载评论...