首页 > 奇怪的背包问题增加了
开通博客写题解
头像 段三园的小迷弟
发表于 2020-03-23 10:14:44
加数ci<2^30，所以如果加数和大于2^30，则一定有组合可以构成2^30 注意这里和一般加法不同，一般的如234+567，而这里就好比 只允许加上1,10,100。。。而不允许加上567这样的数字 然后就是找到这样的组合，这里从大到小排列这些ci，初始sum=2^30，如果ci 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 熠丶
发表于 2021-05-07 13:43:41
做法 先记录每种体积的背包数以及下标因为每两个体积为的背包能合成一个体积为的背包所以我们只需要把背包从小到大开始合并，判断体积为的背包数是否大于等于2个即可然后按照体积从大到小开始找背包，初始是需要2个体积为的背包，该层不满足则需要调到下一层，并且数量是当前的两倍 代码 // Problem: 奇怪 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 白菜茄子
发表于 2020-03-24 22:49:05
网址：https://ac.nowcoder.com/acm/contest/4784/H 题目描述 有一个容量为2^30的背包，和m件物品，第i件物品的体积为c_i，你需要从中选出若干件，使得选出的物品的体积恰好等于背包容量。这些物品有一个奇怪的特性，那就是c_i = 2^ki，其中0<=k 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 jzdx（hjh）
发表于 2021-05-06 17:43:30
题号 NC204441名称H-奇怪的背包问题增加了来源 [牛客小白月赛23] 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K Special Judge, 64bit IO Format: %lld题目描述 有一个容量为的背包，和m件物品，第i 展开全文
去ta的博客 赞 (0) 回复(2) 收起
头像 2wx
发表于 2021-05-07 17:39:00
写题的时候最开始想的是bitset写一个背包，但是这道题里bitset开不下然后想到了CF上写过的这道题CF1498B题意是说给定一个容量为w的背包，每个物件的体积都是2的幂次方，求最少能用多少个背包把所有物件装下迭代N次，每次迭代25位，选出一个可选的最大的物块。这样每个背包里容量都是尽可能大的。 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”