EOJ 2020.7 C OLED 题解

题目大意

有一个$a\times b$的矩阵，中间含有一个$n\times m$的01矩阵，这个矩阵可以在大的矩阵中间移动（平移），移动不能重复，矩阵中的1可以使大矩阵这个位置加一，求大矩阵中每个位置的相对比例。即该点的值比上所有位置的最大值，乘以100。

解题思路

其实原本的题目并没有我写的大意这么容易理解。。。

看了半天没看懂啥意思。

由于小矩阵是可以进行移动的，那个可以以小矩阵中的1为对象。

发现他的移动区域是一块确定的空间。

对这块空间进行加一。

那么就可以使用二维差分了。

（应该算是模板题了。

取出小矩阵中的每个1，对于他的区间进行加1。

最后进行前缀和，求出每一位的值并输出即可。

其实读懂了题还挺简单的。

但是我还是第一次做二维差分和前缀和的。。

虽然之前学了一点。

推荐一下这个大佬写的二维差分和二维前缀和的博客，讲的很好。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int dif[4000][3000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int a, b, n, m;
	cin >> n >> m >> a >> b;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int num;
			cin >> num;
			if (num) {
				int x = b - m + j, y = a - n + i;
				dif[i][j]++;
				dif[i][x + 1]--;
				dif[y + 1][j]--;
				dif[y + 1][x + 1]++;
			}
		}
	}
	int M = 0;
	for (int i = 1; i <= a; i++) {
		for (int j = 1; j <= b; j++) {
			dif[i][j] += dif[i - 1][j] + dif[i][j - 1] - dif[i - 1][j - 1];//对差分数组进行求前缀和，得到这一位修改了多少
			M = max(M, dif[i][j]);
		}
	}
	for (int i = 1; i <= a; i++) {
		for (int j = 1; j <= b; j++) {
			printf("%d%c", 100 * dif[i][j] / M, j == b ? '\n' : ' ');
		}
	}
	return 0;
}