UOJ - 118. 进京赶考

#题面

#题目背景

高中，高中，短暂的三年。NOI 是高中结业考试，而高考在每年暑假举行。

高二暑假，这是你最后一次参加高考的机会。你已经为了高考停课很久了，OI 的知识很久没管了。你并没有能力用一年时间补起别人三年的 OI 课程。这是你的最后一战，如果你失败了，可能就不能工地搬砖只能去清华了。

#题目描述

这天你背上行囊赴京赶考。此时全国交通主要靠瞬间传送装置。全国交通网络可以抽象为一张 $n$ 行 $m$ 列的网格图。行依次编号为 $1, \dots, n$，列依次编号为 $1, \dots, m$。

有 $n + m$ 个为 $0$ 或 $1$ 的整数 $a_1, \dots, a_n, b_1, \dots, b_m$。对于 $1 \leq i \leq n$，$1 \leq j \leq m$，如果 $a_i = b_j$ 那么网格图上第 $i$ 行第 $j$ 列上标着 $0$ 否则标着 $1$。

你的家在第 $x_s$ 行第 $y_s$ 列，高考考场在第 $x_e$ 行第 $y_e$ 列。现在你想从家出发到高考考场去。每次你可以：

1. 向上移动一行。（如果你在第一行那么移动后会到最后一行去）
2. 向下移动一行。（如果你在最后一行那么移动后会到第一行去）
3. 向左移动一列。（如果你在第一列那么移动后会到最后一列去）
4. 向右移动一列。（如果你在最后一列那么移动后会到第一列去）

对于每次移动，如果移动前的格子上标的数跟移动后的格子上标的数不同，那么就要耗费 $1$ 分钟时间等待瞬移装置调整配置，否则不耗时间。

现在你想知道你从家出发到高考考场最少需要花多长时间。

#输入格式

第一行两个正整数 $n, m$，表示网格图为 $n$ 行 $m$ 列。

第二行 $n$ 个整数，分别表示 $a_1, \dots, a_n$。保证 $a_1, \dots, a_n \in \{0, 1\}$。

第三行 $m$ 个整数，分别表示 $b_1, \dots, b_m$。保证 $b_1, \dots, b_m \in \{0, 1\}$。

接下来一个正整数 $q$。

接下来 $q$ 行，每行四个整数 $x_s, y_s, x_e, y_e$。表示询问如果你的家在第 $x_s$ 行第 $y_s$ 列，高考考场在第 $x_e$ 行第 $y_e$ 列时的最少花费时间。

#输出格式

共 $q$ 行，每行一个整数表示最少花费多少分钟。

#输入输出样例

样例输入 #1

1 2
1
0 1
2
1 2 1 2
1 1 1 2

样例输出 #1

0
1

样例输入 #2

10 10
1 1 0 1 1 1 0 1 0 1
0 0 1 0 1 1 0 0 1 0
4
7 6 4 8
8 2 1 4
8 5 7 4
3 1 9 5

样例输出 #2

2
4
2
5

#数据范围与约定

#思路

由题可知，每次移动只能向上下左右四个方向移动。因为 $(i, j)$ 的权值由 $a_i$ 和 $b_j$ 决定，所以从 $(i, j)$ 移动到 $(i + 1, j)$ 的耗时与 $j$ 的取值无关，在 $y$ 轴上同理。那么可以分开处理 $x$ 轴和 $y$ 轴，计算出移动距离的前缀和即可以常数级别的复杂度处理每次询问。需要注意的是，向反方向移动也可以到达终点，因此需要取正向移动和反向移动耗时的最小值作为答案。

#代码

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

#include <iostream>
#include <algorithm>
#include <cmath>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 100005;

int n, m, q, d_a[N], d_b[N];
bool a[N], b[N];

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    if (a[1] != a[n]) d_a[0] = 1;
    for (int i = 1; i <= n; i++) {
        d_a[i] = d_a[i - 1] + (a[i] != a[i + 1]);
    }

    if (b[1] != b[m]) d_b[0] = 1;
    for (int i = 1; i <= m; i++) {
        d_b[i] = d_b[i - 1] + (b[i] != b[i + 1]);
    }

    cin >> q;

    while (q--) {
        std::pair<int, int> s, e;

        cin >> s.first >> s.second >> e.first >> e.second;

        cout << std::min({
                    std::abs(d_a[s.first - 1] - d_a[e.first - 1]),
                    d_a[n - 1] - d_a[std::max(s.first, e.first) - 1] + d_a[std::min(s.first, e.first) - 1],
                }) +
                    std::min({
                        std::abs(d_b[s.second - 1] - d_b[e.second - 1]),
                        d_b[m - 1] - d_b[std::max(s.second, e.second) - 1] + d_b[std::min(s.second, e.second) - 1],
                    })
             << endl;
    }

    return 0;
}