[TIOJ] 1991. 冰塊盒
題目連結:http://tioj.infor.org/problems/1991
大概看個一兩眼就會發現其實橫的跟直的可以分開,每個區塊都是獨立的(表示我選了這塊,我再選另一塊並不會影響前面那塊的值(某些奇怪的題目會有)),所以不難發現實作個二維的前綴和就好了,跟普通前綴和差不多,就輸出的時候再扣掉不要的部分就好了。
大概看個一兩眼就會發現其實橫的跟直的可以分開,每個區塊都是獨立的(表示我選了這塊,我再選另一塊並不會影響前面那塊的值(某些奇怪的題目會有)),所以不難發現實作個二維的前綴和就好了,跟普通前綴和差不多,就輸出的時候再扣掉不要的部分就好了。
#include <bits/stdc++.h>
using namespace std;
const int N = 2000000 + 5;
#define Hash(i, j) ((i)*(m+1)+(j))
bool mtx[N];
int preH[N], preZ[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n, m; cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mtx[Hash(i, j)];
if(mtx[Hash(i, j)] and mtx[Hash(i, j-1)]) preH[Hash(i, j)]++;
if(mtx[Hash(i, j)] and mtx[Hash(i-1, j)]) preZ[Hash(i, j)]++;
preH[Hash(i, j)]+=preH[Hash(i, j-1)];
preZ[Hash(i, j)]+=preZ[Hash(i-1, j)];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
preH[Hash(i, j)]+=preH[Hash(i-1, j)];
preZ[Hash(i, j)]+=preZ[Hash(i, j-1)];
}
}
int q; cin>>q;
while(q--){
int x1, y1, x2, y2; cin>>x1>>y1>>x2>>y2;
cout<<(preZ[Hash(x2, y2)]+preZ[Hash(x1, y1-1)]-preZ[Hash(x1, y2)]-preZ[Hash(x2, y1-1)] + \
preH[Hash(x2, y2)]+preH[Hash(x1-1, y1)]-preH[Hash(x1-1, y2)]-preH[Hash(x2, y1)])<<'\n';
}
return 0;
}
留言
張貼留言