链接：#118. 【UR #8】赴京赶考
高中，高中，短暂的三年。NOI是高中结业考试，而高考在每年暑假举行。 高二暑假，这是你最后一次参加高考的机会。你已经为了高考停课很久了，OI的知识很久没管了。你并没有能力用一年时间补起别人三年的OI课程。这是你的最后一战，如果你失败了，可能就不能工地搬砖只能去清华了。 这天你背上行囊赴京赶考。此时全国交通主要靠瞬间传送装置。全国交通网络可以抽象为一张 nn 行 mm 列的网格图。行依次编号为 ,…,n1,…,n，列依次编号为 ,…,m1,…,m。 有 n+mn+m 个为 或 的整数 a1,…,an,b1,…,bma1,…,an,b1,…,bm。对于 ≤i≤n1≤i≤n，≤j≤m1≤j≤m，如果 ai=bjai=bj 那么网格图上第 ii 行第 jj 列上标着 否则标着 。 你的家在第 xsxs 行第 ysys 列，高考考场在第 xexe 行第 yeye 列。现在你想从家出发到高考考场去。每次你可以： 向上移动一行。（如果你在第一行那么移动后会到最后一行去）
向下移动一行。（如果你在最后一行那么移动后会到第一行去）
向左移动一列。（如果你在第一列那么移动后会到最后一列去）
向右移动一列。（如果你在最后一列那么移动后会到第一列去）
对于每次移动，如果移动前的格子上标的数跟移动后的格子上标的数不同，那么就要耗费 分钟时间等待瞬移装置调整配置，否则不耗时间。 现在你想知道你从家出发到高考考场最少需要花多长时间。 输入格式
第一行两个正整数 n,mn,m，表示网格图为 nn 行 mm 列。 第二行 nn 个整数，分别表示 a1,…,ana1,…,an。保证 a1,…,an∈{,}a1,…,an∈{,}。 第三行 mm 个整数，分别表示 b1,…,bmb1,…,bm。保证 b1,…,bm∈{,}b1,…,bm∈{,}。 接下来一个正整数 qq。 接下来 qq 行，每行四个整数 xs,ys,xe,yexs,ys,xe,ye。表示询问如果你的家在第 xsxs 行第 ysys 列，高考考场在第 xexe 行第 yeye 列时的最少花费时间。 输出格式
共 qq 行，每行一个整数表示最少花费多少分钟。 样例一
input output 样例二
input output 限制与约定
测试点编号 n,mn,m的规模 qq的规模
n,m≤100n,m≤ q≤10q≤ n≤,m=1n≤,m= q≤105q≤ n,m≤105n,m≤ q≤105q≤ 时间限制：1s1s
空间限制：256MB
题干
如果10^5个询问，每次都无脑遍历肯定不行。
想一想横向移动，和纵向移动是互不影响的，那我单独考虑变成两个一维的。
但，10^5次遍历一个10^5的图也还不够。。。
我们又想到可以用个前缀和，表示从第一个位置到当前位置所用的时间
询问时：正着走一遍，倒着走一遍，横纵相加就行。
#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
int n,m,a[],b[],q,xs,ys,xe,ye;
int pre[],pree[];
int work1(int x,int y)
{
if(y>=x)
return pre[y]-pre[x];
return pre[n]-pre[x]+pre[y]+(a[n]^a[]);
}
int work2(int x,int y)
{
if(y>=x)
return pree[y]-pree[x];
return pree[m]-pree[x]+pree[y]+(b[m]^b[]);
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%d",&a[]);
for(int i=;i<=n;i++)
scanf("%d",&a[i]),pre[i]=pre[i-]+(a[i]^a[i-]);
scanf("%d",&b[]);
for(int j=;j<=m;j++)
scanf("%d",&b[j]),pree[j]=pree[j-]+(b[j]^b[j-]); scanf("%d",&q);
for(int i=;i<=q;i++)
{
scanf("%d%d%d%d",&xs,&ys,&xe,&ye);
int t1=min(work1(xs,xe),work1(xe,xs)),t2=min(work2(ys,ye),work2(ye,ys));
printf("%d\n",t1+t2);
}
return ;
}
代码