526互联

Atcoder ABC221G Jumping sequence

发布时间 2023-06-09 15:52:00作者: lhzawa

发现这个 \((x, y)\) 对应的是曼哈顿距离不太好求，那直接逆时针旋转 \(45\) 度（其实应该还要伸长 \(\sqrt{2}\) 倍，但是可以当做 \(d_i\) 也伸长 \(\sqrt{2}\) 倍不用去管）转化成切比雪夫距离 \((x - y, x + y)\)。
同时对应的 \(4\) 个方向在旋转后对应的方向也得到了改变：\(U(-d, d), R(d, d), D(d, -d), L(-d, -d)\)，这个可以通过上面得到的 \((x - y, x + y)\) 带进去算。
然后就发现可以分 \(x, y\) 轴来算了，因为 \(x\) 轴的符号无非就正或负，\(y\) 轴同理，\(2\) 个符号结合在一起都能对上 \(4\) 个方向中的 \(1\) 个。

然后考虑如何求解方案，设方案中符号为正的数的和为 \(a\)，符号为负的数的和为 \(b\)，要得到的数为 \(s\)，则可以得到以下式子：
\(\begin{cases}a + b = \sum\limits_{i = 1}^n d_i\\ a - b = s\end{cases}\)
所以可以得到 \(2a = \sum\limits_{i = 1}^n d_i +s\)。
于是当 \((\sum\limits_{i = 1}^n d_i + s) \bmod 2 = 1\) 或 \(\sum\limits_{i = 1}^n d_i +s < 0\) 时无解。

那么这个时候就可以去构造 \(a\) 了，这个东西还是挺板的，因为 \(a\) 代表的是符号为正的数的和，所以对于一个数只有不变或者 \(+d_i\) 这 \(2\) 种操作，然后就上一个背包。
但是时空复杂度 \(O(nm)\)，其中 \(m\) 为背包上限，此题中为 \(3.6\times 10^6\)，于是能发现时空全炸了。
但能发现这个背包只用记录合不合法，于是 bitset 优化，带上一个 \(\frac{1}{w}\) 的常数。
于是就可以跑背包先判断能不能凑出 \(a\)，不能则无解，能再倒退找到对应方案，最后 \(x, y\) 轴的符号相结合得到答案。

时空复杂度 \(O(\frac{nm}{w})\)。

// lhzawa(https://www.cnblogs.com/lhzawa/)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10, M = 3.6e6 + 10;
bitset<M> f[N];
int d[N];
int zf[N];
int main() {
	int n, a, b;
	scanf("%d%d%d", &n, &a, &b);
	int x = a - b, y = a + b;
	f[0].set(0);
	int s = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &d[i]);
		s += d[i];
		f[i] = f[i - 1]  | (f[i - 1] << d[i]);
	}
	if (x + s < 0 || y + s <0 || (s + x) % 2 == 1 || (s + y) % 2 == 1) {
		printf("No\n");
		return 0;
	}
	x = (s + x) / 2, y = (s + y) / 2;
	if ((! f[n][x]) || (! f[n][y])) {
		printf("No\n");
		return 0;
	}
	for (int i = n; i >= 1; i--) {
		if (x >= d[i] && f[i - 1][x - d[i]]) {
			zf[i] += 1, x -= d[i];
		}
		if (y >= d[i] && f[i - 1][y - d[i]]) {
			zf[i] += 2, y -= d[i];
		}
	}
	printf("Yes\n");
	for (int i = 1; i <= n; i++) {
		switch(zf[i]) {
			case 0: {
				printf("L");
				break;
			}
			case 1: {
				printf("D");
				break;
			}
			case 2: {
				printf("U");
				break;
			}
			case 3: {
				printf("R");
				break;
			}
		}
	}
	return 0;
}