[Luogu] CF949E Binary Cards

(Link)

Description

给出(n)个需要表示的数，你需要用最少的(2^k)或(-2^k)，使得能拼出所有需要表示的数。输出方案。

((n,|A_i|leq 100000,kleq20))

Solution

神奇的搜索。

要注意到一个数是最多被选一次的，否则答案一定不优；且不会同时用(2^k)和(-2^k)。

直接搜索即可。设集合(S)表示要被拼成数的集合，(f(S))为最小代价。

设(1)表示给(S)中所有奇数(+1)((f(S+1)))，(2)表示给(S)中所有奇数(-1)((f(S-1)))，(3)表示给(S)中所有数（偶数）(/2)((f(frac{S}{2})))。

当(S)都为偶数时，(f(S)=f(frac{S}{2}))，操作序列中加入一个(3)。

否则(f(S)=min(f(S-1),f(S+1))+1)，操作序列中加入一个(1)或(2)。

当(S)中只剩下(0)时，停止操作。

考虑某个操作序列对应的逆序列，其实就是把所有数拼出来的过程。且可以保证只会产生(2^k/-2^k)。

然鹅这道搜索远没有这么简单。。

首先是必须要剪枝的。其一，每次操作后，对(S)要去重；其二，要限制搜索深度。注意到(kle20)，考虑极端情况，即不断的(+1/-1;/2)，重复(20)次，此时最大搜索深度达到最大，为(40)。

还要注意，(a)数组要设两维，分别表示对应深度和数值，就不用回溯了。一定记得不能先令(b_i=a_i)，回溯时再(a_i=b_i)，因为随着(a_i)不断操作，(b_i)也会不断改变，那么(a_i)回溯到的值可能就不是原来的了。

Code

#include <bits/stdc++.h>

using namespace std;

int n, t, tt, sz, res = 1e9, a[55][100005], out[100005], cnt[100005], mul[100005], que[1000005];

int read()
{
	int x = 0, fl = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') fl = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
	return x * fl;
}

int check(int p, int len)
{
	for (int i = 1; i <= len; i ++ ) if (a[p][i]) return 0;
	return 1;
}

void dfs(int dep, int sum, int len)
{
	if (sum > res || dep > 41) return;
	int now = check(dep, len);
	if (now)
	{
		res = sum;
		for (int i = 1; i <= t; i ++ ) que[i] = cnt[i];
		sz = t;
		return;
 	}
	int fl = 1;
	for (int i = 1; i <= len; i ++ )
		if (a[dep][i] % 2) fl = 0;
	if (fl)
	{
		cnt[ ++ t] = 3;
		for (int i = 1; i <= len; i ++ ) a[dep + 1][i] = a[dep][i] / 2;
		int l0 = unique(a[dep + 1] + 1, a[dep + 1] + len + 1) - a[dep + 1] - 1;
		dfs(dep + 1, sum, l0);
		t -- ;
	}
	else
	{
		cnt[ ++ t] = 1;
		for (int i = 1; i <= len; i ++ ) a[dep + 1][i] = a[dep][i] + ((a[dep][i] & 1) > 0);
		int l0 = unique(a[dep + 1] + 1, a[dep + 1] + len + 1) - a[dep + 1] - 1;
		dfs(dep + 1, sum + 1, l0);
		t -- ;
		cnt[ ++ t] = 2;
		for (int i = 1; i <= len; i ++ ) a[dep + 1][i] = a[dep][i] - ((a[dep][i] & 1) > 0);
		l0 = unique(a[dep + 1] + 1, a[dep + 1] + len + 1) - a[dep + 1] - 1;
		dfs(dep + 1, sum + 1, l0);
		t -- ;
	}
	return;
}

int main()
{
	n = read();
	for (int i = 1; i <= n; i ++ )
		a[0][i] = read();
	sort(a[0] + 1, a[0] + n + 1);
	dfs(0, 0, n);
	printf("%d
", res);
	for (int i = 1; i <= sz; i ++ )
		mul[i] = mul[i - 1] + (que[i] == 3);
	for (int i = 1; i <= sz; i ++ )
	{
		if (que[i] == 1) out[ ++ tt] = -1 * pow(2, mul[i]);
		else if (que[i] == 2) out[ ++ tt] = pow(2, mul[i]);
	}
	for (int i = 1; i <= tt; i ++ )
		printf("%d ", out[i]);
	puts("");
	return 0;
}