(ARC_103_B) 机械臂

题解

题意

形式化题意

给定 N 个平面上的点 (X₁, Y₁), (X₂, Y₂), …, (X_N, Y_N)。

需要判断是否存在一个由 m 个手臂组成的机器人手臂（1 ≤ m ≤ 40），每个手臂的长度为 dᵢ（1 ≤ dᵢ ≤ 10¹²），且每个手臂可以独立选择方向 L, R, D, U 之一。关节 0 位于原点 (0, 0)，关节 i 的坐标由关节 i-1 的坐标沿手臂 i 的方向移动长度 dᵢ 得到。

要求关节 m 能够恰好到达给定的 N 个点中的任意一个。

如果存在这样的机器人手臂，输出：

• 第一行：m
• 第二行：d₁ d₂ … d_m
• 接下来 N 行：每行一个长度为 m 的字符串 w_j，表示到达第 j 个点时各手臂的方向序列。

如果不存在，输出 -1。

数据范围

• 1 ≤ N ≤ 1000
• -10⁹ ≤ Xᵢ, Yᵢ ≤ 10⁹
• 1 ≤ m ≤ 40
• 1 ≤ dᵢ ≤ 10¹²

解法

这是一个很美妙的构造题明明是答份。

读完题之后发现毫无头绪，很难想到一个构造的方案，主要原因是因为这$4$种移动方式，分别只改变横坐标和只改变纵坐标，那么我们就需要考虑如何分机械臂去改变横坐标还是纵坐标，这是十分困难的 。

而这种时候就要用到一个比较经典的$track$旋转坐标系。

我们将坐标系旋转$45$度，这样我们的操作就可以转换为在新的坐标系上$(+1,+1),(+1,-1),(-1,+1),(-1,-1)$这样就可以在新的坐标系上做分别处理横纵坐标，且他们是相互独立的，这样一个二维问题就被我们转换为了一个一维的问题。

接下来考虑构造一个序列，并满足在这个序列中每个数填一个系数$1$或$-1$再相加可以构造出所有题目所需的坐标。

题目要求$m \leq 40$那么此时我们容易想到用类似二进制拆分的方式，将这些坐标拆出来。

可是直接拆的话就变成了填系数$1$或$0$，倘若我们要将那个系数$0$变成$-1$呢？

我们发现如果系数$0$变成了$-1$，怎么把系数变回常规的样子呢？再加上一个最大值不就行了？

假设我们有一个需要表示的坐标$x$，最大值是$s=2^{31}-1$

那么这个坐标$x$假设系数表示为$1,-1,-1,1,-1,1,-1$我们给它加个$s$ 那么系数就变成了$2,0,0,2,0,2,0$欸？好像有东西，再除以$2$呢？$1,0,0,1,0,1,0$这不就是一个数的二进制表示吗？

于是我们可以通过将$\frac{x+s}{2}$这个数的二进制表示中$1$位看成$1$,$0$位看成$-1$来知道如何操作。

但我们发现想要满足这个式子当且仅当$x+s\mod 2=0$才行。

由于$s$是奇数，所以$x$也必须是奇数。

那么如果$x$是偶数呢？

我们发现如果一组坐标，同时存在奇数和偶数是无法构造出任何方案的，因为将系数$1$改为$-1$改变的值一定是$2 \cdot x$即是个偶数。

如果只有偶数的情况可以直接在原坐标系上用一个长度为$1$的机械臂右移$1$次，这样就可将坐标在新坐标系上改为偶数了。

代码

code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e3+10;
int n;
ll x[N],y[N];
int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    int opt=0;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        if(!opt) 
        {
            if(((x[i]+y[i])%2+2)%2) opt=1;
            else opt=2;
        }
        else 
        {
            if(((((x[i]+y[i])%2+2)%2)&&opt==2)||(((x[i]+y[i])%2+2)%2==0&&opt==1))
            {
                cout<<-1<<'\n';
                return 0;
            } 
        }
    }
    if(opt==1) 
    {
        cout<<31<<'\n';
        for(int i=0;i<31;i++) cout<<(1<<i)<<' ';
        cout<<'\n';
    }
    else
    {
        cout<<32<<'\n';
        cout<<1<<' ';
        for(int i=0;i<31;i++) cout<<(1<<i)<<' ';
        cout<<'\n';
    }   
    for(int i=1;i<=n;i++)
    {
        if(opt==1)
        {
            ll kx=(x[i]+y[i]+(1ll<<31)-1ll)>>1ll;
            ll ky=(y[i]-x[i]+(1ll<<31)-1ll)>>1ll;
            for(int i=0;i<31;i++)
            {
                int opx,opy;
                if(kx&(1<<i)) opx=1;
                else opx=-1;
                if(ky&(1<<i)) opy=1;
                else opy=-1;
                if(opx==1&&opy==-1) cout<<'R';
                if(opx==1&&opy==1) cout<<'U';
                if(opx==-1&&opy==1) cout<<'L';
                if(opx==-1&&opy==-1) cout<<'D';
            }
            cout<<'\n';
        }
        else
        {
            cout<<'R';
            ll kx=(x[i]+y[i]+(1ll<<31)-2ll)>>1ll;
            ll ky=(y[i]-x[i]+(1ll<<31))>>1ll;
            for(int i=0;i<31;i++)
            {
                int opx,opy;
                if(kx&(1<<i)) opx=1;
                else opx=-1;
                if(ky&(1<<i)) opy=1;
                else opy=-1;
                if(opx==1&&opy==-1) cout<<'R';
                if(opx==1&&opy==1) cout<<'U';
                if(opx==-1&&opy==1) cout<<'L';
                if(opx==-1&&opy==-1) cout<<'D';
            }
            cout<<'\n';
        }
    }
    return 0;
}