ICPC NEAU 2020 支付

ICPC NEAU 2020 支付

有n 个物品，第i 个物品的价值为wi，选择若干物品，这些物品的价值和为S 作为支付手段，希望选择一部分物品能精确地支付不大于k 的所有金额，即任意s 满足 1 ≤ s ≤ k 都有对应的选择方案使S = s 给定k 的值，构造满足要求的序列wi，使n 尽可能小的前提下wi 的和尽可能小 首先我们思考一下1. Solution: 1可以与任何数字组合。所以对于当前位置的第1位，可以塑造( n - 1 )组。再考虑一下非1的情况。为了防止它们被合并，我们用(n+1)和2n之间的数字填充这些情况。沿着这样的思路，它们被分割成数目相近的领域，而这些集合必须集合在类似的领域中，接受当前领域有x个集合，成形的集合是x(x-1)/2个集合。

#include#defineusing namespace std;int num,T;vector ans;ll n;int main() { scanf("%d",&T); while(T--){ ans.clear(); scanf("%lld",&n);num=0; while(n) ans.push_back((n+1)>>1),n>>=1,++num; printf("%d\n",num); for(int i=num;i>=1;--i) printf("%lld ",ans[i-1]); puts(""); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。