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

lailai0916 · 2026-08-30 21:54:29 · 题解

题意简述

棋盘有 n+1 行、n 列。第 2 到第 n 行各有一个障碍，且障碍所在列互不相同。构造至多 10n 条固定移动指令，使人从左上角出发后，在任意合法障碍分布下都曾到达最后一行。

解题思路

设第 i 行障碍所在列为 p_i。输出如下指令：

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

总长度为：

4n+4(n-2)+(n-1)+2+(n-1)=10n-8

它严格不超过限制。下面分三个阶段证明。

先执行 (\texttt{RDLD})^n。这一阶段没有向上移动，所以行号不会减小。直接检查一个 RDLD 块的四次尝试，可以得到以下结论：

若这个块没有下降，当前位置必须在某一侧边界；
从左上角按此前同样的块到达的状态中，右边界的停滞形态不会出现；
唯一可达的停滞状态是 (r,1)，且 p_r=2、p_{r+1}=1。

说明第二点。若一个块在非边界位置两次向下都失败，下一行唯一的障碍必须同时位于两次向下的目标列，所以中间的横向移动也必须失败。当前行只有一个障碍，这只能在边界形成局部封锁。右边界封锁要求当前行障碍在左侧一格；但第一次到达该边界时，正是依靠这一障碍挡住 L。同一块随后的第二次 D 会立刻越过封锁所需的下一行，无法留下右边界停滞。左边界则可以由 R 被当前行障碍挡住而形成上述状态。

因此，每个非停滞块至少下降一行。执行 n 个块后，要么已经到达第 n+1 行，要么停在：

\begin{aligned} (x,y) & =(r,1) \\ p_r & =2 \\ p_{r+1} & =1 \end{aligned}

此时 2\le r\le n-1。

只需处理这个停滞状态。沿左上方向寻找包含 p_r=2,p_{r+1}=1 的最长连续斜线，设最高行为 h。它满足：

p_i=r+2-i\text{ for }h\le i\le r+1

当前位置 (r,1) 正是第 r 行障碍左侧一格。若当前位于 (i,p_i-1) 且 i>h，执行一次 URRD：

U 到达上一行；
第一个 R 前进一步；
第二个 R 被上一行的障碍 p_{i-1}=p_i+1 挡住；
D 被当前行的障碍 p_i 挡住。

结束位置是 (i-1,p_{i-1}-1)，所以每个块沿斜线左侧上升一行。

到达 (h,p_h-1) 后，再执行一个 URRD。上一行的 p_h-1 与 p_h 两列已经被其他行的障碍占用，不能再出现障碍；若 p_h+1 也有障碍，斜线还能继续向上，与 h 的定义矛盾。因此两个 R 都能执行，随后 D 回到第 h 行障碍右侧。

从 r 上升到 h 并绕过斜线共需 r-h+1 个块。由 r\le n-1、h\ge2 可得：

r-h+1\le n-2

剩余的 URRD 块不会把人带回障碍左侧。每个块结束时仍在第 h 行，并位于 p_h 右侧。随后执行 n-1 个 L，一定会被第 h 行的障碍挡住，最终停在：

(h,p_h+1)

最后执行 DL。由于 p_{h+1}=p_h-1，向下和向左的目标格都不是障碍，最终到达 (h+1,p_h)。列 p_h 的唯一障碍已经位于第 h 行，所以此后连续执行 n-1 个 D 不会再受阻，并必然到达第 n+1 行。

构造字符串需要 O(n) 时间和 O(n) 空间。

正确性证明

第一阶段的块不使行号下降。除唯一可达的左边界封锁外，每个块至少下降一行，所以 n 个块后若尚未成功，状态必为 (r,1) 且相邻两行障碍列为 2,1。

第二阶段中，只要仍位于最长斜线左侧，一个 URRD 就准确上升一行并保持在下一障碍左侧。到达最高障碍后，列唯一性与斜线最大性保证下一块能绕到右侧。所需块数最多为 n-2，之后的左移把位置规范为 (h,p_h+1)。

第三阶段把人移到障碍列 p_h 的下方。该列在更低行不可能再有障碍，所以剩余向下移动必然到达最后一行。三阶段覆盖第一阶段成功与停滞两种情况，因此构造对任意合法障碍分布都有效。

参考代码

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    string ans;
    for(int i=0;i<n;i++)ans+="RDLD";
    for(int i=2;i<n;i++)ans+="URRD";
    for(int i=1;i<n;i++)ans+='L';
    ans+="DL";
    for(int i=1;i<n;i++)ans+='D';
    cout<<ans.size()<<'\n';
    cout<<ans<<'\n';
    return 0;
}