UOJ118-赴京赶考题解

题面

题目描述

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

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

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

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

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

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

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

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

输入格式

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

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

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

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

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

输出格式

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

样例输入

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

样例输出

0
1

数据规模与约定

对于$30\%$的数据，$n,m\le100, q\le10$

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

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

题解

思路

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

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

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

代码实现

时间复杂度$O(n+m+q)$

#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月份就考过，当时也没改这道题，这次考试看了半天才想出来，发个博客记录一下。