题解：P4934 礼物

Mrkn_chenyx12 · 2024-12-28 11:24:07 · 题解

解题思路

首先我们可以发现，假设 a>b，那么 a \operatorname{bitand} b \ge \min(a, b) 当且仅当 a\operatorname{bitand}b=b。显然地，如果 a=\sum_{i\in S}2^i，那么 a 就不能与 b=\sum_{i\in T}2^i 存在于同一个箱子，其中 T 是 S 的子集。

考虑拓扑排序，每个数字 u 向所有比它小且不能与它共存的数字 v 连边，并且置 ans_v\gets\max(ans_v,ans_u+1)，其中 ans_x 表示数字 x 放在哪一个箱子中。

但是这样每个数字连出边的量级是 2^{\operatorname{popcount}x} 的，显然在后面几组数据中不可行。于是考虑每个数字只向二进制下只比它少一位 1 且不能与它共存的数字连边，无论目标数字是否存在，可以证明那些被忽略的边必然会被间接连接。这样每个数字连出边的量级只有 \operatorname{popcount} x，可以通过。

另外，注意使用这种方式连边需要为 1\ldots2^k-1 中的每一个数字而不仅仅是输入的数字连边。拓扑排序时，如果 u 不属于输入，则应该更新 ans_v 为 \max(ans_v,ans_u)，而不是 \max(ans_v,ans_u+1)。

参考代码

#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;
}