#118. 【UR #8】赴京赶考
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://uoj.ac/problem/118
Description
高中，高中，短暂的三年。NOI是高中结业考试，而高考在每年暑假举行。
高二暑假，这是你最后一次参加高考的机会。你已经为了高考停课很久了，OI的知识很久没管了。你并没有能力用一年时间补起别人三年的OI课程。这是你的最后一战，如果你失败了，可能就不能工地搬砖只能去清华了。
这天你背上行囊赴京赶考。此时全国交通主要靠瞬间传送装置。全国交通网络可以抽象为一张 n 行 m 列的网格图。行依次编号为 1,…,n，列依次编号为 1,…,m。
有 n+m 个为 0 或 1 的整数 a1,…,an,b1,…,bm。对于 1≤i≤n，1≤j≤m，如果 ai=bj 那么网格图上第 i 行第 j 列上标着 0 否则标着 1。
你的家在第 xs 行第 ys 列，高考考场在第 xe 行第 ye 列。现在你想从家出发到高考考场去。每次你可以：
向上移动一行。（如果你在第一行那么移动后会到最后一行去）
向下移动一行。（如果你在最后一行那么移动后会到第一行去）
向左移动一列。（如果你在第一列那么移动后会到最后一列去）
向右移动一列。（如果你在最后一列那么移动后会到第一列去）
对于每次移动，如果移动前的格子上标的数跟移动后的格子上标的数不同，那么就要耗费 1 分钟时间等待瞬移装置调整配置，否则不耗时间。
现在你想知道你从家出发到高考考场最少需要花多长时间。
高二暑假，这是你最后一次参加高考的机会。你已经为了高考停课很久了，OI的知识很久没管了。你并没有能力用一年时间补起别人三年的OI课程。这是你的最后一战，如果你失败了，可能就不能工地搬砖只能去清华了。
这天你背上行囊赴京赶考。此时全国交通主要靠瞬间传送装置。全国交通网络可以抽象为一张 n 行 m 列的网格图。行依次编号为 1,…,n，列依次编号为 1,…,m。
有 n+m 个为 0 或 1 的整数 a1,…,an,b1,…,bm。对于 1≤i≤n，1≤j≤m，如果 ai=bj 那么网格图上第 i 行第 j 列上标着 0 否则标着 1。
你的家在第 xs 行第 ys 列，高考考场在第 xe 行第 ye 列。现在你想从家出发到高考考场去。每次你可以：
向上移动一行。（如果你在第一行那么移动后会到最后一行去）
向下移动一行。（如果你在最后一行那么移动后会到第一行去）
向左移动一列。（如果你在第一列那么移动后会到最后一列去）
向右移动一列。（如果你在最后一列那么移动后会到第一列去）
对于每次移动，如果移动前的格子上标的数跟移动后的格子上标的数不同，那么就要耗费 1 分钟时间等待瞬移装置调整配置，否则不耗时间。
现在你想知道你从家出发到高考考场最少需要花多长时间。
Input
第一行两个正整数 n,m，表示网格图为 n 行 m 列。
第二行 n 个整数，分别表示 a1,…,an。保证 a1,…,an∈{0,1}。
第三行 m 个整数，分别表示 b1,…,bm。保证 b1,…,bm∈{0,1}。
接下来一个正整数 q。
接下来 q 行，每行四个整数 xs,ys,xe,ye。表示询问如果你的家在第 xs 行第 ys 列，高考考场在第 xe 行第 ye 列时的最少花费时间。
第二行 n 个整数，分别表示 a1,…,an。保证 a1,…,an∈{0,1}。
第三行 m 个整数，分别表示 b1,…,bm。保证 b1,…,bm∈{0,1}。
接下来一个正整数 q。
接下来 q 行，每行四个整数 xs,ys,xe,ye。表示询问如果你的家在第 xs 行第 ys 列，高考考场在第 xe 行第 ye 列时的最少花费时间。
Output
共 q 行，每行一个整数表示最少花费多少分钟。
Sample Input
1 2
1
0 1
2
1 2 1 2
1 1 1 2
Sample Output
0
1
HINT
n,m≤105 q≤105
题意
题解：
n,m≤105,q≤105 的话，我们发现我们可以突破维度的界限，把每一维拆开分别考虑，最后的答案就是每一维的答案的和。
这为啥是对的呢？
对于 ai≠ai+1，无论 bj 取啥值，你从 (i,j) 穿越到 (i+1,j) 的时候，都必然会花费等待时间；否则如果 ai=ai+1 的话，就必然不会花费等待时间。所以一条路线的总等待时间可以拆分成各个维度的等待时间的和。
然后这个问题就变成一维问题啦，直接用算法一的搞法就可以了。
复杂度 O(n+m+q)，可以拿下100分。
代码：
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define test freopen("test.txt","r",stdin) #define maxn 2000001 #define mod 10007 #define eps 1e-6 const int inf=0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3fLL; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //************************************************************************************** int a[maxn]; int b[maxn]; int pre[maxn]; int pre1[maxn]; int n,m; int solve1(int x,int y) { if(y>=x) return pre[y]-pre[x]; return pre[n]-pre[x]+pre[y]+(a[n]^a[1]); } int solve2(int x,int y) { if(y>=x) return pre1[y]-pre1[x]; return pre1[m]-pre1[x]+pre1[y]+(b[m]^b[1]); } int main() { //test; n=read(),m=read(); for(int i=1;i<=n;i++) { a[i]=read(); if(i!=1) pre[i]=pre[i-1]+(a[i]^a[i-1]); } for(int i=1;i<=m;i++) { b[i]=read(); if(i!=1) pre1[i]=pre1[i-1]+(b[i]^b[i-1]); } int q=read(); for(int i=0;i<q;i++) { int x1=read(),y1=read(),x2=read(),y2=read(); printf("%d ",min(solve1(x1,x2),solve1(x2,x1))+min(solve2(y1,y2),solve2(y2,y1))); } }