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 <bits/stdc++.h>
using namespace std;
const int MN=120000;
bitset <MN> 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<=a1; ++i) dp|=(dp<<1);
for(int i=1; i<=a2; ++i) dp|=(dp<<2);
for(int i=1; i<=a3; ++i) dp|=(dp<<3);
for(int i=1; i<=a4; ++i) dp|=(dp<<4);
for(int i=1; i<=a5; ++i) dp|=(dp<<5);
for(int i=1; i<=a6; ++i) dp|=(dp<<6);
cout<<"Collection #"<<++cnt<<":\n";
if(sum%2==1||dp.test(sum/2)==0){
cout<<"Can't be divided.\n";
}else{
cout<<"Can be divided.\n";
}
cout<<'\n';
}
return 0;
}
浙公網安備 33010602011771號