题解 [牛客OI周赛15-提高组C] 回到过去

• 回到过去

题目描述

给定 给物品，第 个物品的大小为 ，如果两个物品大小相同，则这两个物品为一类。

要求选出一些物品总大小为 ，对于所有类别的物品，询问它是否必须被选至少一个。

不同类的物品，总大小不超过 ，且保证存在一种方案可以选出总大小为 的物品。

正解

暴力想法是对于每一类物品，不选它，然后跑背包看能不能凑出总大小为 的物品。

有一个特别优美的性质就是不同类的物品总大小不超过 ，这说明了最多只有 　种物品。

但是暴力跑背包时间复杂度还是不对，是 的，就算用 bitset 优化还是跑不了。

但只要预处理出前缀的背包状态，和后缀的背包状态，对于一个类 ，就只需要 的时间复杂度就可以判断是否可以凑成大小 了。

跑 0 / 1 背包用 bitset + 分组背包 优化一下，大概就可以卡进 1s 了。

时间复杂度 。 (鬼畜)

/*
    不同总和不超过 10^5
    不同的不超过 450 个 
*/
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define N 100005

using namespace std;

int n, m, tot;
int a[N], b[N];
bool vis[N];

bitset<N> f, g[450];

inline int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x;
}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++i)
        a[i] = read();

    sort(a + 1, a + n + 1);
    for(int i = 1, j; i <= n; i = j) {
        j = i;
        while(j <= n && a[j] == a[i])
            ++j;
        b[++tot] = j - i, a[tot] = a[i];
    }

    g[tot + 1][0] = 1;
    for(int i = tot; i >= 1; --i) {
        g[i] = g[i + 1];
        //for(int j = 1; j <= b[i] && j * a[i] <= m; ++j)
        //    g[i] = g[i] | g[i] << a[i];
        int temp = b[i], d = 1;
        while(true) {
            if(d * a[i] > m) break;
            g[i] = g[i] | g[i] << (d * a[i]);
            temp -= d, d <<= 1;
            if(temp <= d) {
                if(temp * a[i] > m) break;
                g[i] = g[i] | g[i] << (temp * a[i]);
                break;
            }
        }
    }

    f[0] = 1;
    for(int i = 1; i <= tot; ++i) {
        vis[i] = true;
        for(int j = 0; j <= m; ++j)
            if(f[j] && g[i + 1][m - j]) {
                vis[i] = false;
                break;
            }
        //for(int j = 1; j <= b[i] && j * a[i] <= m; ++j)
        //    f = f | f << a[i];
        int temp = b[i], d = 1;
        while(true) {
            if(d * a[i] > m) break;
            f = f | f << (d * a[i]);
            temp -= d, d <<= 1;
            if(temp <= d) {
                if(temp * a[i] > m) break;
                f = f | f << (temp * a[i]);
                break;
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= tot; ++i)
        if(vis[i])
            ++ans;

    printf("%d\n", ans);
    for(int i = 1; i <= tot; ++i)
        if(vis[i])
            printf("%d ", a[i]);
    putchar('\n');
    return 0;
}