题解：CF1817D Toy Machine

ZMQ_Ink6556 · 2024-07-11 14:35:19 · 题解

题解：CF1817D Toy Machine

一道比较水的构造。

解题思路

我们可以打开英文题面给的链接，实践几次，就可以更快得到结论。

通过实践，我们发现，若 k 在图形前一半，也就是 k \le \lfloor\frac{n}{2}\rfloor 时，可以通过每轮操作将其左移一位来移动到左端，也就是 LDRU，如图：

经过操作，可以用下面的槽位将原有的第一位扔到后面，从而让第二个成为第一个，我们可以重复多轮这样的操作，使得第 k 个成为第一个。

但是不要认为这题就这么简单，比如在 n = 5 时，k = 4 或 k = 5 的方块都不能转到位置。而是 a、b 和 c 原地打转。

所以在 k > \lfloor\frac{n}{2}\rfloor 时，我们得推新的方法。比如说让这个方块先放到最右端：

同样是通过重复操作，使第 k 个方块到达最后一位，然后进行压缩，让所有方块都聚集在右边，形如：

然后按一下左后，这情况好像很熟悉，k 不就是第一种情况时最大的符合条件的位置吗？所以剩下的就可以按照第一种的方法做了。

总结第二种情况的思路：先是 n - k - 2 次 RDLU，再是 \lfloor \frac{n}{2} \rfloor 次 RDRU，最后是 \lfloor \frac{n}{2} \rfloor - 1 次 LDRU，最后一个 L，将第 k 个物品推到第一格。

这道题整体思维偏难，但代码非常简单，又可以水一道紫题。

参考代码

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int n , k , go_right;
int main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    n -= 2;
    if(k <= n / 2 + 1)
    {
        for(int i = 1 ; i < k ; i++)
        {
            cout << "LDRU";
        }
        cout << "L";
        return 0;
    }
    if(k > n / 2 + 1)
    {
        go_right = n - k;
        for(int i = 1 ; i <= go_right ; i++)
        {
            cout << "RDLU";
        }
        for(int i = 1 ; i <= n / 2 ; i++)
        {
            cout << "RDRU";
        }
        for(int i = 1 ; i <= n / 2 ; i++)
        {
            cout << "LDRU";
        }
        cout << "L";
    }
    return 0;
}

感谢浏览。