链接

题意

有个小机器人在 \((0,0)\)，构造一个长度为 \(m\) 的程序，每次执行 \(LRDU\) 中的一个，使得循环执行这个程序，在 \(t_i\) 时间在点 \((x_i,y_i)\)，\(t_i\leq 10^{18}\)。

题解

考虑每次钦定多走了 \((1,0)\)，然后旋转坐标轴。

这样两维就可以分开做了。

设 \(T\) 表示的是完整运行一个周期之后的坐标，设 \(k_i=\lfloor\frac{x_i}{m}\rfloor,w_i=x_i\bmod{m}\)，令 \(s_i\) 表示 \(i\) 时刻的位置，有 \(k_i=s_{w_i}+Tk_i\)。

显然 \(|s_{i}-s_{j}|\leq |j-i|\)，然后可以确定出 \(T\) 的范围，显然最后结果是一个区间，随意取一个即可。

然后反推出 \(s\) 即可。复杂度 \(O(n\log n)\)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 2000010
#define ll long long
#define ld long double
using namespace std;
struct node{
    ll x,k,w;
    node(ll X=0,ll K=0,ll W=0):x(X),k(K),w(W){}
    bool operator <(const node a)const{return w<a.w;}
}x[N],y[N];
int n,m;
void solve(node a[],int ans[])
{
    a[n+1]=node(0,-1,m);
    ll l=0,r=m;
    for(int i=1;i<=n+1;i++)
    {
        ll x=a[i].x-a[i-1].x,w=a[i-1].w-a[i].w;
        ld k=a[i].k-a[i-1].k;
        if(k<0) l=max(l,(ll)ceil(x/k)),r=min(r,(ll)floor((x+w)/k));
        else if(k>0) l=max(l,(ll)ceil((x+w)/k)),r=min(r,(ll)floor(x/k));
        else if(x+w>0 || x<0){puts("NO");exit(0);}
    }
    if(l>r){puts("NO");exit(0);}
    ll s=l;int c=0;
    for(int i=1;i<=n+1;i++)
    {
        ll x=a[i].x-a[i-1].x-(a[i].k-a[i-1].k)*s;
        int t=a[i].w-a[i-1].w;
        while(t --> 0) ans[++c]=(x --> 0);
    }
}
int ax[N],ay[N];
const char ans[]="DLRU";
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        ll t,x,y;
        scanf("%lld%lld%lld",&t,&x,&y);
        if((t+x+y)&1){puts("NO");return 0;}
        ::x[i]=node((x+y+t)>>1,t/m,t%m);
        ::y[i]=node((-x+y+t)>>1,t/m,t%m);
    }
    sort(x+1,x+n+1);sort(y+1,y+n+1);
    solve(x,ax);solve(y,ay);
    for(int i=1;i<=m;i++) putchar(ans[ax[i]<<1|ay[i]]);
    return 0;
}