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. 1 0 1 2 0 0
2. 1 0 0 0 1 1
3. 0 0 0 0 0 0

复制代码

输出 #1

1. Collection #1:
2. Can't be divided.
4. Collection #2:
5. Can be divided.

复制代码

这题很容易发现是一个可行性背包，但是如果我们直接这么做的话，我们的世间复杂度是 \(O(sumval\times n)\)，这个显然是不行的，我们使用 bitset 优化一下就行，这样可以在复杂度上处以一个 \(w\)，这样就能过了。
点击查看代码[code]#include using namespace std;const int MN=120000;bitset  dp;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