题解：CF1838F Stuck Conveyor

ZMQ_Ink6556 · 2024-11-20 17:13:53 · 题解

题解：CF1838F Stuck Conveyor

前置知识：IO 交互题。

题意简述

一个 n \times n 的正方形区域，有 n^2 个传送带方块，你每次可以指定每个方块的方向，并且在其中任意一个位置投放一个物品，物品会沿方块所指的方向运动，你最后会得知方块出来的位置 (x , y) 或方块进入了死循环 (-1 , -1)。但是有一个方块不会受到你的控制，而是会固定朝向一个方向，请你在 25 次分配内找到这个方块以及它的朝向。

解题思路

交互题、构造、二分。

打表找规律，可以发现：

• 如果出现了死循环，那么意味着你设计的路线比较靠后的一个点卡住了，跳到了比较靠前的点。
• 如果在错误的位置走出循环，那么说明紧挨着的点就是卡住的点。
• 如果正确，那么说明要么方向和你设计的路线相同，要么从一个比较靠前的点跳到了比较靠后的点。

所以我们可以设计出类似蛇形的地图：

>>>>v
v<<<<
>>>>v
v<<<<
>>>>v

^<<<<
>>>>^
^<<<<
>>>>^
^<<<<

此时可以发现这两张地图非常巧妙的让所有正确的情况在两张图里面没有交集，即：如果一个点在第一张图成功，那么一定是：

• 第一张图左、下成功对应第二张图右、上成功。
• 第一张图右、下成功对应第二张图左、上成功。

换句话说，无论如何也有一张图会让它死循环或出界。

生成第一张图：

void zmp()
{
    for(int i = 1 ; i <= n ; i++)
    {
        if(i % 2)
        {
            for(int j = 1 ; j < n ; j++)
            {
                cout << '>';
            }
            cout << 'v' << endl;
        }
        else
        {
            cout << 'v';
            for(int j = 1 ; j < n ; j++)
            {
                cout << '<';
            }
            cout << endl;
        }
    }
    return;
}

生成第二张图：

void fmp()
{
    for(int i = 1 ; i <= n ; i++)
    {
        if(i % 2)
        {
            cout << '^';
            for(int j = 1 ; j < n ; j++)
            {
                cout << '<';
            }
            cout << endl;
        }
        else
        {
            for(int j = 1 ; j < n ; j++)
            {
                cout << '>';
            }
            cout << '^' << endl;
        }
    }
    return;
}

此时，问题就被划分为了两个子问题：出界、死循环。

出界问题相对简单，直接判掉就可以了。

if(没到达目标位置且没有输入 -1 -1)
{
    if(x < 1)
    {
        x++;
        cout << "! " << x << ' ' << y << " ^" << endl;
        return 0;
    }
    if(x > n)
    {
        x--;
        cout << "! " << x << ' ' << y << " v" << endl;
        return 0;
    }
    if(y < 1)
    {
        y++;
        cout << "! " << x << ' ' << y << " <" << endl;
        return 0;
    }
    if(y > n)
    {
        y--;
        cout << "! " << x << ' ' << y << " >" << endl;
        return 0;
    }
}

死循环的情况相对复杂，需要先确定哪张图能够导致死循环，然后再做下一步处理。确定之后就最坏情况还剩 23 次询问，恰好我们需要在最多 10^4 个数里面找，联想 \log 级别的算法，联想二分算法。

我们可以把矩阵转换成一条链。

这条链就是物品在没有坏方块时要经过的道路，也就相当于上面的蛇形矩阵。链中有仅有一次每个位置，即链长是 n^2。

由于物品能不能正常离开满足单调性，所以可以在链上二分。

• 若放入物品，系统返回 (-1 , -1) 则代表错误点在链更靠后的位置。
• 若系统返回正常退出的位置，则代表错误在这个放入物品的位置之前。

换成代码来说，如果系统返回 x , y，[l , r] 为链上可能为答案的区间，那么可以用以下方法进行检查：

mid = (l + r) / 2;
if(x == -1 && y == -1)
{
    ans = mid;
    l = mid + 1;
}
else
{
    r = mid - 1;
}

通过 \log \text{链长} 的询问次数找到到底是哪个点出现了问题。

此时，答案即为链上答案点对应矩阵中的 x,y 坐标。

可是丧心病狂的出题人还要我们输出方向。

我们可以使用“冲浪”矩阵：

对于第一组地图构造：

vvvvv
vvvvv
vvvvv
vvvvv
vvvvv

对于第二组地图构造：

^^^^^
^^^^^
^^^^^
^^^^^
^^^^^

• 如果物品的 y 坐标等于答案的 y 坐标，那么答案就是顺着矩阵的方向。
• 如果物品的 y 坐标小于答案的 y 坐标，答案为 <。
• 如果物品的 y 坐标大于答案的 y 坐标，答案为 >。

这题就这么用特判堆过了。

期望最大询问次数：1 + 1 + 14 + 1 = 17。