听说是两道思维题!可是我并没有思维!
A. 1-11F. JM的赃物被盗
http://222.180.160.110:1024/contest/3341/problem/1
题目一大堆 P 话,总而言之就是一个长方体,里面的每一个单位体积有自己的权值,接下来询问里面的子长方体内单位体积的权值之和。
所以这跟思维有什么关系呢?我不知道,但是我确实没写过三维前缀和。
设 \((x,y,z)\) 为左上角,\((a,b,c)\) 为右下角。
不妨画个图,令 \(x \gets x - 1, y\gets y - 1, z\gets z - 1\),然后得到下面这个式子(\(s_{a,b,c}\) 表示前缀和,\(f\) 表示待求):
\[f_{(x,y,z),(a,b,c)} = s_{a, b, c} - s_{x, b, c} - s_{a, y, c} + s_{x, y, c} - s_{a, b, z} + s_{x, b, z} + s_{a, y, z} - s_{x, y, z} \]那么问题来辽,\(s\) 本身要怎么求呢?再画个图就可以了:
\[s_{i, j, k} = a_{i - 1, j - 1, k - 1} + f_{(1, j, 1), (i, j, k - 1)} + f_{(i, 1, 1), (i, j - 1, k)} + f_{(1, 1, k), (i - 1, j, k)} \]注意到我们的式子是轮换的,所以不管你在思考和画图的时候三个坐标分别代表什么,只要你按着题目输入顺序来就可以了,不然可能会加空!!
namespace XSC062 {
using namespace fastIO;
const int maxn = 135;
int s[maxn][maxn][maxn];
int n, m, w, x, y, z, a, b, c, q;
inline int f(int x, int y, int z,
int a, int b, int c) {
--x, --y, --z;
return s[a][b][c] - s[x][b][c] - s[a][y][c] +
s[x][y][c] - s[a][b][z] + s[x][b][z] +
s[a][y][z] - s[x][y][z];
}
int main() {
read(n), read(m), read(w);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = 1; k <= w; ++k) {
read(s[i][j][k]);
s[i][j][k] += s[i - 1][j - 1][k - 1]
+ f(1, j, 1, i, j, k - 1)
+ f(i, 1, 1, i, j - 1, k)
+ f(1, 1, k, i - 1, j, k);
}
}
}
read(q);
while (q--) {
read(x), read(y), read(z);
read(a), read(b), read(c);
print(f(x, y, z, a, b, c), '\n');
}
return 0;
}
} // namespace XSC062
#undef int
B. 1-11H. cyy的养殖基地
http://222.180.160.110:1024/contest/3341/problem/2
总觉得 mj 确乎是讲过这么一道题的(ps:一诺说 mj 讲的那道是直线上,仿佛和这个不一样)……
标签:记录,int,230221,read,maxn,--,gets,长方体 From: https://www.cnblogs.com/XSC062/p/17141490.html