弹珠-题解

发表于 2022-07-13 分类于信奥，题解阅读次数：

原题链接：Link

题目描述

有六种不同价值的弹珠，告诉你每一种有多少个，求能不能将弹珠均分为相等的两份。

输入格式给的很费解，其实就是给出了价值分别为 \(1 \sim 6\) 的弹珠的个数，此外输出格式里还要求多打一个空行，~~就坑的离谱~~。

思路分析

很容易想到的特判：如果总价值是奇数，直接输出 Can't be divided.

然后就很关键了，题目可以理解为：在所有珍珠中选出一些，使得价值和正好是总价值的一半。

怎么实现这个算法呢？

在一堆东西里面选出一些，使得总价值满足一定条件，很容易可以想到背包问题。
（如果没有学习过背包的，建议移步AcWing背包九讲(主题库2~10题)或者P1048）。
以下默认各位大佬都会01背包。

我们可以把珍珠的价值也看做费用，求在价值和不超过总价值的一半的前提下能够选的的最大价值，如果这个最大价值就是总价值的一半，那么可以均分，否则不行。

所以这个问题就可以转化为：
一共有6种弹珠，每种弹珠可能有多种，在价值和不超过总价值的一半的前提下求出能够选的的最大价值。

~~各位大佬肯定一眼就看出来~~这是一个多重背包问题。

多重背包

多重背包问题可以转化为01背包问题求解，最朴素的方法就是把一种当中的 \(n\) 个看成 \(n\) 个不同的物品，然后每个物品都可以取或者不取。也就是在经过如下操作后套用01背包模板：

int a[maxn]; //存储价值
int j = 1;
for (int i = 1; i <= 6; i++) {
	int t;
	cin >> t;
	while (t--) {
		a[j++] = i;
	}
}

时间复杂度 \(O(n\cdot sum/2)\) （ \(sum\) 为价值和）。这样跑一遍最大是 \(20000 \times 60000 / 2\) ，已经T飞了，况且还有多组数据。

所以我们要进行优化。观察上面的步骤，让时间复杂度剧增的就是把一种当中的 \(n\) 个看成 \(n\) 个不同的物品，由于每一种物品都可能有很多个，所以最终的物品总数会很大。我们可以在这个方面着手优化：

我们的最终目的是使得分出来的物品可以表示 \(1 \sim n\) 里面的所有价值，为了达成这一目的，我们并不需要分出 \(n\) 个物体。

二进制优化

在计算机中，为了表示 \(1 \sim x\) ，我们只需要 \(\log_2 x\) 个bit。同样的道理，为了表示 \(1 \sim n\) 的所有数，我们只需把 \(n\) 拆分成 \(\log_2 n\) 个数。举个例子，对于 \(n = 30\) 我们可以拆成 \(1, 2, 4, 8, 15\) ，各位大佬可以自己试验亿下，一定可以表示 \(1 \sim 30\) 中的所有数。

根据这个原理，我们可以更改上述代码：

int j = 1;
for (int i = 1; i <= 6; i++) {
	int t;
	cin >> t;
	int k = 1;
	while (k <= t) {
		a[j++] = k * i;
		t -= k;
		k <<= 1;
	}
	if (t > 0) a[j++] = t * i;
}

再次套用01背包模板，时间复杂度为 \(O(log_2 n \cdot sum/2)\) ，这样就快多了。

效率：https://www.luogu.com.cn/record/59760585。

AC代码

code

#include <bits/stdc++.h>
using namespace std;

#define uns unsigned
#define ll long long
#define use_cin_cout do { ios::sync_with_stdio(false); cin.tie(); } while (false)
#define endl '\n'

const ll inf_ll = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int maxv = 6e4 + 5, maxn = 2e4 + 5;

int sum, collection;
int dp[maxv], a[maxn];

int main() {
	use_cin_cout;
	
	while (true) {
		collection++;
		
		bool end = true;
		sum = 0;
		memset(a, 0, sizeof(a));
		memset(dp, 0, sizeof(dp));
		
		int j = 1;
		for (int i = 1; i <= 6; i++) {
			int t;
			cin >> t;
			sum += t * i;
			if (t != 0) end = false;
			
			int k = 1;
			while (k <= t) {
				a[j++] = k * i;
				t -= k;
				k <<= 1;
			}
			if (t > 0) a[j++] = t * i;
		}
		
		if (end) return 0;
		
		cout << "Collection #" << collection << ":" << endl;
		
		if (sum & 1) {
			cout << "Can't be divided." << endl << endl;
			continue;
		}
		
		bool flag = false;
		for (int i = 1; i < j; i++) {
			for (int v = (sum >> 1); v >= a[i]; v--) {
				dp[v] = max(dp[v], dp[v - a[i]] + a[i]);
				
				if (dp[v] == (sum >> 1)) {
					flag = true;
					break;
				}
			}
		}
		
		if (flag) cout << "Can be divided." << endl << endl;
		else cout << "Can't be divided." << endl << endl;
	}
	
	return 0;
}