自动搬运

查看原文

来自洛谷，原作者为

	MaxFwl 这个家伙很懒，什么也没有留下。

搬运于2025-08-24 23:11:04，当前版本为作者最后更新于2025-03-16 13:58:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先考虑如何判断是否存在合法解。

由于所有限制都是关于两个数的相对关系的，所以我们可以假定 $b_1 = 0$，则是否存在合法解转化为是否存在一种方案满足前 $n - 1$ 条限制且 $\text{popcount}(b_n) = a_n$。

定义 $dp_{i, j}$ 表示是否存在一种方案使得满足前 $i - 1$ 条限制且 $\text{popcount}(b_i) = j$，考虑顺推，假设从第 $i$ 个数推到第 $i + 1$ 个数，枚举使 $b_i$ 中几个 $1$ 变为 $0$，则可以表示出其能转移到的下一个状态，复杂度 $O(nk^2)$。

dp[1][0] = 1;
for (int i = 1; i < n; i++){
	for (int j = 0; j <= k; j++)
		if (dp[i][j])
			for (int x = max(0, a[i] - k + j); x <= min(j, a[i]); x++)
				dp[i + 1][j - x + a[i] - x] = 1;
}

考虑优化，我们发现每次转移到的位置都是编号奇偶性相同的一段连续段，于是我们可以对编号为奇数和编号为偶数的位置分别建立差分数组，每次转移可以看成区间覆盖，这样可以做到 $O(nk)$。

dp[1][0] = 1;
for (int i = 1; i < n; i++){
	for (int j = 0; j <= k; j++)
		if (dp[i][j]){
			int l = abs(a[i] - j), r = min(a[i] + j, k * 2 - a[i] - j);
			if (l <= r){
				dp[i + 1][l]++;
				if (r + 2 <= k)		dp[i + 1][r + 2]--;
			}
		}
	for (int j = 2; j <= k; j += 2)	dp[i + 1][j] += dp[i + 1][j - 2];
	for (int j = 3; j <= k; j += 2)	dp[i + 1][j] += dp[i + 1][j - 2];
}

考虑如何找出合法解，我们把 dp 的过程倒过来，回溯找出一种合法的方案，由于根据上一个 dp 状态可以推出分别改了几个 $0$，几个 $1$，所以可以很简单地找出合法解，复杂度 $O(nk)$。

总复杂度 $O(nk)$，略微有点卡空间，实现的时候要注意一下。

code。