Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


[UOJ Round #8]赴京赶考

传送门

题目描述

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

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

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

有 n+mn+m 个为 00 或 11 的整数 a1,…,an,b1,…,bma1,…,an,b1,…,bm。对于 1≤i≤n1≤i≤n,1≤j≤m1≤j≤m,如果 ai=bjai=bj 那么网格图上第 ii 行第 jj 列上标着 00 否则标着 11。

你的家在第 xsxs 行第 ysys 列,高考考场在第 xexe 行第 yeye 列。现在你想从家出发到高考考场去。每次你可以:

1.向上移动一行。(如果你在第一行那么移动后会到最后一行去)
2.向下移动一行。(如果你在最后一行那么移动后会到第一行去)
3.向左移动一列。(如果你在第一列那么移动后会到最后一列去)
4.向右移动一列。(如果你在最后一列那么移动后会到第一列去)
对于每次移动,如果移动前的格子上标的数跟移动后的格子上标的数不同,那么就要耗费 11 分钟时间等待瞬移装置调整配置,否则不耗时间。

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


输入格式

第一行两个正整数 n,mn,m,表示网格图为 nn 行 mm 列。
第二行 nn 个整数,分别表示 a1,…,ana1,…,an。保证 a1,…,an∈{0,1}a1,…,an∈{0,1}。

第三行 mm 个整数,分别表示 b1,…,bmb1,…,bm。保证 b1,…,bm∈{0,1}b1,…,bm∈{0,1}。

接下来一个正整数 qq。
接下来 qq 行,每行四个整数 xs,ys,xe,yexs,ys,xe,ye。表示询问如果你的家在第 xsxs 行第 ysys 列,高考考场在第 xexe 行第 yeye 列时的最少花费时间。

输出格式

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

解题思路

对于(ai,bi),若ai+1≠ai,则无论bi取何值,显然(ai,bi)到(ai+1,bi)都是需要花费1单位时间的。因此我们可以在x维度和y维度分别定义两种边:若ai≠ai+1,则ai到ai+1的距离就是1,否则为0。y维度亦然。

因此我们可以将x坐标和y坐标分块处理,得到每个维度上的边权的前缀和。然后根据x维度直接从xs走到xt、x维度从xs穿越边界走到xt、y维度直接从ys走到yt、y维度从ys穿越走到yt这四种情况进行讨论,得到最终的最短距离即可。复杂度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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MOD 998244353
#define MAXN 110000

using namespace std;

typedef long long int LL;

int n,m,Q;
int a[MAXN],b[MAXN],distA[MAXN],distB[MAXN];

int main()
{

scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d",&b[i]);
if(a[1]!=a[n]) distA[0]=1;
for(int i=1;i<=n;i++)
{
if(a[i]!=a[i+1])
distA[i]=distA[i-1]+1;
else distA[i]=distA[i-1];
}
if(b[1]!=b[m]) distB[0]=1;
for(int i=1;i<=m;i++)
{
if(b[i]!=b[i+1])
distB[i]=distB[i-1]+1;
else distB[i]=distB[i-1];
}
scanf("%d",&Q);
while(Q--)
{
int sx,sy,tx,ty;
scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
if(sx>tx) swap(sx,tx);
if(sy>ty) swap(sy,ty);
LL x1=abs(distA[sx-1]-distA[tx-1]);
LL x2=distA[n-1]-distA[tx-1]+distA[sx-1];
LL y1=abs(distB[sy-1]-distB[ty-1]);
LL y2=distB[m-1]-distB[ty-1]+distB[sy-1];
printf("%d\n",min(x1,x2)+min(y1,y2));
}
return 0;
}

Markdown

最近的文章

Chess

传送门题目描述 車是中国象棋中的一种棋子,它能攻击同一行或同一列中没有其他棋子阻隔的棋子。一天,小度在棋盘上摆起了许多車……他想知道,在一共N×M个点的矩形棋盘中摆最多个数的車使其互不攻击的方案数。他经过思考,得出了答案。但他仍不满足,想增加一个条件:对于任何一个車A,如果有其他一个車B在它的上方( …

于  组合数 继续阅读
更早的文章

百度之星初赛B--小小粉丝度度熊

传送门题目描述 度度熊喜欢着喵哈哈村的大明星——星星小姐。 为什么度度熊会喜欢星星小姐呢? 首先星星小姐笑起来非常动人,其次星星小姐唱歌也非常好听。 但这都不是最重要的,最重要的是,星星小姐拍的一手好代码! 于是度度熊关注了星星小姐的贴吧。 一开始度度熊决定每天都在星星小姐的贴吧里面签到。 …

于  尺取法, 贪心 继续阅读