发现这个 \((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;
}
标签:Atcoder,limits,sequence,int,sum,符号,Jumping,zf,10
From: https://www.cnblogs.com/lhzawa/p/17469425.html