题解：P17305 [ICPC 2026 Xi'an I] Yesterday Once More (Easy Version)

lailai0916 · 2026-08-31 08:33:54 · 题解

题意简述

网格中的障碍位置未知。构造一组不超过 30n 步的固定指令。这组指令应适用于每种合法障碍分布，并使角色到达最后一行。

解题思路

先用 n 次 R 走到第一行最右端。接下来使用关于竖直中线对称的构造：

\texttt{R}^n(\texttt{LDRD})^n(\texttt{ULLD})^{n-1}\texttt{R}^n\texttt{DR}\texttt{D}^n

其长度为：

n+4n+4(n-1)+n+2+n=11n-2\le30n

为证明构造，先把列序反转。令原坐标的第 c 列对应新坐标的第 n+1-c 列。第一段 R 执行后，角色在新坐标的 (1,1)。剩余指令变为：

(\texttt{RDLD})^n(\texttt{URRD})^{n-1}\texttt{L}^n\texttt{DL}\texttt{D}^n

反转列序仍保持「每行一个、每列至多一个」的障碍限制。下面证明这段标准方向的指令一定成功。

记第 i 行的障碍列为 p_i，这些列两两不同。考虑一组 RDLD 开始时的位置 (r,c)。在到达最后一行前，始终保持 r\ge c。初始时两者都是 1。若组内至少一次向下成功，行号至少增加 1。整组指令让列号至多增加 1，所以不等式继续成立。

设某一组的两次向下均失败。两个目标格位于下一行，而该行只有一个障碍。因此，两次下移时的列必须相同，中间的 L 没有成功。

若该列为 1，则角色停在 (r,1)。第一次 R 被当前行第 2 列的障碍挡住。两次 D 被下一行第 1 列的障碍挡住。因此：

\begin{aligned} p_r & =2 \\ p_{r+1} & =1 \end{aligned}

若该列大于 1，L 只能被当前行的障碍挡住。此前的 R 不可能成功，否则障碍会落在移动前角色所在的格子。当前行也不能再有另一个障碍，所以 R 只能被右边界挡住，此时 c=n。由 r\ge c 得 r\ge n。若 r=n，下一行没有障碍，下移不会失败；若 r=n+1，已经完成目标。因此，这种情况在失败前不存在。

所以，每组 RDLD 要么使行号增加，要么进入上述停滞状态。后一状态会被后续同样的指令保持。执行 n 组后，若仍未到达最后一行，角色必定处于该状态。

从第 r+1 行向上取包含这两个障碍的最长连续斜线。设其最高行为 h。对所有 h\le i\le r+1，均有：

p_i=r+2-i

若角色位于 (i,p_i-1) 且 i>h，执行一组 URRD 后，前两步到达上一行障碍左侧。第二个 R 被该障碍挡住，D 又被当前行障碍挡住。最终位置为 (i-1,p_{i-1}-1)。因此，角色会沿斜线左侧逐行上移。

到达第 h 行后，斜线无法再向上延伸。下一组 URRD 的两个右移都能成功，随后下移到 (h,p_h+1)。这里不会碰到右边界，因为失败状态满足 r\le n-1，从而 p_h\le r<n。

剩余的 URRD 每次都先进入上一行，再向右移动，最后回到第 h 行。角色始终位于障碍 p_h 的右侧。随后执行 n 次 L，便会被该障碍挡在 (h,p_h+1)。

斜线性质给出 p_{h+1}=p_h-1。执行 DL 后，角色到达 (h+1,p_h)。第 p_h 列的唯一障碍已经位于第 h 行，所以该列下方完全畅通。最后的 n 次 D 一定会经过最后一行。

构造长度为 11n-2。时间复杂度为 O(n)，空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    string ans(n,'R');
    for(int i=1;i<=n;i++)ans+="LDRD";
    for(int i=1;i<n;i++)ans+="ULLD";
    ans+=string(n,'R');
    ans+="DR";
    ans+=string(n,'D');
    cout<<ans.size()<<'\n';
    cout<<ans<<'\n';
    return 0;
}