链接: https://ac.nowcoder.com/acm/contest/332/E
题意:
有一个沿海地区, 可以看作有 n 行 m 列的城市, 第 i 行第 j 列的城市海拔为 h[i][j].
由于沿海, 所以这个地区经常会发生海啸.
海啸发生时, 部分城市会被淹没, 具体来说, 海水高度会达到 d, 因此海拔低于 d 的城市都会被淹没.
现在有 q 次询问, 每次问你一个矩形区域中, 有多少城市不会被淹没.
思路:
二维前缀和
代码:
- #include <bits/stdc++.h>
- using namespace std;
- int main()
- {
- int n, m, d;
- int x;
- cin>> n>> m>> d;
- int res[n+1][m+1];
- for (int i = 0;i <= m;i++)
- res[0][i] = 0;
- for (int i = 0;i <= n;i++)
- res[i][0] = 0;
- for (int i = 1;i <= n;i++)
- {
- for (int j = 1; j <= m; j++)
- {
- cin>> x;
- int v = 0;
- if (x>= d)
- v = 1;
- res[i][j] = res[i][j - 1] + res[i - 1][j] - res[i - 1][j - 1] + v;
- }
- }
- int q;
- int x1,x2,y1,y2;
- cin>> q;
- for (int i = 1;i <= q;i++)
- {
- cin>> x1>> y1>> x2>> y2;
- cout << res[x2][y2] - res[x2][y1-1] - res[x1-1][y2] + res[x1-1][y1-1] << endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2945441.html