题解 [牛客OI周赛15-提高组C] 回到过去
回到过去
https://ac.nowcoder.com/acm/contest/4912/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; }