链接：#118. 【UR #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 列。现在你想从家出发到高考考场去。每次你可以： 向上移动一行。（如果你在第一行那么移动后会到最后一行去） 向下移动一行。（如果你在最后一行那么移动后会到第一行去） 向左移动一列。（如果你在第一列那么移动后会到最后一列去） 向右移动一列。（如果你在最后一列那么移动后会到第一列去） 对于每次移动，如果移动前的格子上标的数跟移动后的格子上标的数不同，那么就要耗费 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 行，每行一个整数表示最少花费多少分钟。 样例一 input 1 2 1 0 1 2 1 2 1 2 1 1 1 2 output 0 1 样例二 input 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 output 2 4 2 5 限制与约定 测试点编号 n,mn,m的规模 qq的规模 1 n,m≤100n,m≤100 q≤10q≤10 2 3 4 n≤105,m=1n≤105,m=1 q≤105q≤105 5 6 n,m≤105n,m≤105 q≤105q≤105 7 8 9 10 时间限制：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[100009],b[100009],q,xs,ys,xe,ye; int pre[100009],pree[100009]; int work1(int x,int y) { if(y>=x) return pre[y]-pre[x]; return pre[n]-pre[x]+pre[y]+(a[n]^a[1]); } int work2(int x,int y) { if(y>=x) return pree[y]-pree[x]; return pree[m]-pree[x]+pree[y]+(b[m]^b[1]); } int main() { scanf("%d%d",&n,&m); scanf("%d",&a[1]); for(int i=2;i<=n;i++) scanf("%d",&a[i]),pre[i]=pre[i-1]+(a[i]^a[i-1]); scanf("%d",&b[1]); for(int j=2;j<=m;j++) scanf("%d",&b[j]),pree[j]=pree[j-1]+(b[j]^b[j-1]); scanf("%d",&q); for(int i=1;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 ",t1+t2); } return 0; }