gym100702D Log Set

版本 T0。

学背包不做 Log Set，就像打二游不玩某二字开放世界游戏，追星不追理塘王丁真珍珠，玩泣系旮旯不玩克拉纳的，只能度过一个相对失败的人生。

Problem

有一个大小为 \(m(m \le 60)\) 的多重集 \(S\)，它的所有子集（包括空集）和组成了一个大小为 \(2^{m}\) 的多重集 \(T\)。

现在以如下方式给定 \(T\)：给定一个正整数 \(n(n \le 10^4)\)，表示 \(T\) 中不同元素的数量。

给定 \(n\) 个二元组，第 \(i\) 个二元组 \((a_i, b_i)\) 表示数字 \(a_i\) 在 \(T\) 中出现了 \(b_i\) 次。

请求出符合条件的 \(S\) 中按元素大小升序排序后字典序最小的方案。

\(S^{'} < S^{''}\)，当且仅当 \(\exists k, 1 \le k \le m\)，\(\forall i, 1 \le i < k, S^{'}_i = S^{''}_i\)，\(S^{'}_k < S^{''}_k\)。

Solution

模拟赛时的部分分设了一个 \(m \le 20\)，\(T\) 中的元素非负。好啊！每次拎出 \(T\) 中的最小值，这个最小值一定是 \(S\) 中的元素，对其做一遍撤销。直到所有元素确定完。好！模拟赛时获得了 \(35pts\) 的好成绩。

这个部分分给的太牛了，因为正解是每次按 \(T\) 中元素最大的那两个来确定 \(S\) 中元素的！！！（/yun/yun/yun

记 \(A\) 表示 \(T\) 中当前最大的值，\(B\) 表示 \(T\) 中当前次大值。

记 \(d = B - A\)。

若 \(d = 0\)，说明 \(T\) 中只剩下一种数了，可以单独判掉。

否则，\(d\) 或 \(-d\) 一定是 \(S\) 中的元素，且一定是 \(S\) 中（除 \(0\) 外）的最小元素。

对 \(d \neq 0\) 简要说明：要么 \(B\) 加一个负数成为 \(A\)，要么 \(A\) 加一个正数成为 \(B\)，这里只讨论 \(A + d = B, d > 0\) 的情况。

\(A\) 经过不断加数 \(x\) 成为 \(B\) 的过程，一定有 \(x \ge 0\)，否则 \(B\) 不是最大值。

假设 \(\exists x, y \in S, x > 0, y > 0\)，\(A + x + y = B\)，则 \(B > A + x, A + y > A\)，\(A\) 不是 \(T\) 中次大值，所以 \(A\) 至多加一个 \(S\) 中的数成为 \(B\)。

又因为 \(A \neq B\)，\(A\) 是次大值，所以中间缺的这一块是 \(S\) 中（非 \(0\) 元素）的最小值。

现在我们尚且只知道了 \(S\) 中一个元素的绝对值，那第二个元素、第三个元素又如何确定呢？就算确定出来了 \(S\) 中所有元素的绝对值，我们又如何得知 \(S\) 中每个元素真正的值、又如何得出字典序最小的方案呢？

01 背包中改变一个元素 \(x\) 的正负，等价于将 dp 数组整体平移 \(x\) 个单位。

神中神！这就是背包啊！

简要说明：只讨论 \(x > 0\) 的情况，其它情况类似。

现在有一个未加入 \(x\) 的 dp 数组 \(f\)，考虑加入 \(x\) 的本质：

先将 \(f\) 向右平移 \(x\) 个单位，得到 dp 数组 \(f^{'}\)，再将 \(f\) 与 \(f^{'}\) 合并（对应下标的 \(f\) 与 \(f^{'}\) 值相加），得到 dp 数组 \(g\)。

将 \(x\) 反号，再做一遍：先将 \(f\) 向左平移 \(x\) 个单位，得到 dp 数组 \(f^{''}\)，再将 \(f\) 与 \(f^{''}\) 合并（对应下标的 \(f\) 与 \(f^{''}\) 值相加），得到 dp 数组 \(h\)。

你发现 \(g\) 和 \(h\) 唯一的区别就是 \(x\) 个单位的位置偏移！

那先强行钦定得到的 \(d\) 全部取正数，这样并不会改变 dp 数组的值以及相对关系，只会改变 dp 数组的整体位置。

所以最大值和次大值的差是不变的，那么由上述算法得出的 \(d\) 也不会失其本原的意义。也就是说，我们可以得出 \(S\) 中每个元素的绝对值，我们记这个大小为 \(m\) 的可重集为 \(D\)。

现在可以进行定号了！

如果按照正确的 \(S\) 进行撤销，最终得到的 \(T\) 应该只剩下一个元素 \(0\)，表示空集。

而我们的算法中，当 \(S\) 中存在负数时，最后得到的 \(T\) 会是一个负数——由于我们把某些 \(-d\) 强行钦定成了 \(+ d\)，这会导致 dp 数组发生右偏，而 \(T\) 是我们在右偏错误下观测的，相对地，我们的原点发生的左偏——结果是，原点位于 \(0\) 的左侧，一个负数 \(\Delta\)。

幸运的是，我们能够知道，一个错误的元素能够导致多少偏移量。

贪心地按绝对值从大到小判断当前值是否能够反号。

这又是一个背包问题：有 \(m\) 个非负整数，选出若干个数使得它们的和为 \(-\Delta\)，并使方案最优。

将 \(D\) 降序排序，并对排序后的 \(D\) 倒序做一遍可行性背包。再正序确定每个数是否能反号，这个事情用先前处理的可行性背包判断。

实现上，由于元素数值太大，需要用 map, set 等工具进行辅助。

做可撤销背包和求答案的时间复杂度为 \(O(nm\log{n})\)。由于这里限制了 \(n \le 10^4\)，所以本做法可以通过。

Code

const int N = 1e4 + 5;
const int M = 65;
int T, n, m;
PLL a[N];
LL ans[M];
map<LL, LL> mp;
set<LL> f[M];
void work(int cas)
{
	mp.clear(); LL sum = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%lld", &a[i].fi);
	for(int i = 1; i <= n; ++i)
		scanf("%lld", &a[i].se);
	for(int i = 1; i <= n; ++i)
	{
		mp.insert(a[i]);
		sum += a[i].se;
	}
	m = log2(sum);
	for(int i = 1; i <= m + 1; ++i)
		f[i].clear();
	for(int i = 1; i <= m; ++i)
	{
		vector<PLL> vec; vec.clear();
		LL mx1 = 7210721, mx2 = 7210721;
		mx2 = mx1 = prev(mp.end())->fi;
		if(prev(mp.end()) != mp.begin())
			mx2 = prev(prev(mp.end()))->fi;
		LL p = mx1 - mx2;
		ans[i] = p;
		for(auto now : mp)
		{
			LL x = now.fi, c = now.se;
			if(c == 0)
			{
				vec.EB(MP(x, c));
				continue;
			}
			if(mp.find(x + p) == mp.end())
				continue;
			if(p == 0) mp[x] >>= 1;
			else mp[x + p] -= c;
		}
		for(auto now : vec)
			mp.erase(now.fi);
	}
	LL delta = abs(mp.begin()->fi);
	sort(ans + 1, ans + m + 1, [&](LL x, LL y){
		return x > y;
	});
	f[m + 1].insert(0);
	for(int i = m; i >= 1; --i)
		for(auto x : f[i + 1])
		{
			f[i].insert(x);
			f[i].insert(x + ans[i]);
		}
	for(int i = 1; i <= m; ++i)
		if(f[i + 1].find(delta - ans[i]) != f[i + 1].end())
			delta -= ans[i], ans[i] = -ans[i];
	sort(ans + 1, ans + m + 1);
	printf("Case #%d: ", cas);
	for(int i = 1; i <= m; ++i)
		printf("%lld ", ans[i]);
	puts("");
}
int main()
{
	scanf("%d", &T);
	for(int cas = 1; cas <= T; ++cas)
		work(cas);
	return 0;
}