[Mivik Round 2021] [题解] Mirror

· · 题解

欢迎到我的博客查看

Subtask 1

由于可以直走，两个点之间要走多少格就是它们的曼哈顿距离了，然后中间需要拆除的障碍物直接判一下就好了。

Subtask 2

如果你善于观察，那么你会发现当起点位于 (0,0) 时，两个点之间要走多少格依旧等于他们的曼哈顿距离。为什么呢？

我们注意到时刻都必须有 x\&y=0，初始时是满足条件的，那么我们考虑每次取出 (x|y) 的 lowbit，然后把这一位走掉，一直这样直到走到 (0,0)，我们的总路径是 (x+y)。举个例子，假设 (x,y)=(4,3)，那么我们先写出二进制：

x: 100

y: 011

然后 lowbit 是 y 的 1，所以我们从 (4,3) 走到 (4,2)，变成了：

x: 100

y: 010

lowbit 是 y 的 2，所以我们从 (4,2) 走到 (4,0)，变成了：

x: 100

y: 000

然后直接走到 (0,0) 就可以了。容易发现最短的路径是唯一的，因为如果你减少的那一维不是 lowbit 所在的那一维的话，那么必定会产生一堆 1，然后这堆 1 就会和 lowbit 所在的那一维位与不为 0 了，不合法。

综上，我们模拟一下上面那个过程就好了。

mivik.h

// Mivik 2021.1.6
#include <mivik.h>

#include <algorithm>
#include <list>

using std::list;

MI cin;

typedef long long qe;

const int N = 200005;

struct point { qe x, y; };
template<> struct Q<point> { inline void operator()(MI &r, point &t) {
    r > t.x > t.y;
} };
int N;
point st, en, bar[N];
bool vis[N];
list<int> rem; // 还没被处理的障碍物
int main() {
    cin > n;
    for (int i = 1; i <= n; ++i) {
        cin > bar[i];
        rem.push_back(i);
    }
    cin > st > en;
    if (st.x || st.y) {
        cout < "Orz\n";
        return 0;
    }
    auto &[x, y] = en;
    cout < (x + y) < endl;
    for (int i = 0; i < 60; ++i) { // 扫描 lowbit
        if ((x >> i) & 1) {
            const qe to = x & (x - 1);
            for (auto it = rem.begin(); it != rem.end(); ) {
                auto &p = bar[*it];
                if (p.y == y && to <= p.x && p.x <= x) {
                    vis[*it] = 1;
                    it = rem.erase(it);
                } else ++it;
            }
            x = to;
        } else if ((y >> i) & 1) {
            const qe to = y & (y - 1);
            for (auto it = rem.begin(); it != rem.end(); ) {
                auto &p = bar[*it];
                if (p.x == x && to <= p.y && p.y <= y) {
                    vis[*it] = 1;
                    it = rem.erase(it);
                } else ++it;
            }
            y = to;
        }
    }
    for (int i = 1; i <= n; ++i) cout < vis[i];
    cout < endl;
}

满分做法

实际上我们可以递归。每次把一个宽和高都为 2^n 的迷宫（以 (0,0) 为左上角）平均分成四个部分，即左上左下右上和右下，但右下是不能走的所以我们忽略。如果当前位置和终点在一个块就继续向下递归，否则我们使两个点都统一“走”到左上角那一块然后再递归到左上角。容易发现这样对答案是没有影响的。

根据我们在 Subtask 2 中得到的结论，在一个块内的点是可以用 abs(x-\text{左上角x})+abs(y-\text{左上角y}) 的步数走到左上角的，因此计算距离就容易了。但是障碍物的判断呢？

实际上我们只需要判断一下 dist(st,p)+dist(p,en) 是否等于 dist(st,en) 就好了，因为根据上面的说明我们知道两点间的最短路径只有一条。

时间复杂度 O\left(\log^2(10^{18})n\right)。但我的实现 稍 微 研究了一下二进制本质然后写了一个 O(1) 判上面那个东西的函数，所以就少了个平方了。

mivik.h

代码