[题解] [Mivik Round nurture] Mirror

[题解] [Mivik Round nurture] Mirror

一个无穷的地图,行列从 0 开始标号。$(i,j)$ 可以通过当且仅当 $(i\&j)=0$。同时地图中还有 $n$ 个炸弹。现在给出两个格子,保证可以通过,问从一个格子走到另一个格子至少需要走多少步,且在步数最少的情况下至少需要拆除哪些炸弹。

$1\le n\le 2\cdot 10^5$,$0\le x,y\le 10^{18}$

题目链接


思路

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 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

代码

作者

Mivik

发布于

2021-01-10

更新于

2021-05-31

许可协议

评论