首页 > 其他分享 >做题记录 // 230221

做题记录 // 230221

时间:2023-02-21 17:33:40浏览次数:34  
标签:记录 int 230221 read maxn -- gets 长方体

听说是两道思维题!可是我并没有思维!


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

相关文章