Skip to content

UOJ - 118. 进京赶考

题解约 1.2 千字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目背景

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

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

#题目描述

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

n+mn + m 个为 0011 的整数 a1,,an,b1,,bma_1, \dots, a_n, b_1, \dots, b_m。对于 1in1 \leq i \leq n1jm1 \leq j \leq m,如果 ai=bja_i = b_j 那么网格图上第 ii 行第 jj 列上标着 00 否则标着 11

你的家在第 xsx_s 行第 ysy_s 列,高考考场在第 xex_e 行第 yey_e 列。现在你想从家出发到高考考场去。每次你可以:

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

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

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

#输入格式

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

第二行 nn 个整数,分别表示 a1,,ana_1, \dots, a_n。保证 a1,,an{0,1}a_1, \dots, a_n \in \{0, 1\}

第三行 mm 个整数,分别表示 b1,,bmb_1, \dots, b_m。保证 b1,,bm{0,1}b_1, \dots, b_m \in \{0, 1\}

接下来一个正整数 qq

接下来 qq 行,每行四个整数 xs,ys,xe,yex_s, y_s, x_e, y_e。表示询问如果你的家在第 xsx_s 行第 ysy_s 列,高考考场在第 xex_e 行第 yey_e 列时的最少花费时间。

#输出格式

qq 行,每行一个整数表示最少花费多少分钟。

#输入输出样例

样例输入 #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

#数据范围与约定

测试点编号 nn mm qq
11 100\leq 100 10\leq 10
22
33
44 105\leq 10^5 =10= 10 105\leq 10^5
55
66 105\leq 10^5
77
88
99
1010

#思路

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

#代码

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;
}