链接
CF
题解
真的是人类智慧题啊。
首先遇到这种走格子题，往往都或许可以通过某些变换，将横纵坐标分开来考虑的。
考虑上面的套路，将坐标系旋转 $45$ 度，那么就变成了：
$$U(x+1,y+1),D(x-1,y-1),L(x-1,y+1),R(x+1,y-1)$$
原先的坐标 $(x,y)$ 就变成了 $(x+y,y-x)$。
现在就可以分开横纵坐标考虑了，每次可以加上 $1$ 或者减去 $1$，并满足第 $t_i$ 秒等于某个值 $x$。
设走了 $k$ 次 $+1$，那么有：$k-(t-k)=x$，即 $k=\frac{x+t}{2}$。
那么再转换一下，原先在第 $t$ 秒的坐标 $(x,y)$ 变成 $(\frac{x+y+t}{2},\frac{y-x+t}{2})$，然后横纵坐标都满足，每次 $+1$ 或者不加。（注意特判掉 $x+y+t$ 不是偶数的情况）
那么原先的四个方向就变成了：
$$U(x+1,y+1),D(x,y),L(x,y+1),R(x+1,y)$$
下面只考虑 $x$ 的（$y$ 同理）：
设第 $i$ 秒的位置在 $pos_i$。$k_i=\left\lfloor \frac{t_i}{l}\right\rfloor,w_i=t_i\bmod l$。
那么有：$X_i=pos_{t_i}=pos_l\times k_i+pos_{w_i}$。
$w_i$ 是比较小的，考虑将这 $n$ 个方程按照 $w_i$ 的大小排序，然后差分。
为了方便，我们加入两个方程，分别满足 $k_i=0,w_i=0,X_i=0$，以及 $k_i=-1,w_i=l,X_i=0$，原因是最前一段和最后一段也需要考虑。
假设是方程 $i$ 和方程 $j$ 进行差分，那么有：
$$X_i-X_j=pos_l\times (k_i-k_j)+(pos_{w_i}-pos_{w_j})$$
由于我们按照 $w_i$ 进行排序，那么就有 $pos_{w_i}-pos_{w_j}\geq 0$。
设 $X=X_i-X_j,k=k_i-k_j$。原式变为：$X=pos_l\times k+(pos_{w_i}-pos_{w_j})$
由于每次只能让 $pos_{i}$ 最多加上 $1$，因此 $pos_{w_i}-pos_{w_j}\in[0,w_i-w_j]$。
原式再变为：$X-(w_i-w_j)\leq pos_l\times k\leq X$。
根据 $k$ 的大小分 $k=0,k>0,k<0$ 三种情况进行讨论，得出无解，或者一个关于 $pos_l$ 大小的区间。
那么在这个区间内的值都是能满足的了。
得到了 $pos_l$，由最开始的方程 $X_i=pos_{t_i}=pos_l\times k_i+pos_{w_i}$ 就能算出每个 $pos_{w_i}$。
最后只需构造方案就好了，根据贪心，我们对于 $x,y$ 每次都加一，直到 $x$ 或 $y$ 不能再加为止。然后再 $x$ 或 $y$ 单独跳，最后走 $U(x,y)$（也就是不动）就好了。
时间复杂度 $O(n\log n)$。
程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| #include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline ll read()
{
ll x=0; char ch=getchar(); bool f=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=200020;
const ll inf=8e18;
int n,l;
struct node{
ll x,y,k,w;
friend inline bool operator<(const node &A,const node &B)
{
return A.w<B.w;
}
}q[N];
ll lx,rx,ly,ry,dx,dy,nx,ny;
int main()
{
n=read(); l=read();
ll X,Y,T,w,k;
fo(i,1,n)
{
T=read(); X=read(); Y=read();
if((X+Y+T)&1) return puts("NO")&0;
q[i].x=(X+Y+T)/2;
q[i].y=(Y-X+T)/2;
q[i].k=T/l; q[i].w=T%l;
}
q[n+1].k=-1,q[n+1].w=l;
sort(q+1,q+n+2);
lx=ly=-inf;
rx=ry=inf;
fo(i,1,n+1)
{
w=q[i].w-q[i-1].w;
k=q[i].k-q[i-1].k;
X=q[i].x-q[i-1].x;
Y=q[i].y-q[i-1].y;
if(k==0)
{
if(X-w>0||X<0) return puts("NO")&0;
if(Y-w>0||Y<0) return puts("NO")&0;
}
else if(k>0)
{
lx=max(lx,(ll)ceil((long db)(X-w)/k));
ly=max(ly,(ll)ceil((long db)(Y-w)/k));
rx=min(rx,(ll)floor((long db)X/k));
ry=min(ry,(ll)floor((long db)Y/k));
}
else
{
lx=max(lx,(ll)ceil((long db)X/k));
ly=max(ly,(ll)ceil((long db)Y/k));
rx=min(rx,(ll)floor((long db)(X-w)/k));
ry=min(ry,(ll)floor((long db)(Y-w)/k));
}
}
if(lx>rx||ly>ry) return puts("NO")&0;
nx=lx; ny=ly;
fo(i,0,n+1) q[i].x=q[i].x-q[i].k*nx,q[i].y=q[i].y-q[i].k*ny;
fo(i,1,n+1)
{
dx=q[i].x-q[i-1].x,dy=q[i].y-q[i-1].y;
X=Y=0; w=q[i].w-q[i-1].w;
for(;w--;)
{
if(X<dx)
{
++X;
if(Y<dy) ++Y,putchar('U');
else putchar('R');
}
else
{
if(Y<dy) ++Y,putchar('L');
else putchar('D');
}
}
}
return 0;
}
|