P1537 弹珠
P1537 弹珠题目描述
玛莎和比尔各自有自己的弹珠收藏。他们想重新分配收藏品，使两人能平等拥有弹珠。如果所有的弹珠的价值相同，那么他们就可以平分。但不幸的是，有一些弹珠更大，或者更美丽，所以，玛莎和比尔给每个弹珠一个 \(1\) 到 \(6\) 的价值。现在他们想平分这些弹珠，使每个人得到的总价值相同。不幸的是，他们发现，他们可能无法以这种方式分弹珠（即使弹珠的总价值为偶数）。例如，如果有一个价值为 \(1\)、一个价值为 \(3\) 和两个价值为 \(4\) 的弹珠，这样他们就不能把弹珠分为价值相等的两部分。因此，他们想要你写一个程序，告诉他们是否能将所有弹珠分成价值相等的两部分。
输入格式
输入文件有若干行，行中包含六个非负整数 \(N_1,\cdots,N_6\)，其中 \(N_i\) 是价值为 \(i\) 的弹珠的个数。最大弹珠总数将达到 \(2\times 10^4\)。
输入文件的最后一行是 0 0 0 0 0 0。不要处理这一行。
输出格式
对于每一组数据，输出 Collection #k:，\(k\) 为输出的是第几组，接着是 Can be divided. 或 Can't be divided.。
每一组输出后多打一个空行。可以参考样例。
输入输出样例 #1
输入 #1
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0输出 #1
Collection #1:
Can't be divided.
Collection #2:
Can be divided.这题很容易发现是一个可行性背包，但是如果我们直接这么做的话，我们的世间复杂度是 \(O(sumval\times n)\)，这个显然是不行的，我们使用 bitset 优化一下就行，这样可以在复杂度上处以一个 \(w\)，这样就能过了。
点击查看代码#include using namespace std;const int MN=120000;bitsetdp;int a1, a2, a3, a4, a5, a6, cnt=0;int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); while(cin>>a1>>a2>>a3>>a4>>a5>>a6){ if(a1==0&&a2==0&&a3==0&&a4==0&&a5==0&&a6==0) break; dp.reset(); dp.set(0,1); int sum=0; sum+=a1*1+a2*2+a3*3+a4*4+a5*5+a6*6; for(int i=1; i 感谢分享 感谢分享 懂技术并乐意极积无私分享的人越来越少。珍惜 谢谢楼主提供！ 热心回复！ 前排留名，哈哈哈 感谢分享，学习下。 用心讨论，共获提升！ 这个有用。 这个好，看起来很实用 谢谢分享，辛苦了 谢谢楼主提供！ 鼓励转贴优秀软件安全工具和文档！ 谢谢楼主提供！ 前排留名，哈哈哈 谢谢分享，试用一下 谢谢分享，试用一下 感谢发布原创作品，程序园因你更精彩 谢谢分享，辛苦了
页:
[1]
2