UOJ118-赴京赶考题解

题面

题目描述

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

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

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

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

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

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

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

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

输入格式

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

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

第三行 mm 个整数,分别表示 b1,,bmb_1,…,b_m。保证 b1,,bm{0,1}b_1,…,b_m∈\{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
2
3
4
5
6
1 2
1
0 1
2
1 2 1 2
1 1 1 2

样例输出

1
2
0
1

数据规模与约定

对于30%30\%的数据,n,m100,q10n,m\le100, q\le10

对于另外20%20\%的数据,n,q100000,m=1n,q\le100000, m=1

对于100%100\%的数据,n,m,q100000n,m,q\le100000

题解

思路

仔细观察,就会发现对于每行或每列,与当前所在行/列无关,只与 aia_ibib_i 有关。

所以我们将每列和每行分别求经过边界到达和直接到达的最小值。

直接每次都暴力求一遍是肯定会超时的,我们可以将aa数组和bb数组做一个前缀和,然后就可以O(1)O(1)的时间复杂度应对询问。

代码实现-时间复杂度O(n+m+q)O(n+m+q)

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<array>
#include<algorithm>
#include<cmath>
#include<vector>
#include<bitset>
using namespace std;
using gg=long long;
bitset<100010> a,b;
array<gg,100010> aa,bb;
inline gg rd(){
char ch=getchar();gg x=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
inline bool getval(const gg &x,const gg &y){
return a[x]==b[y]?0:1;
}
int main(){
gg n,m,q,xs,ys,xt,yt,tp1,tp2;
n=rd(),m=rd();
char ch=getchar();
for(gg i=1;i<=n;i++){
while(ch<'0'||ch>'1') ch=getchar();
a[i]=ch-'0';
ch=getchar();
}
if(a[1]!=a[n]) aa[1]=1;
else aa[1]=0;
for(gg i=2;i<=n;i++){
if(a[i]!=a[i-1]) aa[i]=aa[i-1]+1;
else aa[i]=aa[i-1];
}
for(gg i=1;i<=m;i++){
while(ch<'0'||ch>'1') ch=getchar();
b[i]=ch-'0';
ch=getchar();
}
if(b[1]!=b[m]) bb[1]=1;
else bb[1]=0;
for(gg i=2;i<=m;i++){
if(b[i]!=b[i-1]) bb[i]=bb[i-1]+1;
else bb[i]=bb[i-1];
}
// for(gg i=1;i<=n;i++){
// for(gg j=1;j<=m;j++){
// cout<<getval(i,j)<<' ';
// }
// cout<<'\n';
// }
q=rd();
while(q--){
tp1=0,tp2=0;
xs=rd(),ys=rd(),xt=rd(),yt=rd();
if(xs<xt){
tp1=min(aa[xt]-aa[xs],aa[n]-aa[xt]+aa[xs]);
}
else if(xs>xt){
swap(xs,xt);
tp1=min(aa[xt]-aa[xs],aa[n]-aa[xt]+aa[xs]);
swap(xs,xt);
}
if(ys<yt){
tp2=min(bb[yt]-bb[ys],bb[m]-bb[yt]+bb[ys]);
}
else if(ys>yt){
swap(ys,yt);
tp2=min(bb[yt]-bb[ys],bb[m]-bb[yt]+bb[ys]);
swap(ys,yt);
}
cout<<tp1+tp2<<'\n';
}
return 0;
}

总结

题本身不是很难,只要发现了这个地图的特殊性即可做出。

6月份就考过,当时也没改这道题,这次考试看了半天才想出来,发个博客记录一下。