ABC221G 解题报告

· · 题解

题意

有一个无限大的平面直角坐标系，初始时你在 (0,0) 处。你要走 n 步，每次向上/下/左/右走 d_i 的距离，不能不走，最终要走到 (x,y)。

分析

有个套路？那就是把坐标系顺时针旋转 45 \degree，那就要更新一下旋转后的终点坐标和操作。

操作看起来比较容易，画一张坐标系可以发现，新坐标系上的单位长度是旧坐标系上的 \sqrt 2 倍，而且对应操作也变成了在横坐标和纵坐标上一起移动的形式。我们为了方便操作（解释）就把这个单位长度除以 \sqrt 2。终点坐标的变换见下图：

这里需要注意到一点，每次操作横坐标和纵坐标的值更改时相同的，也就是说我们只需要处理一遍 dp 就能处理出来他们俩的可行性。

到了这一步我们的问题就转换成了能否通过 \sum_{i=1}^{n}d_i \times a 这些移动使得最终坐标为 (x-y,x+y)， 其中 a \in \{ -1,1\}。有点像背包 dp，但是 x 不是选和不选的关系，那我们得进一步转换一下：我们先看横坐标（以下都只考虑横坐标，纵坐标类似），将左右两边同时加上 \sum d，这样左边就成为了 \sum_{i=1}^{n}d_i \times (a+1)，这里 a+1 \in\{0, 2\}，右边变成了 x-y +\sum d。这就有点类似了，但是可以进一步转换一下，左右两边同时除以 2，这样 a+1 的值就变成了 0 或 1，就转化成可行性 dp 了。

对于 dp，先将 x 转化成要 dp 的答案，即 \frac{x-y+\sum d}{2}，设 dp_{i,j} 表示取前 i 个状态，能否取到 j 这个坐标，basecase 为 dp_{0,0}=1，ans 为 dp_{n,x}。转移就是 dp_{i,j}=dp_{i-1,j}|dp_{i-1,j-d_i}。但是这里开数组时间有点炸，需要用 bitset 进行优化，转移方程大致相同，只不过省去了枚举 j 的循环，直接整体按位或。

判断完不可达之后就是回溯路径的时候了。我们看一下什么时候要取 d_i，只有当这一位到不了最终答案地时候才肯定要取它，也就是 dp_{i,x}=0 时就要取。那怎么判断方向呢，我们回到上面提到的在新坐标系中的操作方式（以下横纵坐标都只新坐标系中的），U 和 R 都是有纵坐标的变化的，L 都是 D 有横坐标变化的，那我们就要构造一种记录方式，考虑三进制——每一个数都有唯一的三进制值，仿照这个，设横坐标取的时候权值加 1，纵坐标加 2，模拟一下发现每一个方向都有一个唯一的值，这样就可以确定了。

至此完结撒花！！！

代码

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

int n, a, b, x, y, sum;
int d[2005], pos[2005];
bitset<3600005> dp[2005];//数据范围是3.6e6……

int main(){
    cin >> n >> a >> b;
    x = a - b, y = a + b;//更新旋转后终点位置
    for (int i = 1; i <= n; i++) cin >> d[i], sum += d[i];
    if (abs(x) > sum || abs(y) > sum) return cout << "No", 0;//特判
    if ((x + sum) & 1 || (y + sum) & 1) return cout << "No", 0;
    x = (x + sum) / 2, y = (y + sum) / 2;//直接转化成我们dp要去做的东西
    dp[1][0] = 1;//basecase 这里为了之后找路径方便计算（美观）把basecase第一维加了1，后面同理
    for (int i = 1; i <= n; i++) dp[i + 1] = dp[i] | (dp[i] << d[i]);//转移
    if (dp[n + 1][x] == 0 || dp[n + 1][y] == 0) return cout << "No", 0;//特判不可能到达
    for (int i = n; i >= 1; i--){
        int tmp = 0;
        if (!dp[i][x]) x -= d[i], tmp++;//统计方法
        if (!dp[i][y]) y -= d[i], tmp += 2;
        pos[i] = tmp;
    }
    cout << "Yes\n";
    for (int i = 1; i <= n; i++){
        if (pos[i] == 0) cout << "L";//按统计方法输出
        if (pos[i] == 1) cout << "D";
        if (pos[i] == 2) cout << "U";
        if (pos[i] == 3) cout << "R";
    }
    return 0;
}