[NC记录]AT4432 [ARC103B] Robot Arms
command_block
2021-05-17 10:53:19
**题意** ： 给定 $n$ 个坐标 $(x_i,y_i)$。
构造长度为 $m$ 的序列 $\{c_{1\sim m}\}$ ，满足：
- $c_i$ 表示第 $i$ 步「步长」。
- 对于每个坐标，从 $(0,0)$ 开始走，共走 $m$ 步。第 $i$ 步可以让 $(x,y)$ 变成 $(x±c_i,y)$ 或 $(x,y±c_i)$ 。
- 走完 $m$ 次之后，恰好走到这组坐标。
- 要求 $m\leq 40,c_i\leq 10^{12}$ 。
给出 $\{c_{1\sim m}\}$ 的具体值，以及每个坐标的行动方向序列。或指出无解。
$n\leq 10^3,x_i,y_i\leq 10^9$ ，时限$\texttt{2s}$。
------------
不难发现，最终到达的点的 $x+y$ 的奇偶性是相同的。故若给定的坐标中 $x+y$ 的奇偶性有不同，则无解。
观察下列图像，图中 `i` 是走第 $i$ 步能到达的范围 ：
```cpp
.......
.......
...1...
..101..
...1...
.......
.......
```
$c=\{1\}$。
```cpp
...2...
..212..
.2.2.2.
2120212
.2.2.2.
..212..
...2...
```
$c=\{2,1\}$。
不难发现，只需令 $c=\{2^m,2^{m-1},...,1\}$ ，就能达到 $O(2^m)$ 以内的任何 $x+y$ 为奇数的位置。
若要到所有 $x+y$ 为偶数的位置，则在 $c$ 后面再加一个 $1$ 即可。
最后考虑如何构造方向方案。
对于四种方向，走向离目的地曼哈顿距离最小的一个。不难理解正确性。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 1050
using namespace std;
ll x[MaxN],y[MaxN],c[MaxN];
int n,m;
int main()
{
scanf("%d",&n);
int o=0;
for (int i=1;i<=n;i++){
scanf("%lld%lld",&x[i],&y[i]);
o+=(x[i]+y[i])&1;
}
if (o!=0&&o!=n){puts("-1");return 0;}
for (int i=35;i>=0;i--)c[++m]=1ll<<i;
if (!o)c[++m]=1;
printf("%d\n",m);
for (int i=1;i<=m;i++)
printf("%lld ",c[i]);puts("");
for (int i=1;i<=n;i++){
ll sx=0,sy=0;
for (int k=1;k<=m;k++){
ll tx,ty,sav=1ll<<60,tx2,ty2;
char op;
tx=sx+c[k];ty=sy;
if (abs(x[i]-tx)+abs(y[i]-ty)<sav){
op='R';
sav=abs(x[i]-tx)+abs(y[i]-ty);
tx2=tx;ty2=ty;
}
tx=sx-c[k];ty=sy;
if (abs(x[i]-tx)+abs(y[i]-ty)<sav){
op='L';
sav=abs(x[i]-tx)+abs(y[i]-ty);
tx2=tx;ty2=ty;
}
tx=sx;ty=sy+c[k];
if (abs(x[i]-tx)+abs(y[i]-ty)<sav){
op='U';
sav=abs(x[i]-tx)+abs(y[i]-ty);
tx2=tx;ty2=ty;
}
tx=sx;ty=sy-c[k];
if (abs(x[i]-tx)+abs(y[i]-ty)<sav){
op='D';
sav=abs(x[i]-tx)+abs(y[i]-ty);
tx2=tx;ty2=ty;
}putchar(op);
sx=tx2;sy=ty2;
}puts("");
}return 0;
}
```